{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T06:05:45Z","timestamp":1747548345908,"version":"3.32.0"},"reference-count":14,"publisher":"Wiley","issue":"7","license":[{"start":{"date-parts":[[2006,10,30]],"date-time":"2006-10-30T00:00:00Z","timestamp":1162166400000},"content-version":"vor","delay-in-days":5234,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Softw Pract Exp"],"published-print":{"date-parts":[[1992,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The ET* algorithm is a complete evaluation strategy for Datalog programs, which are logic programs without function symbols. The ET* algorithm uses extension tables and depth\u2010first iterative deepening to provide the evaluation of pure function\u2010free logic programs as declarative specifications. Extension tables are a memo facility that the algorithm uses both to cut infinite derivation paths for complete evaluation and to optimise the evaluation of logic programs.<\/jats:p><jats:p>The original implementation of the ET* algorithm incorporated extension tables as part of the Prolog database using the built\u2010in predicates assert and retract. The advantage of implementing the extension table using the Prolog database is the portability of the ET* algorithm. There are several disadvantages, however, with this approach. One disadvantage is the cost associated with the built\u2010in predicates assert and retract, which are known to be expensive operations in most current Prolog systems. Another disadvantage is the differences across implementations in the semantics that these built\u2010ins provide for dynamic predicates. This paper presents an efficient implementation of extension tables as a global data structure in Prolog, which includes a set of built\u2010in primitives for manipulating the extension table. The ET* algorithm is updated to reflect the utilisation of the global extension table data structure. The implementations of the ET* algorithm are compared using time and space performance on a variety of benchmark programs.<\/jats:p>","DOI":"10.1002\/spe.4380220706","type":"journal-article","created":{"date-parts":[[2006,11,17]],"date-time":"2006-11-17T19:52:22Z","timestamp":1163793142000},"page":"573-597","source":"Crossref","is-referenced-by-count":9,"title":["Extension table built\u2010ins for prolog"],"prefix":"10.1002","volume":"22","author":[{"given":"Changguan","family":"Fan","sequence":"first","affiliation":[]},{"given":"Suzanne Wagner","family":"Dietrich","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,30]]},"reference":[{"volume-title":"Introduction to Logic Programming","year":"1984","author":"Hogger C. J.","key":"e_1_2_1_2_2"},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","unstructured":"F.BancilhonandR.Ramakrishnan \u2018An amateur's introduction to recursive query processing strategies\u2019 SIGMOD ACM 1986 pp.1\u201315.","DOI":"10.1145\/16856.16859"},{"key":"e_1_2_1_4_2","unstructured":"S. W.Dietrich \u2018Extension tables: memo relations in logic programming\u2019 1987 Symposium on Logic Programming IEEE 1987 pp.264\u2013272."},{"volume-title":"SB\u2010Prolog: A User Manual","year":"1988","author":"Debray S. K.","key":"e_1_2_1_5_2"},{"key":"e_1_2_1_6_2","unstructured":"T. G.LindholmandR. A.O'Keefe \u2018Efficient implementation of a defensible semantics for dynamic prolog code\u2019 International Conference on Logic Programming 1987 pp.21\u201339."},{"key":"e_1_2_1_7_2","unstructured":"C.Fan \u2018Extension table primitives for prolog\u2019 Master's Thesis Arizona State University Tempe AZ 85287\u20135406 December1989."},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","unstructured":"S. W.Dietrich \u2018A performance comparison of top\u2010down recursive query evaluation strategies on datalog benchmarks\u2019 Hawaiian International Conference on System Sciences IEEE January1989 pp.621\u2013629.","DOI":"10.1109\/HICSS.1989.48041"},{"key":"e_1_2_1_9_2","unstructured":"B.Fagin \u2018Issues in caching prolog goals\u2019 Master's Thesis University of California Berkeley November1984."},{"volume-title":"The Art of Prolog","year":"1986","author":"Sterling L.","key":"e_1_2_1_10_2"},{"volume-title":"Principles of Database and Knowledge\u2010Base Systems, Volume 2: The New Technologies","year":"1989","author":"Ullman J. D.","key":"e_1_2_1_11_2"},{"key":"e_1_2_1_12_2","unstructured":"S. W.Dietrich \u2018Extension tables for recursive query evaluation\u2019 Ph.D. Thesis State University of New York at Stony Brook Stony Brook NY 11794 1987."},{"key":"e_1_2_1_13_2","unstructured":"S. K.Debray \u2018Register allocation in a prolog machine\u2019 1986 Symposium on Logic Programming IEEE 1986 pp.267\u2013275."},{"key":"e_1_2_1_14_2","first-page":"259","volume-title":"Implementations of Prolog","author":"Bruynooghe M.","year":"1984"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/356850.356854"}],"container-title":["Software: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fspe.4380220706","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/spe.4380220706","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T23:56:46Z","timestamp":1736639806000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/spe.4380220706"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,7]]},"references-count":14,"journal-issue":{"issue":"7","published-print":{"date-parts":[[1992,7]]}},"alternative-id":["10.1002\/spe.4380220706"],"URL":"https:\/\/doi.org\/10.1002\/spe.4380220706","archive":["Portico"],"relation":{},"ISSN":["0038-0644","1097-024X"],"issn-type":[{"type":"print","value":"0038-0644"},{"type":"electronic","value":"1097-024X"}],"subject":[],"published":{"date-parts":[[1992,7]]}}}