Finite representation of infinite query answers

ABSTRACT

We define here a formal notion of finite representation of infinite query answers in logic programs. We apply this notion to DatalognS programs may be infinite and consequently queries may have infinite answers. We present a method to finitely represent infinite least Herbrand models of DatalognS program (and its underlying computational engine) can be forgotten. Given a query to be evaluated, it is easy to obtain from the relational specification finitely many answer substitutions that represent infinitely many answer substitutions to the query. The method involved is a combination of a simple, unificationless, computational mechanism (graph traversal, congruence closure, or term rewriting) and standard relational query evaluation methods. Second, a relational specification is effectively computable and its computation is no harder, in the sense of the complexity class, than answering yes-no queries. Our method is applicable to every range-restricted DatalognS program. We also show that for some very simple non-DatalognS logic programs, finite representations of query answers do not exist.

REFERENCES

• 1: L. Aiello , C. Cecchi, Adding a closure operator to the extended relational algebra: a further step towards the integration of database techniques and logic programming, Foundations of knowledge base management, Springer-Verlag New York, Inc., New York, NY, 1989
• 2: M. Abadi , Z. Manna, Temporal logic programming, Journal of Symbolic Computation, v.8 n.3, p.277-295, Sep. 1989 [doi>10.1016/S0747-7171(89)80070-7]
• 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: BAUDINET, M. On the expressiveness of temporal logic programming. Submitted, Sept. 1991.
• 5: BEZEM, M. Characterizing termination of logic programs with level mappings. In North American Conference on Logic Programming (1989).
• 6: B~Am, H.A. Decidabihty in the Herbrand base. In Workshop on Foundations of Deductive Databases and Logic Programming (Washington, D.C., 1986). Manuscript.
• 7: Marianne Baudinet , Marc Niézette , Pierre Wolper, On the representation of infinite temporal data and queries (extended abstract), Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.280-290, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113439]
• 8: Francois Bancilhon , Raghu Ramakrishnan, An amateur's introduction to recursive query processing strategies, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.16-52, May 28-30, 1986, Washington, D.C., United States
• 9: CHOLVY~ L, AND DEMOLOMBE, R. Querying a rule base. In Expert Database Systems. L. Kerschberg, Ed. Benjamin Cummings, 1987, 477-485.
• 10: CttANDRA, A. K., AND HAREL, D. Computable queries for relational databases. J. Comput. Syst. Sct. 21 (1980), 156-178.
• 11: CHANDRA, A. K., AND HAREL, D. Horn clause queries and generalizations. J. Logic Programm. 2, i (Apr. 1985). i 16.
• 12: Hong Chen , Jieh Hsiang, Logic programming with recurrence domains, Proceedings of the 18th international colloquium on Automata, languages and programming, p.20-34, June 1991, Madrid, Spain
• 13: CHOMICKI, J. A decidable class of logic programs with function symbols. Tech. Rep. TR-CS- 90-11, Dept. of Computing and Information Sciences, Kansas State Univ., Sept. 1990, 44 pp.
• 14: Jan Oskar Chomicki, Functional deductive databases: query processing in the presence of limited function symbols, Rutgers University, New Brunswick, NJ, 1990
• 15: Jan Chomicki, Polynomial time query processing in temporal deductive databases, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.379-391, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298589]
• 16: 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]
• 17: 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
• 18: CORELLA, F. Semantic retrieval and levels of abstraction. In Expert Database Syst., L. Kerschberg, Ed. Benjamin Cummings, 1987, 477 485.
• 19: Peter J. Downey , Ravi Sethi , Robert Endre Tarjan, Variations on the Common Subexpression Problem, Journal of the ACM (JACM), v.27 n.4, p.758-771, Oct. 1980 [doi>10.1145/322217.322228]
• 20: ENDERTON, H.B. A Mathematzcal Introduction to Logic. Academic Press, New York, 1972.
• 21: FR{IHWlRTH, T., SHAPIRO, E., VARDI, M. Y., AND YARDENI, E. Logic programs as types for logic programs. In IEEE Symposium on Logic in Computer Science (1991).
• 22: Ff~RER, M. Alternation and the Ackermann case of the decision problem. L'Enseignement Mathemattque, 1981.
• 23: GREEN, C. Application of theorem proving to problem solving. In Internattonal Joint Conference on Artificial Intelltgence (1969).
• 24: GI~CSEG, F., AND STEINB~, M. Tree Automata. Akad6miai Kiad6, Budapest, 1984.
• 25: HEINTZE, N., AND JAFFAR, J. A decismn procedure for a class of set constraints. In IEEE Sympostum on Logic m Computer Science (1990).
• 26: Nevin Heintze , Joxan Jaffar, A finite presentation theorem for approximating logic programs, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.197-209, December 1989, San Francisco, California, United States [doi>10.1145/96709.96729]
• 27: IMIELII(ISKI, T. Domain abstractmn and limited reasoning. In Internattonal Joint Conference on Artificial Intelligence (1987).
• 28: Tomasz Imeilinski, Intelligent query answering in rule based systems, Journal of Logic Programming, v.4 n.3, p.229-257, Sept. 1987 [doi>10.1016/0743-1066(87)90003-3]
• 29: J. Jaffar , J.-L. Lassez, Constraint logic programming, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.111-119, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41635]
• 30: Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages (preliminary report), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.299-313, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298582]
• 31: Dexter Kozen, Complexity of finitely presented algebras, Proceedings of the ninth annual ACM symposium on Theory of computing, p.164-177, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803406]
• 32: Paris C. Kanellakis , Peter Z. Revesz, On the relationship of congruence closure, Advances in database programming languages, ACM Press, New York, NY, 1990 [doi>10.1145/101620.101622]
• 33: F. Kabanza , J.-M. Stevenne , P. Wolper, Handling infinite temporal data, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.392-403, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298590]
• 34: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 35: J A Makowsky, Why Horn formulas matter in computer science: initial structures and generic examples, Proc. of the international joint conference on theory and practice of software development (TAPSOFT) Berlin, March 25-29, 1985 on Mathematical foundations of software development, Vol. 1: Colloquium on trees in algebra and programming (CAAP'85), p.374-387, April 1985, Berlin, Germany
• 36: MONK, J.D. Mathematical Logic. Springer-Verlag, New York, 1976.
• 37: Greg Nelson , Derek C. Oppen, Fast Decision Procedures Based on Congruence Closure, Journal of the ACM (JACM), v.27 n.2, p.356-364, April 1980 [doi>10.1145/322186.322198]
• 38: Peter Padawitz, Computing in Horn clause theories, Springer-Verlag New York, Inc., New York, NY, 1988
• 39: PLAISTED, D.A. Complete problems in the first-order predicate calculus. J. Comput. Syst. Sct. 29 (1984), 8-35.
• 40: R. Ramakrishnan , F. Bancilhon , A. Silberschatz, Safety of recursive Horn clauses with infinite relations, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.328-339, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28694]
• 41: Peter Z. Revesz, A closed form for Datalog queries with integer order (preliminary version), Proceedings of the third international conference on database theory on Database theory, p.187-201, November 1990, Paris, France
• 42: J. C. Shepherdson, Negation in logic programming, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 43: SHUM, C.-D., AND MUNTZ, R. Implicit representation for extensional answers. In International Conference on Expert Database Systems, L. Kerschberg, Ed. (Tysons Corner, Va., April 1988), 257-273.
• 44: TARNLUND, S.A. Horn clause computability. BIT 17, 2 (1977), 215-226.
• 45: Wolfgang Thomas, Automata on infinite objects, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 46: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 47: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 48: 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]
• 49: 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]
• 50: WAND, M. Final algebra semantics and data type extensions. J. Comput. Syst. Sct. 19 (1979), 27-44.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

          Nouns: Datalog

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Deduction (e.g., natural, rule-based)

General Terms:
Algorithms, Theory