Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-24T03:23:43.007Z Has data issue: false hasContentIssue false
  • English
  • Français

Top-down and Bottom-up Evaluation Procedurally Integrated

Published online by Cambridge University Press:  10 August 2018

DAVID S. WARREN
DAVID S. WARREN*
Affiliation:
Stony Brook University, Stony Brook, NY, 11794-4400USA (e-mail: [email protected]) XSB Inc., Setauket, NY, 11733USA (e-mail: [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

This paper describes how the Logic Programming System XSB combines top-down and bottom-up computation through the mechanisms of variant tabling and subsumptive tabling with abstraction, respectively.

It is well known that top-down evaluation of logical rules in Prolog has a procedural interpretation as recursive procedure invocation (Kowalski 1986). Tabling adds the intuition of short-circuiting redundant computations (Warren 1992). This paper shows how to introduce into tabled logic program evaluation a bottom-up component, whose procedural intuition is the initialization of a data structure, in which a relation is initially computed and filled, on first demand, and then used throughout the remainder of a larger computation for efficient lookup. This allows many Prolog programs to be expressed fully declaratively, programs which formerly required procedural features, such as assert, to be made efficient.

Keywords

top-downbottom-uplogic programmingtablingPrologprocedural interpretation
Type
Original Article
Information
Theory and Practice of Logic Programming , Volume 18 , Special Issue 3-4: 34th International Conference on Logic Programming , July 2018 , pp. 706 - 721
Copyright
Copyright © Cambridge University Press 2018 

References

Aref, M., ten Cate, B., Green, T. J., Kimelfeld, B., Olteanu, D., Pasalic, E., Veldhuizen, T. L., and Washburn, G. 2015. Design and implementation of the logicblox system. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. SIGMOD '15. ACM, New York, NY, USA, 1371–1382.Google Scholar
Arni, F., Ong, K., Tsur, S., Wang, H., and Zaniolo, C. 2003. The deductive database system L++. Theory and Practice of Logic Programming 3, 1 (Jan.), 61–94.Google Scholar
Bry, F. 1990. Query evaluation in deductive databases: Bottom-up and top-down reconciled. Data Knowledge Engineering 5, 289–312.Google Scholar
Cruz, F. and Rocha, R. 2011. Efficient instance retrieval of subgoals for subsumptive tabled evaluation of logic programs. CoRR abs/1107.5556.Google Scholar
Dowling, W. F. and Gallier, J. H. 1984. Linear-time algorithms for testing the satisfiability of propositional horn formulae. J. Log. Program. 1, 267–284.Google Scholar
Hermenegildo, M. V., Bueno, F., Carro, M., López-García, P., Mera, E., Morales, J. F., and Puebla, G. 2012. An overview of Ciao and its design philosophy. TPLP 12, 1–2, 219–252.Google Scholar
Johnson, E. 2000. Interfacing a tabled-wam engine to a tabling subsystem supporting both variant and subsumption checks. In 2nd Workshop on Tabulation in Parsing and Deduction. Vigo, Spain.Google Scholar
Johnson, E. 2002. A system supporting both variant- and subsumption-based tabled evaluations of logic programs. Ph.D. thesis, Stony Brook University, Stony Brook, NY, 11794-4400.Google Scholar
Johnson, E., Ramakrishnan, C. R., Ramakrishnan, I. V., and Rao, P. 1999. A space efficient engine for subsumption-based tabled evaluation of logic programs. In Functional and Logic Programming: 4th Fuji International Symposium, FLOPS'99 Tsukuba, Japan, November 11-13, 1999 Proceedings, Middeldorp, A. and Sato, T., Eds. Springer Berlin Heidelberg, Berlin, Heidelberg, 284–299.Google Scholar
Kowalski, R. 1986. Logic for Problem-solving. North-Holland Publishing Co., Amsterdam, The Netherlands, The Netherlands.Google Scholar
Lloyd, J. W. 1993. Foundations of Logic Programming, 2nd ed. Springer-Verlag New York, Inc., Secaucus, NJ, USA.Google Scholar
Ramakrishnan, I. V., Rao, P., Sagonas, K., Swift, T., and Warren, D. S. 1999. Efficient access mechanisms for tabled logic programs. Journal of Logic Programming 38, 1 (Jan), 31–54.Google Scholar
Ramakrishnan, R., Srivastava, D., Sudarshan, S., and Seshadri, P. 1994. The CORAL deductive system. VLDB J. 3, 2, 161–210.Google Scholar
Santos Costa, V., Rocha, R., and Damas, L. 2012. The YAP prolog system. TPLP 12, 1–2, 5–34.Google Scholar
Swift, T. and Warren, D. S. 2012. XSB: Extending Prolog with tabled logic programming. The Theory and Practice of Logic Programming 12, 1–2 (January), 157–187. (http://journals.cambridge.org/repo_A84WadE7).Google Scholar
Tekle, K. T. and Liu, Y. A. 2011. More efficient datalog queries: Subsumptive tabling beats magic sets. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data. SIGMOD '11. ACM, New York, NY, USA, 661–672.Google Scholar
Toman, D. 1995. Top-down beats bottom-up for constraint extensions of datalog. In In Proc. Intl. Logic Programming Symposium. MIT Press, 98–114.Google Scholar
Ullman, J. D. 1989. Bottom-up beats top-down for datalog. In Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. PODS '89. ACM, New York, NY, USA, 140–149.Google Scholar
Warren, D. S. 1992. Memoing for logic programs. CACM 35, 3 (Mar), 93–111.Google Scholar
Warren, D. S., Swift, T., and Sagonas, K. F. 2007. The XSB programmer's manual. Tech. rep., Department of Computer Science, State University of New York at Stony Brook, Stony Brook, New York, 11794-4400. Mar. The XSB System, current version 3.8.0, Nov 2017, is available from xsb.sourceforge.net, and the system and manual are continually updated.Google Scholar
Weilemaker, J., Frehwirth, T. and de Koninck, L. 2017. SWI-Prolog reference manual. Tech. rep. Tabling library available at http://www.swi-prolog.org/pldoc/man?section=tabling.Google Scholar
Zhou, N. 2012. The language features and architecture of B-Prolog. TPLP 12, 1–2, 189–218.Google Scholar