Introduction
Query reformulation is a fundamental challenge in database systems and knowledge representation. It involves rewriting a query to use only a restricted "interface" vocabulary, typically necessitated by access constraints or schema mappings. While well-understood for simple Horn rules, the problem becomes significantly more complex when background theories incorporate disjunction and negation. This paper presents the first comprehensive study of query reformulation in these expressive logics, establishing tight complexity bounds and developing optimized algorithms that outperform standard approaches.
Problem Definition
The research focuses on two primary problems:
- Existence ($\exists$REF): Determining if any reformulation exists that is logically equivalent to the original query under the given background knowledge.
- Size-Restricted (REF$\le$): Determining if a reformulation exists within a specific size limit $k$.
In disjunctive theories, the target language's expressiveness is crucial; a reformulation that exists as a complex union of queries might not exist as a single simple query, making disjunction in the target language essential.
Algorithmic Approaches
The authors bridge the gap between theory and practice through several key strategies:
Interpolation-based Reformulation
Leveraging the Craig Interpolation theorem, the authors demonstrate that if a query $Q$ is equivalent to some $Q'$ over a sub-vocabulary $V$, then $Q'$ can be derived from a formal proof of that equivalence. They implemented several interpolation algorithms, including Huang, McMillan, and Bonacina-Johansson, integrated with state-of-the-art theorem provers like MathSat and E.
Optimized Huang Algorithm
A significant contribution is the "Optimized Huang" algorithm. Standard interpolation often fails to preserve monotonicity—the property that adding data should not remove answers. The optimized version ensures the resulting reformulation is a Lyndon interpolant, which is vital for producing high-quality, monotone queries.
Disjunctive Chase
For propositional cases, the authors utilized the DLV system to explore minimal models of the theory, constructing reformulations in Disjunctive Normal Form (DNF).
Experimental Evaluation
To evaluate these methods, the authors developed a custom generator for reformulation problems, as no standard benchmark existed. They conducted over 3,600 runs across six classes of reformulations (CNF, DNF, and various AND/OR alternations).
The practical results indicated that MathSat-based interpolation was the fastest, often resolving in milliseconds. Furthermore, the Optimized Huang algorithm generally produced smaller, more succinct reformulations compared to the McMillan algorithm, although McMillan proved more robust for very complex proofs.
Results and Insights
The study provides a detailed map of the complexity landscape for various background theories, such as Tuple-Generating Dependencies (TGDs) and weakly-acyclic TGDs.
Key insights include:
- Complexity Gap: Checking for existence is often comparable to standard logical entailment, but adding a size constraint significantly increases complexity, often moving up a level in the polynomial hierarchy.
- Interpolation vs. Black Box: Extracting interpolants from resolution proofs (using MathSat or E) proved more effective than using the native interpolation features of general-purpose provers like Vampire.
Conclusion
This work establishes a robust theoretical and practical foundation for query reformulation in expressive logics. Future research may focus on "interpolant-driven theorem-proving," where a prover's search heuristics are guided by the quality and size of partial interpolants generated during the proof process, potentially overcoming current bottlenecks in proof detail.
Summary updated