Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-13T04:20:54.989Z Has data issue: false hasContentIssue false
  • English
  • Français

Incremental Tabling in Support of Knowledge Representation and Reasoning

Published online by Cambridge University Press:  21 July 2014

TERRANCE SWIFT
TERRANCE SWIFT*
Affiliation:
Coherent Knowledge Systems, Inc. and NOVALincs, Universidade Nova de Lisboa (e-mail: terranceswift@gmail.com)
Get access Rights & Permissions [Opens in a new window]

Abstract

Resolution-based Knowledge Representation and Reasoning (KRR) systems, such as Flora-2, Silk or Ergo, can scale to tens or hundreds of millions of facts, while supporting reasoning that includes Hilog, inheritance, defeasibility theories, and equality theories. These systems handle the termination and complexity issues that arise from the use of these features by a heavy use of tabled resolution. In fact, such systems table by default all rules defined by users, unless they are simple facts.

Performing dynamic updates within such systems is nearly impossible unless the tables themselves can be made to react to changes. Incremental tabling as first implemented in XSB (Saha 2006) partially addressed this problem, but the implementation was limited in scope and not always easy to use. In this paper, we introduce transparent incremental tabling which at the semantic level supports updates in the 3-valued well-founded semantics, while guaranteeing full consistency of all tabled queries. Transparent incremental tabling also has significant performance improvements over previous implementations, including lazy recomputation, and control over the dependency structures used to determine how tables are updated.

Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 14 , Special Issue 4-5: 30th International Conference on Logic Programming , July 2014 , pp. 553 - 567
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Chen, W. and Warren, D. S. 1996. Tabled Evaluation with Delaying for General Logic Programs. Journal of the ACM 43, 1, 20–74.Google Scholar
Grosof, B. and Swift, T. 2013. Radial restraint: A semantically clean approach to bounded rationality for logic programs. In Conference of the American Association for Artificial Intelligence.Google Scholar
Hermenegildo, M., Puebla, G., Marriott, K., and Stuckey, P. 2000. Incremental Analysis of Constraint Logic Programs. ACM TOPLAS 22, 2 (March), 187–223.Google Scholar
Hermenegildo, M. V., Bueno, F., Carro, M., López-Garciá, P., Mera, E., Morales, F., and Puebla, G. 2012. An overview of Ciao and its design philosophy. Theory and Practice of Logic Programming 12, 1-2, 219–252.Google Scholar
ISO working group JTC1/SC22. 1995. Prolog international standard ISO-IEC 13211-1. Tech. rep., International Standards Organization.Google Scholar
Lloyd, J. and Topor, R. 1984. Making Prolog more expressive. Journal of Logic Programming 1, 3, 225–240.Google Scholar
Naish, L. 2006. A three-valued semantics for logic programmers. Theory and Practice of Logic Programming 6, 5, 509–538.Google Scholar
Ramakrishnan, C., Ramakrishnan, I., and Warren, D. S. 2007. XcelLog: A deductive spreadsheet system. Knowledge Engineering Review 22, 3, 269–279.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, 31–55.Google Scholar
Reece, J., Urry, L., Cain, M., Wasserman, S., Minorsky, P., and Jackson, R. 2010. Campbell Biology. B. Cummings. 9th Edition.Google Scholar
Riguzzi, F. and Swift, T. 2013. Well–definedness and efficient inference for probabilistic logic programming under the distribution semantics. Theory and Practice of Logic Programming 13, 2, 279–302.Google Scholar
Sagonas, K. and Swift, T. 1998. An abstract machine for tabled execution of fixed-order stratified logic programs. ACM TOPLAS 20, 3 (May), 586–635.Google Scholar
Sagonas, K., Swift, T., and Warren, D. S. 2000. An abstract machine for efficiently computing queries to well-founded models. Journal of Logic Programming 45, 1–3, 1–41.Google Scholar
Saha, D. 2006. Incremental evaluation of tabled logic programs. Ph.D. thesis, SUNY Stony Brook.Google Scholar
Saha, D. and Ramakrishnan, C. 2005. Incemental and demand-driven points-to analysis using logic programming. In Principles and Practice of Declarative Programming. 117–128.Google Scholar
Santos Costa, V., Damas, L., and Rocha, R. 2012. The YAP prolog system. Theory and Practice of Logic Programming 12, 1-2, 5–34.Google Scholar
Swift, T. and Warren, D. 2012. XSB: Extending the power of Prolog using tabling. Theory and Practice of Logic Programming 12, 1-2, 157–187.Google Scholar
Yang, G., Kifer, M., Wan, H., and Zhao, C. 2013. FLORA-2: User's Manual Version 0.99.3. http://flora.sourceforge.net.Google Scholar
Zhou, N. and Have, C. 2012. Efficient tabling of structured data with enhanced hash-consing. Theory and Practice of Logic Programming 12, 4-5, 547–563.Google Scholar
Supplementary material: PDF

SWIFT

Incremental Tabling in Support of Knowledge Representation and Reasoning

Download SWIFT(PDF)
PDF 132.5 KB