{'fraction_non_alphanumeric': 0.033761577532118316, 'fraction_numerical': 0.008863658998107758, 'mean_word_length': 4.995223880597015, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
TransJoin: An Algorithm to Implement Division Operator of Relational Algebra in Structured Query Language

Division operator is one of operators in Relational Algebra which is not implemented directly in SQL (Structured Query Language) standard. Therefore it is not be able to retrieve division query results with an SQL statement in the current relational database management systems (RDBMS). Database programmers have to create a complicated query to perform the task. It is the only relational algebra operators which is not implemented in ANSI SQL standard. This research aimed to study and design an algorithm named TransJoin (transformation and join) to implement it in SQL. TransJoin works to relation P(x, y) divided by Q(y) resulted R(x) through grouping and transforming each y attribute becomes P’(x, y’) and Q’(y’) and each x value is a single tuple with y’ is a composite value of y. Then, result R(x) is resulted of joining P’(x, y’) and Q’(y’) relations by matching y’ attribute. TransJoin was implemented in an open source RDBMS SQLLite. TransJoin tested and delivered valid results by comparing of traditional SQL queries and our proposed SQL queries with various data. The research showed that our algorithm is much more efficient by consuming 0.078 milliseconds compared contrasted the traditional query in 1,974.08 milliseconds for 9,991 tuples.


Introduction
Modern database was started in 1960s when computer was discovered. In 1970, Edgar Frank Codd published a paper "A Relational Model of Data for Large Shared Data Banks". It was the first theory of relational database. Codd offered algebra as foundation of query language for database. He introduced six primitive algebra operators: Selection, Projection, Cartesian product, Union, Set difference and Rename. While the derivative operators are Intersections, Divisions, and Joins. Join operator consist Natural Join, Equijoin, Semijoin, Antijoin and Devide [1]. SQL (structured query language) is a relational database language. In 1986, a standard for SQL was defined by the American National Standards Institute (ANSI) and was subsequently adopted in 1987 as an international standard by the International Organization for Standardization (ISO, 1987). More than one hundred DBMSs now support SQL, running on various hardware platforms from PCs to mainframes [2].
SQL implemented all Code's relational algebra operations except division operations. Native SQL did not have direct operator to solve division query need. In the order words, no direct syntax of division operator in SQL. SQL programmers built their own methods and logics using existing operators to solve their requirements.
Cases of division operations are very common and often appear in queries used to solve any problems. However, the current solution or temporary solution used was to use a combination of various 2 existing operators with their respective different methods. Using the existing query programmers built their SQL query by using sub-query. The method implicated to poor performance and inefficient to produce query results. Moreover, the logic were really complicated.

Methods
The research focused on study of division operator in SQL and designed an algorithm of division operator to be implemented as SQL standard. The algorithm applied using C language in SQLite, one of open source RDBMS engine.
The algorithm would be validated by comparing query results of the new standard with the ones using conventional method. The research would design recommendation standard of using our division operator to SQL Organization (sql.org) to implement our research output.

Algorithm Design
Division operator was the only operator which did not support and be implemented in SQL Standard for ANSI SQL-2008. Joe Celko, a writer for some books about SQL, had been devoted himself more than 10 years in ANSI/ISO SQL Committee, and a contributor of SQL-89 and SQL-92 standard, in his electronic journal deplored division operator has not been adopted in SQL standard. [4] Division is binary operation which is written as R ÷ S. The operation results are tuples in set R relates to set S as the followed instance: In the real world there are many division cases. For instances, finding programmers who have skill set of all programming language, finding suppliers who provide all product items, and finding library members who borrow all computer books. Database practitioners use different method to solve division cases. Current solving method combines several algebra operators: projection, Cartesian product, set difference, and join. They also use sub-query to solve the problems which is lack and inefficient performance.
Division operator algorithm comprises definite division and partial division. Below is explanation of both algorithms.

Definite Division Algorithm
Given two relations R(X,Y) and S(Y), the results of R ÷ S operation defined as maximum relation Q which qualifies for: The definition is written as: Furthermore, an algorithm which directly implements the above definition will be given, but beforehand it will be explained beforehand a definition that will be used in the algorithm: , where X and Y may composite, R grouped by X, written as X  (R), is a grouping operation R(X,Y) by X transforms to γ(X,Y) that: The following is an example for R(X,Y):

Partial Division Algorithm
For two relations R(X,Y) and S(Z,Y), the result of R ÷ S is defined as maximum relation Q which qualifies for: The following is given two algorithms to implement the definition of the relation structure of the results of the partial division operations using the help of Definition 1 (transformation). In addition, one of them also uses Algorithm 1 (Definite Division Algorithm): In conclusion, the algorithm works by grouping (transforming) all values of each group into single tuple (cell) for both columns then performing inner join for value of both columns (attributes). We call this algorithm as TransJoin (transformation and join).

Proposal of New SQL Standard on SELECT Statement
In this section we will discuss grammar design and syntax of the algorithm. Division operator implemented with a syntactic pattern which is grammatically similar JOIN operator. As join operation, a division operation involves more than one table, and requires a column that is made as a condition (divisor factor attribute). We applied the design algorithm (Definite Division and Partial Division). The algorithm is implemented syntactically using the same the operator, DIVIDE.
Design of proposed SQL standard composed in the form of BNF (Backus-Naur form) to ease probability of existing RDBMS which support the form. Modification of SQL standard is by inserting in code of QUERY (SELECT STATEMENT) with addition of using DIVISION operation. The following is modification of the standard. … <scalar subquery> ::= <subquery> <subquery> ::= <left paren> <query expression> <right paren> <query expression> ::= <non-join query expression> | <joined table> | <divided table> <non-join query expression> ::= <non-join query term>  The following is given 3 (three) common relations in database system text books: Supplier, Part, and SupplierPart.

Figure 2. Supplier, part, and supplier part relations
Here is division operation of Relational Algebra to solve problem for finding suppliers (SupplierID) who supply all parts (PartID).
Using the existing standard we write below query statement. While using the new standard the query statement is: SELECT DISTINCT SupplierID FROM SupplierPart DIVIDE Part using (PartID)

Implementation
The algorithm is implemented in SQLite (http://www.sqlite.org) which is an embedded RDBMS engine in the form of an in-process library that was developed using the C programming language. The main reason for choosing SQLite is because it is an RDBMS engine that is public domain and open source, so it is more realistic to be implemented as an object of implementation of the algorithm. The implementation is by modifying the SQLite library in order to make the engine recognize the "DIVIDE" token with the grammar-compliant syntax and produces output that matches the division operation. Figure 3 depicts SQLite architecture. "Other source files" comprises C code files collection which contains 107 files including header-files. One of the files is "SELECT.C" as the core of SELECT statement. Based on an analysis of the overall flow of the existing process, the modification steps taken are: adding DIVIDE keywords to be recognized by the parser; modifying the grammar on the parser so that it can recognize DIVIDE syntax patterns; adding a new type other than JOIN and modify the parser to generate code for that type; and adding new process functions as the core of the processing routines performed on the DIVIDE type..

Evaluation
Tests for the proposed new query (SELECT query contains the DIVIDE operator) compared against classic queries which are alternative queries that exist in a variety of commonly found database literature books [5][6][7] [10] and in general are often used and taught academically as an alternative form of query for the implementation of division operations.
The test factors to be compared are of two types. The first one is in terms of performance factors to the existing query by looking at the travel time used (elapsed time). Then the second is in terms of ease of use factor with the indicator used is the number of tokens / words used in each query. We conducted 10 (ten) tests with different number of tuples then we compare query time between the conventional query and new query for the same cases. Q1 is execution time for conventional query while Q2 is for the new query as in Table 1. The test used the same machine with the specifications are Intel Core2Duo 2,66Ghz, RAM 3GB under Windows 7 32-bit operating system. Table 1 showed that that new query (using our algorithm) is much more efficient by consuming 0.078 milliseconds compared contrasted the traditional query in 1,974.08 milliseconds for 9,991 tuples.