On the (Completeness of) QSQR Datalog Query Evaluation Algorithm

Qery-Subquery (QSQ) refers to a family of top-down datalog query evaluation techniques. This family includes both iterative and recursive algorithms each of which can be applied in a tuple-at-a-time (depth-first) or a set-at-a-time (breadth-first) fashion. QSQ is based on SLD-resolution but it is DB-complete, which it achieves using tabling.

Fix to the Algorithm as Presented in [AHV95]

The initial QSQ algorithm was query-subquery recursive (QSQR) presented in [Vie86]. This algorithm was later found to be incomplete and was corrected [Vie87, Nej87]. One of the most cited source on the QSQR algorithm is [AHV95], which presents the algorithm using the same setting as the one used to present magic sets in [BMSU86], including adornments and sideways information passing. Most recent works that use QSQR which we came across base their work on the description of the algorithm in [AHV95]. We claim that this description of QSQR is incomplete and propose a fix to this problem. To the best of our knowledge, we are the first to detect this incompleteness, which we communicated to the authors of [MBN08], resulting in a modification of their work, see http://www.mimuw.edu.pl/~nguyen/GQSQR-revised-long.pdf.

The counterexample used to show incompleteness is based on example 2 in [ZSY+00]. It was one of several examples used to test the correctness of my implementation of QSQR. After the implementation failed to return the correct answer, and after debugging both my implementation and understanding of QSQR, the issue mentioned above was discovered. (01.03.2011).

Elsewhere

  • Evaluating DATALOG Programs over Infinite and Founded Databases: This work revisits the weak safety and termination problems for recursive DATALOG programs evaluated over infinite databases. Based on the master’s thesis of Evelina Zarivach.
    [Thesis] | [Paper]

  • Distributed Query-Sub-Query Project (dQSQ): The purpsoe of this project is to develop a distributed algorithm based on Query-Sub-Query technique for optimization of Datalog queries in a peer-to-peer environment. Based on master’s thesis of Noam Pettel
    [Project website]

Definitions

  • A procedure for answering a query is database-complete (DB-complete) if, whenever there are finitely many answers to a query it terminates after returning all the answers [Vie87].

References

[AHV95] Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995.

[BMSU86] François Bancilhon, David Maier, Yehoshua Sagiv, and Jeffrey D. Ullman. Magic sets and other strange ways to implement logic programs. In PODS, 1986.

[MBN08] Ewa Madalinska-Bugaj and Linh Anh Nguyen. Generalizing the qsqr evaluation method for horn knowledge bases. In New Challenges in Applied Intelligence Technologies. 2008.

[Nej87] Wolfgang Nejdl. Recursive strategies for answering recursive queries - the RQA/FQI strategy. In VLDB, 1987.

[Vie86] Laurent Vieille. Recursive axioms in deductive databases: The query/subquery approach. In Expert Database Conf., 1986.

[Vie87] Laurent Vieille. A database-complete proof procedure based on sld resolution. In ICLP, 1987.

[ZSY+00] Neng-Fa Zhou, Yi-Dong Shen, Li-Yan Yuan, Jia-Huai You. Implementation of a Linear Tabling Mechanism. PADL, 2000.