Reformulation Algorithms for TGDs

Abstract

Let us rephrase the meta-algorithm for reformulating queries that we have referred to throughout the book, adding a bit more generality. It says we should:

• 1. Isolate a semantic property that any input query Q must have with respect to the target T and constraints Σ in order to have a reformulation of the desired type.

• 2. Express this property as a proof goal or entailment.

• 3. Search for a proof of the entailment within an appropriate proof system.

• 4. From the proof, extract a plan.

Up until now the last step was always performed through an appeal to an interpolation algorithm. We have shown that this algorithm can be applied to yield optimal worst-case complexity for many reformulation problems—for example, Proposition 2.20 shows that the algorithm achieves this for reformulating over conjunctive query views. Still, there are disadvantages to the use of interpolation. First, since the algorithm goes through first-order logic, it is difficult to get a good grasp on what kinds of plans or reformulations are produced, even in the restricted cases of greatest interest to databases. Secondly, safety of reformulations was not enforced automatically by the algorithms, although in the vocabulary-based setting it could be assured via post-processing (see Section 2.6). Our access-related algorithms were only presented for boolean queries, with the non-boolean case relying on post-processing. We can lift these restrictions in the case of TGD constraints.