Abstract
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 C. Lassez and J.-L. Lassez for quantifier elimination, we present an incremental version of the algorithm to check for subsumption in CQLs with linear arithmetic constraints.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
F. Bancilhon, Naive evaluation of recursively defined relations, in:On Knowledge Base Management Systems — Integrating Database and AI Systems, ed. Brodie and Mylopoulos (Springer, 1985).
M. Baudinet, M. Niezette and P. Wolper, On the representation of infinite temporal data and queries, in:Proc. 10th ACM Symp. on Principles of Database Systems, Denver, CO (1991) pp. 280–290.
I. Balbin and K. Ramamohanarao, A generalization of the differential approach to recursive query evaluation, J. Logic. Progr. 4(3) (1987).
J. Chomicki, Polynomial time query processing in temporal deductive databases, in:Proc. 9th ACM Symp. on Principles of Database Systems, Nashville, TN (1990) pp. 379–391.
M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, 1979).
A. Guttman, R-trees: A dynamic index structure for spatial searching, in:Proc. ACM SIGMOD Conf. on Management of Data (1984) pp. 47–57.
J. Jaffar and J.-L. Lassez, Constraint logic programming, in:Proc. 14th ACM POPL, Munich (1987) pp. 111–119.
J. Jaffar, S. Michaylov, P. Stuckey and R. Yap, The CLP(ℛ) language and system, Technical Report, IBM, T.J. Watson Research Center (1990).
P.C. Kanellakis, G.M. Kuper and P.Z. Revesz, Constraint query languages, in:Proc. 9th ACM Symp. on Principles of Database Systems Nashville, TN (1990) pp. 299–313.
C. Lassez and J.-L. Lassez, Quantifier elimination for conjunctions on linear constraints via a convex hull algorithm, submitted.
J.-L. Lassez and M.J. Maher, On Fourier's algorithm for linear arithmetic constraints, Technical Report, IBM, T.J. Watson Research Center (1988).
R. Ramakrishnan, Magic templates: A spellbinding approach to logic programs, in:Proc. Int. Conf. on Logic Programming, Seattle, Washington (1988) pp. 140–159.
P.Z. Revesz, A closed form for Datalog queries with integer order, in:Int. Conf. on Database Theory, France (1990) pp. 187–210.
A. Schrijver,Theory of Linear and Integer Programming, Discr. Math. Optim. (Wiley-Interscience, 1986).
D. Srivastava and R. Ramakrishnan, Pushing constraint selections, in:Proc. 11th ACM Symp. on Principles of Database Systems, San Diego, CA (1992).
T. Sellis, N. Roussopoulos and C. Faloutsos, The R+-tree: A dynamic index for multi-dimensional objects, in:Proc. 13th Int. Conf. on Very Large Databases (1987) pp. 507–518.
Author information
Authors and Affiliations
Additional information
This work was supported by a David and Lucile Packard Foundation Fellowship in Science and Engineering, a Presidential Young Investigator Award, with matching grants from the Digital Equipment Corporation, Tandem and Xerox, and NSF Grant No. IRI-9011563.
Rights and permissions
About this article
Cite this article
Srivastava, D. Subsumption and indexing in constraint query languages with linear arithmetic constraints. Ann Math Artif Intell 8, 315–343 (1993). https://doi.org/10.1007/BF01530796
Issue Date:
DOI: https://doi.org/10.1007/BF01530796