Database Reference
In-Depth Information
Figure 1. Visual example of relational division
corresponding SQL queries that involve same tables/attributes. However the MySQL parser reported
them as erroneous queries because they refer to non-existing tables/attributes.
Software Used
Zql: A Java SQL Parser
An established SQL lexical parser is needed to check and validate ordinary SQL queries and to explode
clauses such as
select
,
from
and
where
. Zql (Karvounarakis et al., 2002) is appropriately-suited for this
as it is light-weight and easy to use. Unfortunately it is deprecated and unmaintained by its authors.
MySQL with XAMPP
XAMPP is an Apache distribution (Leinders & den Bussche, 2005) which contains MySQL - a popular
DBMS which is free, widespread and easy to install.
Performance
Consistently, the count method division returned results more than an order of magnitude faster that
the not-exists/except division method while returning the same results set
1
. Leinders and den Bussche
show an interesting theoretical result about the divide operation (http://www.gibello.com/code/zql/).
Algorithms implementing the divide operation based on sorting and counting, as in R0, can achieve a
time complexity of
O(n log n).
In contrast, they show that any expression of the divide operator in the
relational algebra with union, difference, projection, selection, and equi-joins must produce intermedi-
ate results of quadratic size. The resources and time needed to rewrite a character string as outlined in
this paper are negligible.
The implementation is tested on Windows XP Professional (3.39GHz, 1GB of RAM). We randomonly
sample DIVIDE queries from a pool of different cases. The performance chart is shown in Figure 1,
where data labels are average time(ms) per query, we observe that the parsing and rewrite execute ef-
ficently on avarage, including large sampled data set.
