Database Reference
In-Depth Information
gap, the goal of this work is twofold: to devise a minimal division grammar that when encountered will
be rewritten to two contemporary SQL division queries; and to implement such a query rewriter in Java,
execute both rewritten queries on a sample database, and compare their returned sets for consistency.
It is not intended to expand the existing SQL syntax or the already accepted SQL standard; rather we
have developed a wrapper that could be integrated on the top of the existing SQL. This way, the end
users will be able to express explicit division using DIVIDE as if it is one of the agreed upon keywords
for SQL. Then, the developed rewriter translates the SQL query with DIVIDE into an equivalent SQL
query where the division is expressed using the traditional way in SQL and hence our approach does
not affect the underlying query system.
The rest of this paper is organized as follows. Next section describes the division operator, followed
by the discussion of proposed explicit division in SQL. We then cover the division grammar parser, and
report the results of the testing process. A special divide-by-zero case is discussed before our conclu-
sion of findings.
RELATIONAL DEVISION
Relational division is one of the eight basic operations in Codd's relational algebra (Darwen & Date,
1992). Though it can be coded using four of the five core relational algebra operators, it has been defined
as standalone operator to make the coding of queries involving explicit division easier. The concept
is that a divisor relation is used to partition a dividend relation and produce a quotient or results table.
The quotient table is made up of those values of one group of columns (or a single column) for which
a second group of columns (or column) had all of the values in the divisor.
Division in Relational Algebra
Let R
1
(A
∧
B) and R
2
(B) be relation schemas, where A = {a
i
,..,a
j
} and B = {b
r
,..,b
s
} are non-empty, disjoint
sets of ordered attributes. Let r
1
(R
1
) and r
2
(R
2
) be relations on these schemas with
r
1
÷ r
2
= r
3
, where by
definition the schema of r
3
is R
3
(A). Table r
1
is the
dividend
, r
2
is the
divisor
, and r
3
is the
quotient
of the
relational division operation. Healy's division (Date, 1995) is defined as follows:
r
1
÷r
2
= π
A
(r
1
)−π
A
((π
A
(r
1
) × r
2
) − r
1
) = r
3
A visual example of relational division is given below. This query could be interpreted as follows.
For A in R
1
(schema of R
1
minus schema of R
2
) find every value which is related with all values in R
2
.
Relational Division in SQL
The highly-regarded database textbook by Elmasri and Navathe describes the division operation using the
SQL formulation of D0 (see below) (Elmasri & Navathe, 2006). The use of the NOT EXISTS predicates
is for speed because most SQL parsers in DBMSs will look up a value in an index rather than scan the
whole table (Harris & Shadbolt, 2005). This query for relational division was made popular by Chris
Date in his textbooks (Codd, 1972).
