💻 computer science

Interpolation and Query Rewriting

This paper overviews applications of Craig interpolation and Beth definability to simplifying logical expressions and database queries, offering new perspectives on effective algorithms, connections to model-theoretic preservation theorems, and the development of interpolation forms tailored to database interests.

Original authors: Michael Benedikt

Published 2026-06-16

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Michael Benedikt

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery, but you have a very specific set of rules about how you can gather information. You have a big question (a Query) you want answered, but the data you need is locked behind different doors, some of which have strict entry requirements.

This paper is a guidebook for a special kind of detective work. It explains how to take a big, complex question and translate it into a step-by-step plan that only uses the specific doors and keys you are allowed to use. The magic tool that makes this translation possible is called Interpolation.

Here is the breakdown of the paper's ideas using everyday analogies:

1. The Big Picture: Translating Questions

In the world of databases, we often have a "Source" (the raw data) and a "Target" (what the user sees or what tools are available).

The Problem: You ask a question like, "Who are all the professors named Smith?" But the database doesn't let you just look at the whole list of professors. Maybe you can only look up a professor if you already know their ID number, or maybe you can only see a list of names if you first check a different directory.
The Goal: The paper wants to know: Can we rewrite your big question into a smaller, step-by-step plan that works within these strict rules? If yes, how do we find that plan automatically?

2. The Magic Tool: Craig Interpolation

Think of Interpolation as a "translator" that sits between two languages.

Language A: Your original big question (which might use forbidden words or concepts).
Language B: The restricted vocabulary you are allowed to use (only specific tables, only specific access methods).
The Interpolant: This is the "middle ground" sentence. It is a new sentence that:
1. Is true whenever your original question is true.
2. Only uses the words allowed in the restricted vocabulary.
3. Is strong enough to prove your original question.

The paper argues that if you can prove your question is "determined" (meaning the answer depends only on the data you can access), then this "translator" (Interpolation) can always find a valid plan for you.

3. The Three Main Scenarios

The paper explores three different ways the "doors" to the data might be locked:

A. The "Vocabulary" Lock (Subvocabulary)

The Analogy: Imagine you are writing a story, but you are only allowed to use words from a specific dictionary (e.g., only words related to "animals," not "machines").

The Challenge: You have a story written with "machines" and "animals." Can you rewrite the whole story using only "animal" words, assuming you know the rules that link machines to animals?
The Paper's Solution: If your story's meaning doesn't actually change when you swap the "machine" words for "animal" words (based on the rules), the paper provides a method to automatically generate the "animal-only" version. This is called Vocabulary-Based Reformulation.

B. The "Positive" Lock (Positive Existential Queries)

The Analogy: Imagine you are looking for a treasure, but you are only allowed to say "Yes" if you find something. You are not allowed to say "No" if you don't find something. You can only look for things that are there, not things that aren't.

The Challenge: Can you rephrase your treasure hunt so you only look for positive signs?
The Paper's Solution: If your treasure hunt is "monotonic" (meaning adding more data to the map never makes your answer disappear), the paper shows you how to turn your question into a "positive-only" plan. It uses a special version of the translator that ensures you never accidentally use a "negative" word.

C. The "Access Method" Lock (Access Patterns)

The Analogy: This is the most realistic scenario. Imagine a library where:

You can't just walk in and browse the shelves.
To get a book, you must fill out a form.
Rule 1: To look up a "Professor," you must already know their Employee ID.
Rule 2: To get the "Employee ID," you can look at a public directory that lists everyone.
The Challenge: You want to find "Professors named Smith." You can't just search for "Smith" directly. You must first get a list of IDs from the directory, then feed those IDs into the Professor lookup.
The Paper's Solution: The paper introduces Access Interpolation. It acts like a smart itinerary planner. It looks at your question and the library's rules, and it builds a step-by-step plan (a "Plan") that chains these lookups together.
- Step 1: Get all IDs from the public directory.
- Step 2: For each ID, check if the name is "Smith."
- Step 3: Return the result.
The paper proves that if a plan exists, this interpolation method will find it. If the method fails to find a plan, it proves that no such plan is possible.

4. How It Works (The "Meta-Algorithm")

The paper outlines a general recipe for solving these problems, which it calls the Meta-Algorithm:

Identify the Rule: Figure out what "semantic property" your question must have to be solvable. (e.g., "Does the answer depend only on the accessible data?")
Turn it into a Proof: Turn that rule into a logical statement (an "entailment"). "If the rules are true, does my question follow?"
Find the Proof: Use a computer logic system to prove that statement is true.
Extract the Plan: Use the Interpolation tool on that proof. The tool looks at the proof and pulls out the "middle sentence" (the plan) that only uses the allowed words and access methods.
Execute: Run that plan.

5. Why This Matters

The paper emphasizes that this isn't just theory; it's an effective method.

It's not just saying "a plan exists."
It gives you an algorithm (a recipe) to actually build the plan from a proof.
It connects deep mathematical concepts (Model Theory) to practical database engineering (Query Rewriting).

Summary

Think of this paper as a manual for a Universal Translator for data queries.

You have a question in "Human Language" (complex, unrestricted).
You have a "Restricted Interface" (limited vocabulary or strict access rules).
The paper teaches you how to use Interpolation to automatically translate your question into a "Restricted Language" plan that is guaranteed to work, provided the answer actually depends on the data you can reach.

If the translator can't find a way to say it using only the allowed words, the paper tells you that it's impossible to answer the question with the tools you have.

Technical Summary: Interpolation and Query Rewriting

Problem Statement

The paper addresses the problem of query rewriting (or reformulation) in data management systems. The core task is to translate a declarative source query $Q$ , specified over a high-level vocabulary (e.g., an SQL schema or global schema), into a target query or procedural plan that adheres to specific interface restrictions. These restrictions generally fall into two categories:

Vocabulary-based restrictions: The target query must use a restricted set of relations (e.g., views) rather than the original base relations.
Access-pattern restrictions: The target plan must respect specific access methods (e.g., web forms or APIs) where certain arguments must be provided as input to retrieve data, and the plan must be executable using only these methods.

The goal is to determine when such a rewriting exists and, crucially, to provide effective algorithms to construct it. The paper focuses on source queries expressed in First-Order Logic (specifically Relational Quantified First-Order logic, RQFO) and targets ranging from logical formulas (e.g., positive existential, existential) to procedural plans (Relational Algebra plans).

Methodology

The paper proposes a unified "meta-algorithm" for query rewriting that bridges semantic properties, proof theory, and syntax. The methodology proceeds in five steps:

Isolate a Semantic Property: Identify a semantic condition that a source query $Q$ must satisfy with respect to the target vocabulary (or access schema) and integrity constraints $\Sigma$ to admit a rewriting. Examples include determinacy (for vocabulary restrictions) and access-determinacy (for access patterns).
Formulate as an Entailment: Translate the semantic property into a logical entailment statement of the form $\lambda \models \rho$ . This typically involves creating a "copy" of the schema (using primed relations) and asserting that if two instances agree on the restricted/accessible data, they must agree on the query output.
Search for a Proof: Use a proof system (e.g., analytic tableaux or resolution) to search for a proof of the entailment.
Extract an Interpolant: Apply a specific Craig interpolation algorithm to the proof. The interpolant $\chi$ is a formula such that $\lambda \models \chi$ and $\chi \models \rho$ , containing only symbols common to both sides of the entailment.
Convert to Reformulation: Demonstrate that the extracted interpolant $\chi$ (or a slight modification of it) constitutes the desired target query or plan.

The paper emphasizes that different target languages (e.g., positive existential vs. full first-order) require different variants of interpolation theorems (e.g., standard Craig, Lyndon, or "Access Interpolation") to ensure the interpolant possesses the necessary syntactic structure (e.g., positivity, specific binding patterns).

Key Contributions and Results

1. Vocabulary-Based Reformulation

The paper establishes effective connections between semantic determinacy and syntactic rewritability for various target languages:

First-Order Reformulation: For a target vocabulary $\mathcal{T}$ and RQFO constraints $\Sigma$ , a query $Q$ has a first-order reformulation if and only if it is determined over $\mathcal{T}$ relative to $\Sigma$ . This is proven using the Relativized-Quantifier Craig Interpolation Theorem. The existence of a proof for the determinacy entailment allows for the polynomial-time extraction of an RQFO reformulation.
Positive Existential Reformulation: For targets restricted to positive existential formulas (with inequalities), the paper introduces monotonic determinacy as the necessary semantic property. Using the Relativized-Quantifier Lyndon Interpolation Theorem, it shows that if $Q$ is monotonically determined, a positive existential reformulation can be effectively extracted from the proof.
Existential Reformulation: For targets restricted to existential formulas, the paper defines induced-subinstance-monotonicity. It proves that this property is equivalent to the existence of an existential reformulation, utilizing a specialized interpolation result to handle the specific binding patterns required.

2. Rewriting with Access Patterns

The paper extends the methodology to scenarios where data access is restricted by access methods (e.g., requiring specific input values).

Access-Determinacy: A query is access-determined if its output depends only on the "accessible part" of an instance (facts reachable via the access methods).
Access Interpolation Theorem: The paper introduces a novel interpolation theorem that tracks binding patterns (the subset of variables bound by access methods in quantified subformulas). This theorem ensures that the interpolant respects the input/output constraints of the access methods.
Main Result (Theorem 23): A Boolean RQFO query has an equivalent Relational Algebra (RA) plan if and only if it is access-determined. Furthermore, from a tableau proof of the access-determinacy entailment, an RA-plan can be extracted in linear time.
Variants for Restricted Plans: The paper provides analogous results for specific plan fragments:
- $USPJ\neq$ -plans (Union, Selection, Projection, Join, No Difference) correspond to a version of the entailment using only forward accessibility axioms.
- $USPJAD\neq$ -plans (allowing non-membership checks) correspond to a variant related to the Łos-Tarski preservation theorem, characterizing queries rewritable as existential formulas with inequalities.

3. Effective Definability and Preservation Theorems

The paper frames these results as effective versions of classical model-theoretic preservation theorems (e.g., Łos-Tarski, Beth Definability). It demonstrates that these "semantics-to-syntax" results are not just theoretical existence proofs but can be made algorithmic: the existence of a semantic property implies the existence of a proof, which in turn yields an explicit rewriting algorithm.

Significance and Claims

The paper claims to provide a general, effective framework for query rewriting that unifies diverse problems in data management (view-based reformulation, data integration, and access-constrained querying) under the umbrella of interpolation and definability.

Unification: It shows that seemingly different rewriting problems (vocabulary restriction vs. access patterns) share a common underlying structure: they are all instances of finding interpolants for specific entailments derived from semantic determinacy conditions.
Effectiveness: Unlike classical model-theoretic results which often prove existence non-constructively, this work emphasizes that interpolation algorithms yield constructive rewriting algorithms. If a rewriting exists, the method guarantees it can be found via proof search and interpolation.
New Interpolation Theorems: The paper contributes new variants of interpolation (specifically Access Interpolation and Relativized-Quantifier Lyndon Interpolation) tailored to the specific syntactic constraints of database queries (e.g., active domain semantics, binding patterns, and positivity).
Scope: The work is presented as a systematic overview of how interpolation techniques can be applied to both vocabulary-based and access-pattern-based rewriting, extending previous work by Segoufin, Vianu, Toman, and Weddell. It explicitly connects these database problems to the broader literature on preservation theorems in model theory, offering "database versions" of these classical results.

The paper does not claim to solve undecidable cases (e.g., determinacy for general Datalog or bag semantics remains open or limited) but focuses on providing a complete and effective methodology for the specific fragments of first-order logic and relational algebra commonly used in database systems.