×

Subsumtion and indexing in constraint query languages with linear arithmetic constraints. (English) Zbl 1034.68516

Summary: 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 a fixpoint is reached. 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 nonsubsumption 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. Making use of 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

MSC:

68P15 Database theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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).
[2] 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.
[3] I. Balbin and K. Ramamohanarao, A generalization of the differential approach to recursive query evaluation, J. Logic. Progr. 4(3) (1987). · Zbl 0636.68125
[4] 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.
[5] M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, 1979). · Zbl 0411.68039
[6] A. Guttman, R-trees: A dynamic index structure for spatial searching, in:Proc. ACM SIGMOD Conf. on Management of Data (1984) pp. 47-57.
[7] J. Jaffar and J.-L. Lassez, Constraint logic programming, in:Proc. 14th ACM POPL, Munich (1987) pp. 111-119.
[8] J. Jaffar, S. Michaylov, P. Stuckey and R. Yap, The CLP(?) language and system, Technical Report, IBM, T.J. Watson Research Center (1990).
[9] 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.
[10] C. Lassez and J.-L. Lassez, Quantifier elimination for conjunctions on linear constraints via a convex hull algorithm, submitted. · Zbl 0307.94015
[11] J.-L. Lassez and M.J. Maher, On Fourier’s algorithm for linear arithmetic constraints, Technical Report, IBM, T.J. Watson Research Center (1988).
[12] R. Ramakrishnan, Magic templates: A spellbinding approach to logic programs, in:Proc. Int. Conf. on Logic Programming, Seattle, Washington (1988) pp. 140-159.
[13] P.Z. Revesz, A closed form for Datalog queries with integer order, in:Int. Conf. on Database Theory, France (1990) pp. 187-210. · Zbl 0789.68042
[14] A. Schrijver,Theory of Linear and Integer Programming, Discr. Math. Optim. (Wiley-Interscience, 1986). · Zbl 0665.90063
[15] D. Srivastava and R. Ramakrishnan, Pushing constraint selections, in:Proc. 11th ACM Symp. on Principles of Database Systems, San Diego, CA (1992). · Zbl 0805.68035
[16] 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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.