Reformulating Queries: Theory and Practice

Michael Benedikt, Egor V. Kostylev, Fabio Mogavero, Efthymia Tsamoura

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:

  1. Existence ($\exists$REF): Determining if any reformulation exists that is logically equivalent to the original query under the given background knowledge.
  2. 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).

Comparison of Reformulation Sizes: Optimized Huang vs. McMillan. Points below the diagonal indicate where Optimized Huang produced more succinct results.

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.

Summary of complexity results for the existence problem ($\exists$REF). Complexity ranges from P to Undecidable depending on the logic and vocabulary constraints.

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

Abstract

We consider a setting where a user wants to pose a query against a dataset where background knowledge, expressed as logical sentences, is available, but only a subset of the information can be used to answer the query. We thus want to reformulate the user query against the subvocabulary, arriving at a query equivalent to the user’s query assuming the background theory, but using only the restricted vocabulary. We consider two variations of the problem, one where we want any such reformulation and another where we restrict the size. We present a classification of the complexity of the problem, then provide algorithms for solving the problems in practice and evaluate their performance.
BibTeX
@inproceedings{benedikt2017reformulating,
  author = {Michael Benedikt and Egor V. Kostylev and Fabio Mogavero and Efthymia Tsamoura},
  title = {{Reformulating Queries: Theory and Practice}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/116},
}
Figure