Abstract
Tabling has emerged as an important evaluation technique in logic programming. Currently, changes to a program (due to addition/deletion of rules/facts) after query evaluation compromise the completeness and soundness of the answers in the tables. This paper presents incremental algorithms for maintaining the freshness of tables upon addition or deletion of facts. Our algorithms improve on existing materialized view maintenance algorithms and can be easily extended to handle changes to rules as well. We describe an implementation of our algorithms in the XSB tabled logic programming system. Preliminary experimental results indicate that our incremental algorithms are efficient. Our implementation represents a first step towards building a practical system for incremental evaluation of tabled logic programs.
This research was supported in part by NSF grants EIA-9705998, CCR-9876242, IIS-0072927, CCR-0205376, CCR-0311512, and ONR grant N000140110967. We would like to thank Luis Castro for his extensive help with the implementation of our techniques in XSB.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bol, R., Degerstadt, L.: Tabulated resolution for well-founded semantics. In: ILPS (1993)
Chen, W., Swift, T., Warren, D.S.: Efficient implementation of general logical queries. J. Logic. Prog. (1995)
Chen, W., Warren, D.S.: Tabled evaluation with delaying for general logic programs. Journal of the ACM 43(1), 20–74 (1996)
Damas, L., Costa, V.S.: The YAP prolog system (2002), http://www.ncc.up.pt/~vsc/Yap/
Dawson, S., Ramakrishnan, C.R., Warren, D.S.: Practical program analysis using general purpose logic programming systems — a case study. In: PLDI (1996)
Gupta, A., Katiyar, D., Mumick, I.S.: Counting solutions to the view maintenance problem. In: Workshop on Deductive Databases, JICSLP, pp. 185–194 (1992)
Gupta, A., Mumick, I.S., Subrahmanian, V.S.: Maintaining views incrementally. In: Proceedings of ACM SIGMOD, pp. 157–166 (1993)
Gupta, A., Mumick, I.S.: Maintenance of materialized views: Problems, techniques, and appfications. IEEE Data Engineering Bulletin 18(2), 3–18 (1995)
Gupta, G., Guo, H.-F.: A simple scheme for implementing tabled logic programming systems based on dynamic reordering of alternatives. In: Codognet, P. (ed.) ICLP 2001. LNCS, vol. 2237, pp. 181–196. Springer, Heidelberg (2001)
Liu, Y., Stoller, S.: From Datalog rules to efficient programs with time and space guarantees. In: PPDP (2003)
Lu, J., Moerkotte, G., Schue, J., Subrahmanian, V.S.: Efficient maintenance of materialized mediated views. In: ACM SIGMOD, pp. 340–351 (1995)
Mayol, E., Teniente, E.: A survey of current methods for integrity constraint maintenance and view updating. In: ER 1999, pp. 62–73 (1999)
Paige, R., Koenig, S.: Finite differencing of computable expressions. ACM TOPLAS 4(3), 402–454 (1982)
Ramakrishnan, C.R., Ramakrishnan, I.V., Smolka, S.A., Dong, Y., Du, X., Roychoudhury, A., Venkatakrishnan, V.N.: XMC: A logic-programming-based verification toolset. In: Emerson, E.A., Sistla, A.P. (eds.) CAV 2000. LNCS, vol. 1855, pp. 576–580. Springer, Heidelberg (2000)
Ramakrishnan, V., Rao, P., Sagonas, K., Swift, T., Warren, D.S.: Efficient tabling mechanisms for logic programs. In: ICLP, pp. 697–711 (1995)
Seljee, R.R., de Swart, H.C.M.: Three types of redundancy in integrity checking; an optimal solution. Journal of Data and Knowledge Enigineering 30, 135–151 (1999)
Sokolsky, O.V., Smolka, S.A.: Incremental model checking in the modal mucalculus. In: Dill, D.L. (ed.) CAV 1994. LNCS, vol. 818, pp. 351–363. Springer, Heidelberg (1994)
Staudt, M., Jarke, M.: Incremental maintenance of externally materialized views. The VLDB Journal, 75–86 (1996)
Tamaki, H., Sato, T.: OLDT resolution with tabulation. In: ICLP, pp. 84–98 (1986)
XSB. The XSB logic programming system, Available from http://xsb.sourceforge.net
Yang, G., Kifer, M.: Flora: Implementing an efficient dood system using a tabling logic engine. In: Palamidessi, C., Moniz Pereira, L., Lloyd, J.W., Dahl, V., Furbach, U., Kerber, M., Lau, K.-K., Sagiv, Y., Stuckey, P.J. (eds.) CL 2000. LNCS (LNAI), vol. 1861, pp. 1078–1093. Springer, Heidelberg (2000)
Zhou, N.-F., Shen, Y.-D., Yuan, L.-Y., You, J.-H.: Implementation of a linear tabling mechanism. Journal of Functional and Logic Programming 2001(10) (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Saha, D., Ramakrishnan, C.R. (2003). Incremental Evaluation of Tabled Logic Programs. In: Palamidessi, C. (eds) Logic Programming. ICLP 2003. Lecture Notes in Computer Science, vol 2916. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24599-5_27
Download citation
DOI: https://doi.org/10.1007/978-3-540-24599-5_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20642-2
Online ISBN: 978-3-540-24599-5
eBook Packages: Springer Book Archive