{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T08:13:40Z","timestamp":1760170420589,"version":"3.41.0"},"reference-count":38,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2008,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n\t  <jats:p>Recently there has been a growing interest in research in tabling in the logic programming community because of its usefulness in a variety of application domains including program analysis, parsing, deductive databases, theorem proving, model checking, and logic-based probabilistic learning. The main idea of tabling is to memorize the answers to some subgoals and use the answers to resolve subsequent variant subgoals. Early resolution mechanisms proposed for tabling such as OLDT and SLG rely on suspension and resumption of subgoals to compute fixpoints. Recently, the iterative approach named linear tabling has received considerable attention because of its simplicity, ease of implementation, and good space efficiency. Linear tabling is a framework from which different methods can be derived on the basis of the strategies used in handling looping subgoals. One decision concerns when answers are consumed and returned. This article describes two strategies, namely, <jats:italic>lazy<\/jats:italic> and <jats:italic>eager<\/jats:italic> strategies, and compares them both qualitatively and quantitatively. The results indicate that, while the lazy strategy has good locality and is well suited for finding all solutions, the eager strategy is comparable in speed with the lazy strategy and is well suited for programs with cuts. Linear tabling relies on depth-first iterative deepening rather than suspension to compute fixpoints. Each cluster of interdependent subgoals as represented by a topmost looping subgoal is iteratively evaluated until no subgoal in it can produce any new answers. Naive re-evaluation of all looping subgoals, albeit simple, may be computationally unacceptable. In this article, we also introduce semi-naive optimization, an effective technique employed in bottom-up evaluation of logic programs to avoid redundant joins of answers, into linear tabling. We give the conditions for the technique to be safe (i.e., sound and complete) and propose an optimization technique called <jats:italic>early answer promotion<\/jats:italic> to enhance its effectiveness. Benchmarking in B-Prolog demonstrates that with this optimization linear tabling compares favorably well in speed with the state-of-the-art implementation of SLG.<\/jats:p>","DOI":"10.1017\/s147106840700316x","type":"journal-article","created":{"date-parts":[[2007,8,6]],"date-time":"2007-08-06T14:19:20Z","timestamp":1186409960000},"page":"81-109","source":"Crossref","is-referenced-by-count":18,"title":["Linear tabling strategies and optimizations"],"prefix":"10.1017","volume":"8","author":[{"given":"NENG-FA","family":"ZHOU","sequence":"first","affiliation":[]},{"given":"TAISUKE","family":"SATO","sequence":"additional","affiliation":[]},{"given":"YI-DONG","family":"SHEN","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2008,1,1]]},"reference":[{"key":"S147106840700316X_manual_ref-30","volume-title":"Database and Knowledge-Base Systems","volume":"1 & 2","author":"Ullman","year":"1988"},{"key":"S147106840700316X_manual_ref-15","doi-asserted-by":"crossref","unstructured":"Nielson, F. , Nielson, H. R. , Sun, H. , Buchholtz, M. , Hansen, R. R. , Pilegaard, H. and Seidl, H. 2004. The succinct solver suite. In Proc. Tools and Algorithms for the Construction and Analysis of Systems: 10th International Conference (TACAS), LNCS 2988, 251\u2013265.","DOI":"10.1007\/978-3-540-24730-2_21"},{"key":"S147106840700316X_manual_ref-32","first-page":"93","article-title":"Memoing for logic programs","volume":"35","author":"Warren","year":"1992","journal-title":"Communications of the ACM, Special Section on Logic Programming"},{"key":"S147106840700316X_manual_ref-2","doi-asserted-by":"crossref","unstructured":"Bancilhon, F. and Ramakrishnan, R. 1986. An amateur's introduction to recursive query processing strategies. In Proc. of ACM SIGMOD '86, 16\u201352.","DOI":"10.1145\/16894.16859"},{"key":"S147106840700316X_manual_ref-6","doi-asserted-by":"crossref","unstructured":"Demoen, B. and Sagonas, K. 1999. CHAT: The copy-hybrid approach to tabling. In Proc. of Practical Aspects of Declarative Programming (PADL), LNCS 1551, 106\u2013121.","DOI":"10.1007\/3-540-49201-1_8"},{"key":"S147106840700316X_manual_ref-17","doi-asserted-by":"crossref","unstructured":"Przymusinski, T. C. 1989. Every logic program has a natural stratification and an iterated least fixed point model. In PODS '89: Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. ACM Press, New York, 11\u201321.","DOI":"10.1145\/73721.73723"},{"key":"S147106840700316X_manual_ref-35","doi-asserted-by":"crossref","unstructured":"Zhou, N.-F. and Sato, T. 2003. Efficient fixpoint computation in linear tabling. In Fifth ACM-SIGPLAN International Conference on Principles and Practice of Declarative Programming, 275\u2013283.","DOI":"10.1145\/888251.888277"},{"key":"S147106840700316X_manual_ref-25","doi-asserted-by":"crossref","unstructured":"Sato, T. and Kameya, Y. 2001. Parameter learning of logic programs for symbolic-statistical modeling. Journal of Artificial Intelligence Research, 391\u2013454.","DOI":"10.1613\/jair.912"},{"key":"S147106840700316X_manual_ref-31","unstructured":"Uratani, N. , Takezawa, T. , Matsuo, H. and Morita, C. 1994. ATR Integrated Speech and Language Database [Technical Report TR-IT-0056], ATR Interpreting Telecommunications Research Laboratories. In Japanese, ATR."},{"key":"S147106840700316X_manual_ref-23","doi-asserted-by":"publisher","DOI":"10.1145\/291889.291897"},{"key":"S147106840700316X_manual_ref-29","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-16492-8_66"},{"key":"S147106840700316X_manual_ref-16","unstructured":"Pientka, B. December 2003. Tabled Higher-order Logic Programming. PhD thesis, Technical Report CMU-CS-03-185, Carnegie Mellon University, Pittsburgh."},{"key":"S147106840700316X_manual_ref-1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-934613-40-8.50006-3"},{"key":"S147106840700316X_manual_ref-8","doi-asserted-by":"publisher","DOI":"10.3115\/1219044.1219076"},{"key":"S147106840700316X_manual_ref-7","unstructured":"Dietrich, S. W. 1987. Extension tables: Memo relations in logic programming. In IEEE Fourth Symposium on Logic Programming. 264\u2013272."},{"key":"S147106840700316X_manual_ref-37","doi-asserted-by":"crossref","unstructured":"Zhou, N.-F. , Shen, Y.-D. and Sato, T. 2004. Semi-naive evaluation in linear tabling. In Fifth ACM-SIGPLAN International Conference on Principles and Practice of Declarative Programming, 90\u201397.","DOI":"10.1145\/1013963.1013976"},{"key":"S147106840700316X_manual_ref-5","doi-asserted-by":"crossref","unstructured":"Demoen, B. and Sagonas, K. 1998. CAT: The copying approach to tabling. In Proc. of Programming Language Implementation and Logic Programming (PLILP), LNCS 1490, 21\u201335.","DOI":"10.1007\/BFb0056605"},{"key":"S147106840700316X_manual_ref-26","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068400001010"},{"key":"S147106840700316X_manual_ref-21","doi-asserted-by":"crossref","unstructured":"Rocha, R. , Silva, F. and Costa, V. S. 2005a. Dynamic mixed-strategy evaluation of tabled logic programs. In Proc. of International Conference on Logic Programming (ICLP), 250\u2013264.","DOI":"10.1007\/11562931_20"},{"key":"S147106840700316X_manual_ref-36","unstructured":"Zhou, N.-F. , Sato, T. and Hasida, K. 2003. Toward a high-performance system for symbolic and statistical modeling. In IJCAI Workshop on Learning Statistical Models from Relational Data, 153\u2013159."},{"key":"S147106840700316X_manual_ref-12","doi-asserted-by":"publisher","DOI":"10.1145\/311531.311533"},{"key":"S147106840700316X_manual_ref-19","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(98)10013-4"},{"key":"S147106840700316X_manual_ref-11","article-title":"Memoization of top down parsing","volume":"21","author":"Johnson","year":"1995","journal-title":"Computational Linguistics"},{"key":"S147106840700316X_manual_ref-28","unstructured":"Somogyi, Z. and Sagonas, K. in press. Tabling in mercury: Design and implementation. In Proc. of Practical Aspects of Declarative Programming (PADL) 15. Springer-Verlag, New York."},{"key":"S147106840700316X_manual_ref-22","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068404002030"},{"key":"S147106840700316X_manual_ref-9","unstructured":"Freire, J. , Swift, T. and Warren, D. S. 1998. Beyond depth-first: Improving tabled logic programs through alternative scheduling strategies. Journal of Functional and Logic Programming."},{"key":"S147106840700316X_manual_ref-33","unstructured":"Warren, D. S. 1999. Programming in Tabled Prolog [DRAFT 1]. url: http:\/\/www.cs.sunysb.edu\/warren\/xsbbook\/book.html. Accessed April 1, 2006."},{"key":"S147106840700316X_manual_ref-34","doi-asserted-by":"publisher","DOI":"10.1145\/236114.236120"},{"volume-title":"Foundation of Logic Programming","year":"1988","author":"Lloyd","key":"S147106840700316X_manual_ref-13"},{"key":"S147106840700316X_manual_ref-4","doi-asserted-by":"publisher","DOI":"10.1145\/249069.231399"},{"key":"S147106840700316X_manual_ref-10","doi-asserted-by":"crossref","unstructured":"Guo, H.-F. and Gupta, G. 2001. A simple scheme for implementing tabled logic of programming systems based on dynamic reordering of alternatives. In Proc. of International Conference on Logic Programming (ICLP), LNCS 2237, 181\u2013195.","DOI":"10.1007\/3-540-45635-X_20"},{"key":"S147106840700316X_manual_ref-18","unstructured":"Ramakrishnan, C. Feb. 2002. Model checking with tabled logic programming. In ALP News Letter. ALP."},{"key":"S147106840700316X_manual_ref-3","doi-asserted-by":"publisher","DOI":"10.1145\/227595.227597"},{"key":"S147106840700316X_manual_ref-24","first-page":"512","article-title":"XSB as a deductive database","volume":"23","author":"Sagonas","year":"1994","journal-title":"SIGMOD Record (ACM Special Interest Group on Management of Data)"},{"key":"S147106840700316X_manual_ref-38","doi-asserted-by":"crossref","unstructured":"Zhou, N.-F. , Shen, Y.-D. , Yuan, L.-Y. and You, J.-H. 2000. Implementation of a linear tabling mechanism. In Proc. of Practical Aspects of Declarative Programming (PADL), LNCS 1753, 109\u2013123.","DOI":"10.1007\/3-540-46584-7_8"},{"key":"S147106840700316X_manual_ref-14","doi-asserted-by":"publisher","DOI":"10.1038\/218019a0"},{"key":"S147106840700316X_manual_ref-27","doi-asserted-by":"crossref","unstructured":"Shen, Y.-D. , Yuan, L.-Y. , You, J.-H. and Zhou, N.-F. 1999. Linear tabulated resolutions for the well-founded semantics. In Proc. of Logic Programming and Nonmonotonic Reasoning, 192\u2013205.","DOI":"10.1007\/3-540-46767-X_14"},{"key":"S147106840700316X_manual_ref-20","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(94)00039-9"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S147106840700316X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T01:03:29Z","timestamp":1750467809000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S147106840700316X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,7]]}},"alternative-id":["S147106840700316X"],"URL":"https:\/\/doi.org\/10.1017\/s147106840700316x","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2008,1]]}}}