Subsumption and indexing in constraint query languages with
linear arithmetic constraints.
Divesh Srivastava.
Bottom-up evaluation of a program-query pair in a constraint query
language (CQL) starts with the facts in the database and repeatedly
applies the rules of the program, in iterations, to compute new facts,
until we have reached a fixpoint. Checking if a fixpoint has been
reached amounts to checking if any ``new'' facts were computed in an
iteration. Such a check also enhances efficiency in that subsumed
facts can be discarded, and not be used to make any further
derivations in subsequent iterations, if we use Semi-naive evaluation.
We show that the problem of subsumption in CQLs with linear arithmetic
constraints is co-NP complete, and present a deterministic algorithm,
based on the divide and conquer strategy, for this problem. We also
identify polynomial-time sufficient conditions for subsumption and
non-subsumption in CQLs with linear arithmetic constraints. We adapt
indexing strategies from spatial databases for efficiently indexing
facts in such a CQL: such indexing is crucial for performance in the
presence of large databases. Based on a recent algorithm by Lassez
and Lassez [LL] for quantifier elimination, we present an incremental
version of the algorithm to check for subsumption in CQLs with linear
arithmetic constraints.