×

A closed-form evaluation for Datalog queries with integer (gap)-order constraints. (English) Zbl 0785.68026

We provide a generalization of Datalog based on generalizing databases by adding integer order constraints to relational tuples. For Datalog queries with integer (gap)-order constraints (denoted as Datalog\(^{<Z})\), we show that there is a closed-form evaluation. We also show that the tuple recognition problem can be done in PTIME in the size of the generalized database, assuming that the size of the constants in the query is logarithmic in the size of the database. Note that the absence of negation in critical, Datalog\(^ \neg\) queries with integer order constraints can express any Turing-computable function.
Reviewer: P.-Z.Revesz

MSC:

68P15 Database theory
68Q25 Analysis of algorithms and problem complexity
03C57 Computable structure theory, computable model theory

Software:

CHIP; Datalog
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abiteboul, S.; Vianu, V., Procedural and declarative Database update languages, Proc. 7th ACM Symp. Principles of Database Systems, 240-250 (1988)
[2] Aylamazyan, A. K.; Gilula, M. M.; Stolboushkin, A. P.; Schwartz, G. F., Reduction of the relational model with infinite domain to the case of finite domains, Proc. USSR Acad. of Science (Doklady), 286, 2, 308-311 (1986)
[3] Codd, E. F., A relational model for large shared data banks, Comm. ACM, 13, 377-387 (1970) · Zbl 0207.18003
[4] Colmerauer, A., An introduction to Prolog III, Comm. ACM, 28, 412-418 (1990)
[5] Chandra, A. K.; Harel, D., Computable queries for relational data bases, J. Comput. System Sci., 21, 156-178 (1980) · Zbl 0456.68128
[6] Chandra, A. K.; Harel, D., Horn clause queries and generalizations, J. Logic Prog., 2, 1-15 (1985) · Zbl 0583.68058
[7] Chomicki, J.; Imielinski, T., Relational specifications of infinite query answers, Proc. ACM SIGMOD Internat. Conf. on Management of Data, 174-183 (1989)
[8] Dincbas, M.; Van Hentenryck, P.; Simonis, H.; Aggoun, A.; Graf, T.; Berthier, F., The Constraint logic programming language CHIP, Tokyo, Japan. Tokyo, Japan, Proc. 5th Generation Computer Systems (1988)
[9] Ferrante, J.; Geiser, J. R., An efficient decision procedure for the theory of rational order, Theoret. Comput. Sci., 4, 227-233 (1977) · Zbl 0372.02024
[10] Ferrante, J.; Rackoff, C. W., The Computational Complexity of Logical Theories (1979), Springer: Springer Berlin · Zbl 0404.03028
[11] R. Hull and J. Su, Domain independence and the relational calculus. Tech. Report 88-64, University of Southern California; Acta Inform., submitted.; R. Hull and J. Su, Domain independence and the relational calculus. Tech. Report 88-64, University of Southern California; Acta Inform., submitted. · Zbl 0818.68067
[12] Immerman, N., Relational queries computable in polynomial time, Inform. and Control, 68, 86-104 (1986) · Zbl 0612.68086
[13] Immerman, N., Nondeterministic space is closed under complement, SIAM J. Comput., 17, 935-938 (1988) · Zbl 0668.68056
[14] Jaffar, J.; Lassez, J. L., Constraint logic programming, Proc. 14th ACM Symp. Principles of Programming Languages, 111-119 (1987)
[15] Kabanza, F.; Stevenne, J. M.; Wolper, P., Handling infinite temporal data, Proc. 9th ACM Symp. on Principles of Database Systems, 392-403 (1990) · Zbl 0831.68034
[16] Kanellakis, P. C., Elements of relational Database theory, (van Leeuwen, J.; Meyer, A. R.; Nivat, N.; Paterson, M. S.; Perrin, D., Handbook of Theoretical Computer Science, Vol. B (1990), North-Holland: North-Holland Amsterdam), Chapter 17 · Zbl 0900.68090
[17] Kanellakis, P. C.; Kuper, G. M.; Revesz, P. Z., Constraint query languages, Proc. 9th ACM Symp. on Principles of Database Systems, 299-313 (1990)
[18] Kanellakis, P. C.; Revesz, P. Z., On the relationship of congruence closure and unification, J. Symbolic Comput., 7, 427-444 (1989) · Zbl 0678.68041
[19] Kifer, M., On safety, domain independence, and capturability of database queries, Proc. Internat. Conf. on Databases and Knowledge Bases (1988)
[20] Kleene, S. C., General recursive functions on natural numbers, Math. Ann., 112, 727-742 (1936) · Zbl 0014.19402
[21] Kolaitis, P.; Papadimitriou, C. H., Why not negation by fixpoint?, Proc. 7th ACM Symp. on Principles of Database Systems, 231-239 (1988)
[22] Lewis, H. R.; Papadimitriou, C. H., Elements of the Theory of Computation (1981), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0464.68001
[23] Lloyd, J. W., Foundations of Logic Programming (1984), Springer: Springer Berlin · Zbl 0547.68005
[24] Moschovakis, Y. N., Elementary Induction on Abstract Structures (1974), North-Holland: North-Holland Amsterdam · Zbl 0307.02003
[25] Ramakrishnan, R., Magic templates: A spellbinding approach to logic programs, Proc. 5th Internat. Conf. on Logic Programming, 141-159 (1988)
[26] Revesz, P. Z., A closed form for Datalog queries with integer order, Proc. 3rd Internat. Conf. on Database Theory, 187-201 (1990) · Zbl 0789.68042
[27] Szelepcsènyi, R., The method of forced enumeration for nondeterministic automata, Acta Inform., 26, 279-284 (1988) · Zbl 0638.68046
[28] Ullman, J. D., Principles of Database Systems (1982), Computer Science press: Computer Science press Rockville, MD · Zbl 0558.68078
[29] Ullman, J. D.; Van Gelder, A., Parallel complexity of logical query programs, Algorithmica, 3, 5-42 (1988) · Zbl 0646.68062
[30] Van Hentenryck, P., Constraint Satisfaction in Logic Programming (1989), MIT Press: MIT Press Cambridge
[31] Vardi, M. Y., The complexity of relational query languages, Proc. 14th ACM Symp. on Theory of Computing, 137-146 (1982)
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.