Polynomial time query processing in temporal deductive databases

ABSTRACT

We study conditions guaranteeing polynomial time computability of queries in temporal deductive databases. We show that if for a given set of temporal rules, the period of its least models is bounded from the above by a polynomial in the database size, then also the time to process yes-no queries (as well as to compute finite representations of all query answers) can be polynomially bounded. We present a bottom-up query processing algorithm BT that is guaranteed to terminate in polynomial time if the periods are polynomially bounded. Polynomial periodicity is our most general criterion, however it can not be directly applied. Therefore, we exhibit two weaker criteria, defining inflationary and I-periodic sets of temporal rules. We show that it can be decided whether a set of temporal rules is inflationary. I-periodicity is undecidable (as we show), but it can be closely approximated by a syntactic notion of multi-separability.

REFERENCES

• 1: M. Abadi and Z. Manna. Temporal Logic Programming. In IEEE Symposium on Logic Programming, pages 4-16, San Francisco, Ca., September 1987.
• 2: Serge Abiteboul , Victor Vianu, Procedural and declarative database update languages, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.240-250, March 1988, Austin, Texas, United States [doi>10.1145/308386.308448]
• 3: M. Baudinet, Temporal logic programming is complete and expressive, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.267-280, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75301]
• 4: A.K. Chandra and D. Harel. Computable Queries for Relational Databases. Journal of Computer and System Sciences, 21:156-178, 1980.
• 5: Jan Oskar Chomicki, Functional deductive databases: query processing in the presence of limited function symbols, Rutgers University, New Brunswick, NJ, 1990
• 6: Jan Chomicki , Tomasz Imieliński, Relational specifications of infinite query answers, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.174-183, June 1989, Portland, Oregon, United States
• 7: Jan Chomicki , Tomasz Imieliński, Temporal deductive databases and infinite objects, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.61-73, March 1988, Austin, Texas, United States [doi>10.1145/308386.308416]
• 8: H. Gaifman, Sagiv Y., H. Mairson, and M.Y. Vardi. Undeeidable Optimization Problems for Database Logic Programs. In IEEE Symposium on Logic in Computer Science, 1987.
• 9: T. Imielinski. Complexity of query processing in incomplete databases. Submitted.
• 10: Phokion G. Kolaitis , Christos H. Papadimitriou, Why not negation by fixpoint?, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.231-239, March 1988, Austin, Texas, United States [doi>10.1145/308386.308446]
• 11: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 12: D.A. Plaisted. Complete Problems in the First- Order Predicate Calculus. Journal of Computer and System Sciences, 29:8-35, 1984.
• 13: R. Reiter. Towards a Logical Reconstruction of Relational Database Theory. In M.L. Brodie, J. Mylopoulos, and J.W. Schmidt, editors, On Conceptual Modeling, pages 191-233, Springer-Verlag, 1984.
• 14: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 15: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 16: M. H. Van Emden , R. A. Kowalski, The Semantics of Predicate Logic as a Programming Language, Journal of the ACM (JACM), v.23 n.4, p.733-742, Oct. 1976 [doi>10.1145/321978.321991]
• 17: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Design