Extending Query-Subquery Nets for Deductive Databases under the Well-Founded Semantics

ABSTRACT

We propose a method, called QSQN-WF, for evaluating queries to Datalog^¬ databases under the well-founded semantics. It is the first one that is set-at-a-time and strictly goal-directed w.r.t. SLS-resolution defined by Przymusinski. These properties are important for reducing accesses to the secondary storage and redundant computations. The first property distinguishes our method from the one based on SLG-resolution by Chen, Swift, and Warren (1995 Chen, W., T. Swift, and D. S. Warren. 1995. Efficient top-down computation of queries under the well-founded semantics. Journal of Logic Programming 24 (3):161–99. doi:10.1016/0743-1066(94)00028-5Crossref] , Google Scholar]) (which is tuple-at-a-time). The second property distinguishes our method from the ones based on the magic-sets transformation by Kemp, Srivastava, and Stuckey (1995 Kemp, D. B., D. Srivastava, and P. J. Stuckey. 1995. Bottom-up evaluation and query optimization of well-founded models. Theoretical Computer Science 146 (1 & 2):145–84. doi:10.1016/0304-3975(94)00153-aCrossref], Web of Science ®] , Google Scholar]) and Morishita (1996 Morishita, S. 1996. An extension of Van Gelder's alternating fixpoint to magic programs. Journal of Computer and System Sciences 52 (3):506–21. doi:10.1006/jcss.1996.0038Crossref], Web of Science ®] , Google Scholar]), which use magic atoms not in the most appropriate way and are not strictly goal-directed w.r.t. SLS-resolution. Our method follows SLS-resolution, with Van Gelder’s alternating fixpoint semantics on the background, but uses a query-subquery net to implement tabulation and the set-at-a-time technique, reduce redundant computations, and allow any control strategy within each iteration of the main loop. It is sound and complete w.r.t. the well-founded semantics and has PTIME data complexity.