Tabled evaluation with delaying for general logic programs

ABSTRACT

SLD resolution with negation as finite failure (SLDNF) reflects the procedural interpretation of predicate calculus as a programming language and forms the computational basis for Prolog systems. Despite its advantages for stack-based memory management, SLDNF is often not appropriate for query evaluation for three reasons: (a) it may not terminate due to infinite positive recursion; (b) it may be terminate due to infinite recursion through negation; and (c) it may repeatedly evaluate the same literal in a rule body, leading to unacceptable performance. We address all three problems for goal-oriented query evaluation of general logic programs by presenting tabled evaluation with delaying, called SLG resolution. It has three distinctive features: (i) SLG resolution is a partial deduction procedure, consisting of seven fundamental transformations. A query is transformed step by step into a set of answers. The use of transformations separates logical issues of query evaluation from procedural ones. SLG allows an arbitrary computation rule for selecting a literal from a rule body and an arbitrary control strategy for selecting transformations to apply. (ii) SLG resolution is sound and search space complete with respect to the well-founded partial model for all non-floundering queries, and preserves all three-valued stable models. To evaluate a query under differenc three-valued stable models, SLG resolution can be enhanced by further processing of the answers of subgoals relevant to a query. (iii) SLG resolution avoids both positive and negative loops and always terminates for programs with the bounded-term-size property. It has a polynomial time data complexity for well-founded negation of function-free programs. Through a delaying mechanism for handling ground negative literals involved in loops, SLG resolution avoids the repetition of any of its derivation steps. Restricted forms of SLG resolution are identified for definite, locally stratified, and modularly stratified programs, shedding light on the role each transformation plays.

REFERENCES

• 1: K. R. Apt , H. A. Blair , A. Walker, Towards a theory of declarative knowledge, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 2: Krzysztof R. Apt , M. H. van Emden, Contributions to the Theory of Logic Programming, Journal of the ACM (JACM), v.29 n.3, p.841-862, July 1982 [doi>10.1145/322326.322339]
• 3: I. Balbin , G. S. Port , K. Ramamohanarao , K. Meenakshi, Efficient bottom-up computation of queries on stratified databases, Journal of Logic Programming, v.11 n.3-4, p.295-344, Oct./Nov. 1991 [doi>10.1016/0743-1066(91)90030-S]
• 4: Francois Bancilhon , David Maier , Yehoshua Sagiv , Jeffrey D Ullman, Magic sets and other strange ways to implement logic programs (extended abstract), Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.1-15, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15399]
• 5: C. Beeri , R. Ramakrishnan, On the power of magic, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.269-284, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28689]
• 6: N. Bidoit , P. Legay, WELL!: an evaluation procedure for all logic programs, Proceedings of the third international conference on database theory on Database theory, p.335-348, November 1990, Paris, France
• 7: Roland Bol , Lars Degerstedt, Tabulated resolution for well founded semantics, Proceedings of the 1993 international symposium on Logic programming, p.199-219, December 1993, Vancouver, British Columbia, Canada
• 8: F. Bry, Query evaluation in recursive databases: bottom-up and top-down reconciled, Data & Knowledge Engineering, v.5 n.4, p.289-312, Oct. 1990 [doi>10.1016/0169-023X(90)90017-8]
• 9: CHAN, D. 1988. Constructive negation based on the completed database. In Proceedings of the 5th International Conference and Symposium on Logic Programming. Robert A. Kowalski and Kenneth A. Bowen, eds., MIT Press, Cambridge, Mass., pp. 111-125.
• 10: EllEN, W., AND ADAMS, L. 1994. Constructive negation of general logic programs. Tech. Rep. 94-CSE-16, Department of Computer Science and Engineering, Southern Methodist Univ., Dallas, Tex.
• 11: ellEN, W., SWIFT, T., AND WARREN, D.S. 1995. Efficient top-down computation of queries under the well-founded semantics. J. Logic Prog. 24, 3, 161-199.
• 12: Weidong Chen , David Scott Warren, Computation of Stable Models and Its Integration with Logical Query Processing, IEEE Transactions on Knowledge and Data Engineering, v.8 n.5, p.742-757, October 1996 [doi>10.1109/69.542027]
• 13: ellEN, W., AND WARREN, D.S. 1993. The SLG System. Southern Methodist Univ., Dallas, Tex., August. Available by anonymous FTP from seas.smu.edu or cs.sunysb.edu.
• 14: CHEN, W., AND WARREN, D.S. 1992. A goal-oriented approach to computing well founded semantics. In Proceedings of the Joint International Conference and Symposium on Logic Programming. MIT Press, Cambridge, Mass., pp. 589-603.
• 15: CLARK, K.L. 1978. Negation as failure. In Logic and Databases. H. Gailaire and J. Minker, eds. Plenum, New York, pp. 293-322.
• 16: DIETRICH, S. W. AND WARREN, D.S. 1986. Extension tables: Memo relations in logic programming. Teeh. Rep. 86/18. Dept. Computer Science, SUNY at Stony Brook, Stony Brook, N.Y.
• 17: GELFOND, M., AND LIFSCHITZ, V. 1988. The stable model semantics for logic programming. In Proceedings of the Joint International Conference and Symposium on Logic Programming. R. A. Kowalski and IC A. Bowen, eds. MIT Press, Cambridge, Mass., pp. 1070-1080.
• 18: KEMP, D. B., STUCKEY, P. J., AND SRIVASTAVA, D. 1991. Magic sets and bottom-up evaluation of well-founded models. In Proceedings of the International Logic Programming Symposium. MIT Press, Cambridge, Mass., pp. 337-351.
• 19: KEMP, D. B., STUCKEY, P. J., AND SRIVASTAVA, D. 1992. Query restricted bottom-up evaluation of normal logic programs. In Proceedings of the Joint International Conference and Symposium on Logic Programming. MIT Press, Cambridge, Mass., pp. 288-302.
• 20: KEMP, D. B., AND TOPOR, R.W. 1988. Completeness of a top-down query evaluation procedure for stratified databases. In Proceedings of the Joint International Conference and Symposium on Logic Programming. MIT Press, Cambridge, Mass., pp. 178-194.
• 21: KOMOROWSKt, J. 1990. Towards a programming methodology founded on partial deduction. In Proceedings of the European Conference on Artificial Intelligence.
• 22: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 23: J. W. Lloyd , J. C. Shepherdson, Partial evaluation in logic programming, Journal of Logic Programming, v.11 n.3-4, p.217-242, Oct./Nov. 1991 [doi>10.1016/0743-1066(91)90027-M]
• 24: Wiktor Marek , Mirosław Truszczyński, Autoepistemic logic, Journal of the ACM (JACM), v.38 n.3, p.587-618, July 1991 [doi>10.1145/116825.116836]
• 25: Alberto Martelli , Ugo Montanari, An Efficient Unification Algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.2, p.258-282, April 1982 [doi>10.1145/357162.357169]
• 26: MORISHITA, S. 1992. An alternating fixpoint tailored to magic programs. In Proceedings of the Deductive Database Workshop at Joint International Conference and Symposium on Logic Programming.
• 27: PRZYMUSINSKA, H. AND PRZYMUSINSKI, T.C. 1988. Weakly perfect model semantics for logic programs. In Proceedings of the Joint International Conference and Symposium on Logic Programming, R. A. Kowalski and K. A. Bowen, eds. MIT Press, Cambridge, Mass., pp. 1106-1120.
• 28: T. C. Przymusinski, On the declarative semantics of deductive databases and logic programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 29: T. C. Przymusinski, Every logic program has a natural stratification and an iterated least fixed point model, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.11-21, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73723]
• 30: PRZYMUS1NSKI, T.C. 1989b. On constructive negation in logic programming. In Proceedings of the North American Conference on Logic Programming (Oct.). MIT Press, Cambridge, Mass.
• 31: T. C. Przymusinski, On the declarative and procedual semantics of logic programs, Journal of Automated Reasoning, v.5 n.2, p.167-205, June 1989
• 32: Teodor Przymusinski, Well-founded semantics coincides with three-valued stable semantics, Fundamenta Informaticae, v.13 n.4, p.445-463, Dec. 1990
• 33: Raghu Ramakrishnan, Magic templates: a spellbinding approach to logic programs, Journal of Logic Programming, v.11 n.3-4, p.189-216, Oct./Nov. 1991 [doi>10.1016/0743-1066(91)90026-L]
• 34: RAMAKRISHNAN, R., SRIVASTAVA, D., AND SUDARSHAN, S. 1992. Controlling the search in bottom-up evaluation. In Proceedings of the Joint International Conference and Symposium on Logw Programming. MIT Press, Cambridge, Mass., pp. 273-287.
• 35: R. Ramesh , Weidong Chen, A portable method for integrating SLG resolution into prolog systems, Proceedings of the 1994 International Symposium on Logic programming, p.618-632, November 1994, Symposia, Melbourne
• 36: K. A. Ross, A procedural semantics for well founded negation in logic programs, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.22-33, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73724]
• 37: Kenneth Andrew Ross, The semantics of deductive databases, Stanford University, Stanford, CA, 1992
• 38: Konstantinos Sagonas , Terrance Swift , David S. Warren, XSB as an efficient deductive database engine, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.442-453, May 24-27, 1994, Minneapolis, Minnesota, United States
• 39: H. Seki, On the power of Alexander templates, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.150-159, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73737]
• 40: SEKI, H., AND ITOH, H. 1988. A query evaluation method for stratified programs under the extended CWA. in Proceedings of the Joint International Conference and Symposium on Logic Programming. MIT Press, Cambridge, Mass., pp. 195-211.
• 41: STUCKEY, P.J. 1991. Constructive negation in constraint logic programming. In Proceedings of the 6th IEEE Annual Symposium on Logic in Computer Science. IEEE, New York, 328-339.
• 42: Peter J. Stuckey , S. Sudarshan, Well-Founded Ordered Search (Extended Abstract), Proceedings of the 13th Conference on Foundations of Software Technology and Theoretical Computer Science, p.161-172, December 15-17, 1993
• 43: Hisao Tamaki , Taisuke Sato, OLD resolution with tabulation, Proceedings on Third international conference on logic programming, p.84-98, September 1986, London, United Kingdom
• 44: 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]
• 45: A. V. Gelder, Negation as failure using tight derivations for general logic programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 46: Allen Van Gelder , Kenneth A. Ross , John S. Schlipf, The well-founded semantics for general logic programs, Journal of the ACM (JACM), v.38 n.3, p.619-649, July 1991 [doi>10.1145/116825.116838]
• 47: 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]
• 48: VIEILLE, L. 1987. A database-complete proof procedure based upon SLD-resolution. In Proceedings of the International Conference on Logic Programming. MIT Press, Cambridge, Mass., pp. 74-103.
• 49: L. Vielle, Recursive query processing: the power of logic, Theoretical Computer Science, v.69 n.1, p.1-53, Dec. 5, 1989 [doi>10.1016/0304-3975(89)90088-1]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Languages, Theory

Keywords:
program transformations, stable models, tabled evaluation, well-founded models