Weidong Chen
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.
- APT, K. R., BLtdR, H., AND WnLr, ER, A. 1988. Towards a theory of declarative knowledge. In Foundations of Deductive Databases and Logic Programming, J. Minker, ed. Morgan-Kaufmann Publishers, Los Altos, CaliL Google Scholar
- APT, K. R., AND VAN EMDEN, M.H. 1982. Contributions to the theory of logic programming. J. ACM 29, 3 (July), 841-862. Google Scholar
- BALBIN, L, PORT, G. S., RAMAMOHANARAO, K., AND MEENAKSHI, K. 1991. Efficient bottom-up computation of queries on stratified databases. J. Logic Prog. 11, 295-344. Google Scholar
- BANCILHON, F., MAIER, D., SAGIV, Y., AND ULLMAN, J. 1986. Magic sets and other strange ways to implement logic programs. In Proceedings of the 5th Annual ACM SIGACT-SIGMOD Symposium on Principles of Database Systems (Cambridge, Mass., Mar. 24-26). ACM, New York, pp. 1-15. Google Scholar
- BEERI, C. AND RAMAKRISHNAN, R. 1987. On the power of magic. In Proceedings of the 6th Annual ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (San Diego, CaliL, Mar. 23-25). ACM, New York, pp. 269-283. Google Scholar
- BIDOIT, N., AND LEGAY, P. 1990. WELL!: An evaluation procedure for all logic programs. In Proceedings of the International Conference on Database Theory. Springer-Verlag, New York, pp. 335-348. Google Scholar
- BOL, R., AND DEGERSTEDT, L. 1993. Tabulated resolution for well-founded semantics. In Proceedings of the International Logic Programming Symposium. MIT Press, Cambridge, Mass., pp. 199-219. Google Scholar
- BRY, F. 1990. Query evaluation in recursive databases: Bottom-up and top-down reconciled. Data Knowl. Eng. 5, 4, 289-312. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- CHEN, W., AND WARREN, D.S. Computation of stable models and its integration with logical query processing. IEEE Trans. Knowl. Data Engin., to appear. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- CLARK, K.L. 1978. Negation as failure. In Logic and Databases. H. Gailaire and J. Minker, eds. Plenum, New York, pp. 293-322.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- KOMOROWSKt, J. 1990. Towards a programming methodology founded on partial deduction. In Proceedings of the European Conference on Artificial Intelligence.Google Scholar
- LLOYD, J.W. 1987. Foundations of Logic Programming, Springer-Verlag, New York. Google Scholar
- LLOYD, J. W. AND SHEPHERDSON, J.C. 1991. Partial evaluation in logic programming. J. Logic Prog. 11,217-242. Google Scholar
- MAREK, W., AND TRUSZCZYNSKI, M. 1991. Autoepistemic logic. J. ACM 38, 3, 588-619. Google Scholar
- MARTELLI, A., AND MONTANARI, U. 1982. An efficient unification algorithm. ACM Trans. Prog. Lang. Syst. 4, 2 (Apr.), 258-282. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- PRZYMUSINSKI, T. C. 1988. On the declarative semantics of deductive databases and logic programs. In Proceedings of the Foundations of Deductive Databases and Logic Programming, J. Minker, ed. Morgan-Kaufmann Publishers, Los Altos, Calif. Google Scholar
- PRZYMUSINSK1, T.C. 1989a. Every logic program has a natural stratification and an iterated least fixed point model. In Proceedings of the 8th ACM SIGACT-SIGMOD-SIGART Syrnposiurn on Principles of Database Systems (Philadelphia, Pa., Mar. 29-31). pp. 11-21. Google Scholar
- 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.Google Scholar
- PRZYMUSINSKI, T.C. 1989c. On the declarative and procedural semantics of logic programs. J. Automated Reas. 5, 167-205. Google Scholar
- PRZYMUS1NSK/, T.C. 1990. The well-founded semantics coincides with the three-valued stable semantics. Fund. Inf. 13, 445-463. Google Scholar
- RAMAKRISHNAN, R. 1991. Magic templates: A spellbinding approach to logic programs. J. Logic Prog. 11, 189-216. Google Scholar
- 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.Google Scholar
- RAMESH, R., AND CHEN, W. 1994. A portable method of integrating SLG resolution into prolog systems. In Proceedings of the International Logic Programming Symposium. MIT Pre~, Cambridge, Mass., pp. 618-682. Google Scholar
- Ross, K. A. 1989. A procedural semantics for well founded negation in logic programs, in Proceedings of the 8th Annual ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (Philadelphia, Pa., Mar. 29-31). ACM, New York, pp. 22-33. Google Scholar
- Ross, K.A. 1991. The semantics of deductive databases. Ph.D. dissertation. Department of Computer Science, Stanford University, August. Google Scholar
- SAGONAS, K., SWIFq', T., AND D. S. WARREN, D.S. 1994. XSB as an efficient deductive database engine. In Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data (Minneapolis, Minn., May 24-27). ACM, New York, pp. 442-453. Google Scholar
- SEKI, H. 1989. On the power of Alexander templates. In Proceedings of the 8th ACM SIGACT- SIGMOD-SIGART Symposium on Principles of Database Systems (Philadelphia, Pa., Mar. 29-31 ). ACM, New York, pp. 150-159. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- STUCKEY, P., AND SUDARSHAN, S. 1993. Well-founded ordered search. In Proceedings of the 13th Conference on Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science, vol. 761. Springer-Verlag, New York, pp. 161-171. Google Scholar
- TAMArd, H., AND SATO, T. 1986. OLD resolution with tabulation. In Proceedings of the International Conference on Logic Programming. MIT Press, Cambridge, Mass., pp. 84-98. Google Scholar
- VA~ EMDE~, M. H., AND KOWALSrd, R. A. 1976. The semantics of predicate logic as a programming language. J. ACM 23, 4 (Oct.), 733-741. Google Scholar
- VA~ GELDER, A. 1988. Negations as failure using tight derivations for general logic programs. In Proceedings of the Foundations of Deductive Databases and Logic Programming, J. Minker, ed. Morgan-Kaufmann Publishers, Los Altos, Calif. Google Scholar
- VAN GELDER, A., ROSS, K. A, AND SCHLIPF, J.S. 1991. The well-founded semantics for general logic programs. J. ACM 38, 3 (July), 620-650. Google Scholar
- VARDX, M. 1982. The complexity of relational query languages. In Proceedings of the 14th Annual ACM Symposium on Theory Computing (San Francisco, Calif., May 5-7). ACM, New York, 137-146. Google Scholar
- 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.Google Scholar
- VIEELLE, L 1989. Recursive query processing: The power of logic. Theoret. Comput. Sci. 69, 1-53. Google Scholar
Index Terms
- Tabled evaluation with delaying for general logic programs
Recommendations
Using clausal deductive databases for defining semantics in disjunctive deductive databases
This paper investigates the novel concept of i>clausal deductive databases (cd-databases), which are special normal deductive databases - i.e., deductive databases which may contain default negation in rule bodies - over a typed meta-language i>L...
Reducts of propositional theories, satisfiability relations, and generalizations of semantics of logic programs
Over the years, the stable-model semantics has gained a position of the correct (two-valued) interpretation of default negation in programs. However, for programs with aggregates (constraints), the stable-model semantics, in its broadly accepted ...
Reviews
Ralph Walter Wilkerson
SLG resolution, a new framework for query evaluation that may have significant influence on logic-based computational systems such as Prolog, is presented. The main results are that seven basic transformations are identified for query transformation; logical issues relevant to query evaluation can be separated from procedural issues; SLG resolution allows sharing of subgoals; and SLG resolution delays ground negative literals involved in a loop. The presentation is thorough. Both the practical and theoretical aspects of this method are exceptionally well covered.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments