Source-linked AI summary
Ontological Queries: Rewriting and Optimization (Extended Version)
Georg Gottlob, Giorgio Orsi, Andreas Pieris
TL;DR
The paper addresses how to compile ontology-level queries into equivalent relational queries and how to optimize those rewritings for efficient execution. It develops rewriting and query-elimination techniques for broad ontological constraints, with the optimization procedure preserving correctness while substantially reducing real-world rewriting size, subject to linear-TGD and applicability conditions.
Problem
Ontological query answering must compile ontology queries into sound, complete, and efficiently executable queries over relational databases.
Method
The paper presents a UCQ rewriting algorithm for general ontological constraints and a query-elimination optimization method for linear TGDs.
Results
Query elimination preserves soundness and completeness and substantially reduces perfect-rewriting size for real-world ontologies, though it is ineffective on intentionally exponential synthetic cases.
Takeaways & Limitations
The approach targets smaller, more cost-effective UCQ rewritings that remain executable through relational database systems.
Takeaways & Limitations
The optimization is restricted to linear TGDs, and dropping the applicability condition can produce unsound rewritings.
Abstract
from arXiv · showhide
Ontological queries are evaluated against an ontology rather than directly on a database. The evaluation and optimization of such queries is an intriguing new problem for database research. In this paper we discuss two important aspects of this problem: query rewriting and query optimization. Query rewriting consists of the compilation of an ontological query into an equivalent query against the underlying relational database. The focus here is on soundness and completeness. We review previous results and present a new rewriting algorithm for rather general types of ontological constraints. In particular, we show how a conjunctive query against an ontology can be compiled into a union of conjunctive queries against the underlying database. Ontological query optimization, in this context, attempts to improve this process so to produce possibly small and cost-effective UCQ rewritings for an input query. We review existing optimization methods, and propose an effective new method that works for linear Datalog+/-, a class of Datalog-based rules that encompasses well-known description logics of the DL-Lite family.
1 Introduction
The paper frames ontological query processing as compiling ontology-level queries into equivalent relational queries, then optimizing those rewritings for efficient execution. It situates this work in OBDA, lightweight ontology languages, and Datalog± constraints.
- Research focus: Ontological query processing compiles queries posed over an ontology into direct queries over an underlying relational database.The paper addresses both compilation and optimization of the resulting queries.
- Research focus: OBDA couples ontological reasoning with relational databases, making efficient interaction between the two technologies a central problem.Existing databases may be semantically enriched with ontological constraints and queried through ontology-based systems.
- Background: High description-logic query complexity motivates lightweight languages such as DL-Lite and EL, which provide polynomial-time data complexity for fixed TBoxes and queries.These languages are presented as tractable subclasses of OWL.
- Rewriting: FO-rewritability allows an ontology query to be compiled into an equivalent SQL-executable query evaluated and optimized by a conventional DBMS.The compilation can be separated from data access.
- Rewriting: DL-Lite, linear Datalog±, and sticky-join Datalog± are FO-rewritable, motivating the paper’s focus on correct and efficient UCQ rewriting.For these languages, a conjunctive query can be rewritten into an equivalent union of conjunctive queries.
- Datalog±: Datalog± expresses ontological constraints over relational schemas, including existential rules, inverse relations, taxonomies, and disjointness constraints.Its relation-oriented syntax can represent database attributes more directly than unary and binary description-logic predicates.
2 Ontology Based Data Access
OBDA rewriting methods target efficient access to databases under ontological constraints. Existing approaches trade rewriting size, expressiveness, parallel execution, and compatibility with database optimizers.
- Existing rewriting systems: DL-Lite rewriting systems such as QuOnto reformulate queries into UCQs, but the resulting reformulations can be unnecessarily large.The reported source attributes this to weaknesses in the rewriting process.
- Existing rewriting systems: Requiem addresses useless factorizations by handling existential quantification with functional terms, while producing a Datalog program.The approach was extended to more expressive description-logic languages.
- Existing rewriting systems: Presto eliminates unnecessary existential joins and factorizations and can split disconnected queries into connected components.Its procedure checks query connectivity before executing the rewriting algorithm.
- Generality and limitations: Backward-chaining rewriting can handle more general TGDs under termination-guaranteeing syntactic restrictions, but inherits drawbacks from earlier QuOnto-style methods.The cited approach is designed for arbitrary TGD sets satisfying suitable restrictions.
- Execution trade-offs: Rewritten conjunctive queries can execute independently in parallel, whereas non-recursive Datalog is not equally easy to distribute.The paper identifies a trade-off between keeping UCQ rewritings manageable and exploiting DBMS query optimization.
- Related optimization: Query minimization under views and constraints seeks minimal equivalent reformulations, with chase-and-back-chase identified as a relevant approach.The MARS system implements this algorithmic line of work.
3 Preliminaries
The preliminaries define relational queries, TGDs, ontology-constrained query answering, and the chase. The chase provides a universal model that reduces BCQ answering under TGDs to evaluation over the chased instance.
- Relational foundations: A relational schema contains predicate symbols with fixed arities, while atoms and conjunctions provide the building blocks of relational queries.Terms may be constants, labeled nulls, or variables.
- Relational foundations: A conjunctive query is a head predicate over a conjunction of relational atoms, and a UCQ is a set of CQs sharing arity and head predicate.UCQ answers are obtained from any constituent query that returns the tuple.
- Dependencies: A TGD states that whenever its body matches an instance, its head must also hold, possibly with existentially introduced variables.Satisfaction is defined through homomorphisms and extensions of those mappings.
- Query answering: Query answering under TGDs asks whether a query holds in every model extending the database and satisfying the dependencies.For BCQs, a positive answer is expressed as D ∪Σ |= q.
- The chase: The chase repairs a database by exhaustively applying applicable TGDs and adding head atoms with fresh labeled nulls.The algorithm applies the chase rule breadth-first and may produce an infinite instance.
- The chase: Because the chase is a universal model, D ∪Σ |= q exactly when chase(D, Σ) |= q for every BCQ.This equivalence makes the chase a central tool for query answering under TGDs.
4 The Datalog± Family
The Datalog± family organizes tractable or decidable query answering through chase termination, guardedness, and stickiness. Linear and sticky variants support FO-rewritability, while interactions with keys require restrictions such as separability.
- Decidability paradigms: Datalog± studies decidable query answering through chase termination, guardedness, and stickiness paradigms.These paradigms impose different structural restrictions on TGDs.
- Chase termination: Under chase termination, TGDs produce a finite universal model that can be directly evaluated for query answering.Weak-acyclicity is identified as a notable syntactic condition guaranteeing termination.
- Guardedness: Guarded TGDs contain a body atom covering all universally quantified variables, yielding decidability through bounded treewidth of the chase.The guard makes the chased structure tree-like.
- Linear TGDs: Linear TGDs have one body atom, are FO-rewritable, and support query answering in ac0 data complexity.They generalize inclusion dependencies while remaining a restricted form of guarded TGDs.
- Stickiness: Sticky and sticky-join TGDs use variable-marking conditions and are FO-rewritable, with sticky-join extending the framework to capture linear and sticky sets.Identifying sticky-join sets is harder than identifying sticky sets.
- Additional constraints: Negative constraints can be checked through BCQs, and when the theory is consistent they can be ignored for answering other BCQs.They are also used to represent disjointness conditions in ontologies.
- Additional constraints: General TGDs and key dependencies can make query answering undecidable, so their combination requires suitable syntactic restrictions or separability.For non-conflicting sets, key satisfaction can be checked first and the keys then eliminated from further reasoning.
- Expressiveness: Non-conflicting linear or sticky TGDs with keys and negative constraints remain more expressive than several DL-Lite languages while preserving FO-rewritability.The cited result retains high tractability in data complexity.
5 Datalog± for OBDA
The paper develops TGD-rewrite, which combines factorization and rewriting to construct perfect UCQ rewritings for BCQs under suitable Datalog± TGDs. The algorithm preserves soundness and completeness while terminating for linear, sticky, and sticky-join TGDs.
- Preprocessing: BCQ answering under general TGDs is logspace-equivalent to answering under TGDs with one head-atom and one singly occurring existential variable.These transformations preserve the relevant chase answers and syntactic classes.
- Rewriting algorithm: TGD-rewrite computes a perfect rewriting by exhaustively applying factorization and rewriting until a fixpoint is reached.Factorization removes unnecessary shared variables that can block applicability, while rewriting applies TGDs backward to query atoms.
- Correctness: Ignoring the applicability condition can produce unsound rewritings by losing constants or repeated-variable constraints.The examples show rewritten queries succeeding on a database even though the original queries are not satisfied under the chase.
- Rewriting algorithm: Factorization is essential for completeness because applicability alone can prevent deriving queries that are entailed under the TGDs.In the example, factorization enables deriving q() ← p(A) from a query involving t(A,B) and s(B).
- Correctness: The algorithm is sound and complete, with D |= qΣ iff D ∪Σ |= q, and terminates for linear, sticky, or sticky-join TGDs.Termination follows because only finitely many queries modulo bijective variable renaming are generated in these classes.
6 Rewriting Optimization
The paper introduces query elimination to optimize perfect rewritings under linear TGDs while preserving logical equivalence. It uses dependency graphs and atom coverage to remove redundant atoms and establishes soundness and completeness for the resulting rewriting algorithm.
- Query Elimination: Query elimination reduces the number of rewritten BCQs, atoms per query, and joins before database execution.It is added to TGD-rewrite after factorization and rewriting.
- Scope: Linear TGDs restrict each rule to one body atom and one head atom, enabling the elimination analysis.The paper explicitly limits this section to such TGDs.
- Dependency Graphs: A dependency graph represents positions as nodes and TGD-induced variable propagation as labeled directed edges.Paths describe possible propagation during chase construction, with equality conditions determining when propagation is guaranteed.
- Atom Coverage: Atom coverage identifies query atoms whose shared terms can be propagated through TGD paths, allowing those atoms to be safely eliminated.The resulting query is logically equivalent under the TGDs, as formalized by Lemma 8.
- Correctness: All elimination strategies remove the same number of atoms, and the optimized TGD-rewrite⋆ remains sound and complete under linear TGDs.Theorem 10 states D |= TGD-rewrite⋆(R, Σ, q) iff D ∪Σ |= q.
7 Implementation and Experimental Setting
The implementation and experiments evaluate rewriting systems for large ontologies using real-world and synthetic test cases. Rewriting quality is assessed by the size, length, and width of perfect UCQ rewritings, with query elimination helping substantially on real-world cases but not intentionally exponential synthetic ones.
- Nyaya implements TGD-rewrite and query elimination using an extended IRIS Datalog engine for FO-rewritable Datalog± fragments.
- Experiments use DL-LiteR ontologies with varying axiom counts and canonical queries from real-world and synthetic projects.
- The evaluation compares Nyaya with QuOnto and Requiem, two rewriting-based systems for FO-rewritable ontologies.
- Rewriting quality is measured by perfect-rewriting size, length, and width because the compared algorithms are sound and complete.Size counts conjunctive queries, length counts atoms, and width counts joins executed in the rewritten query.
- Query elimination substantially reduces perfect-rewriting size for real-world ontologies A, U, and S, but is ineffective on exponential synthetic cases P5 and P5X.For Q2 in U and S, it eliminates all redundant input atoms and drastically reduces the final number of queries.
8 Future Work
Future work extends rewriting and optimization beyond the current settings. Planned directions include sticky-join TGDs, positive-existential rewritings, and polynomial-size non-recursive Datalog programs.
- The authors plan to investigate rewriting and optimization techniques for sticky-join sets of TGDs.
- They also plan to study alternative rewriting forms, including positive-existential queries.
- Future work will develop improved techniques for rewriting ontological queries into non-recursive Datalog programs rather than UCQs.
- The planned Datalog rewritings aim for size polynomial in both the query and the TBox, unlike current exponentially large programs.