Source-linked AI summary
Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP
Meghyn Bienvenu, Balder ten Cate, Carsten Lutz, Frank Wolter
TL;DR
The paper asks how ontology-mediated queries over incomplete data can be characterized and classified. It relates them to disjunctive datalog, CSPs, and MMSNP, obtaining results on expressiveness, complexity, rewritability, and containment. It also identifies open questions for UCQ-based rewritability and guarded MMSNP variants.
Problem
The paper addresses the need for expressive and complexity-theoretic classifications of ontology-mediated queries, including their rewritability and containment properties.
Method
It characterizes ontology-mediated queries using disjunctive datalog and establishes connections with CSPs and MMSNP across description logics and first-order fragments.
Results
The paper derives expressiveness correspondences, PTIME/CONP dichotomy results, decidability and complexity results for containment and rewritability, and a strict expressiveness extension from MMSNP to GMSNP.
Takeaways & Limitations
The connections make techniques from CSP and MMSNP applicable to ontology-mediated query evaluation, containment, and rewritability analysis.
Takeaways & Limitations
The data-complexity status of GMSNP and MMSNP2 remains open, and FO- and datalog-rewritability for UCQ-based queries remains future work.
Abstract
from arXiv · showhide
Ontology-based data access is concerned with querying incomplete data sources in the presence of domain-specific knowledge provided by an ontology. A central notion in this setting is that of an ontology-mediated query, which is a database query coupled with an ontology. In this paper, we study several classes of ontology-mediated queries, where the database queries are given as some form of conjunctive query and the ontologies are formulated in description logics or other relevant fragments of first-order logic, such as the guarded fragment and the unary-negation fragment. The contributions of the paper are three-fold. First, we characterize the expressive power of ontology-mediated queries in terms of fragments of disjunctive datalog. Second, we establish intimate connections between ontology-mediated queries and constraint satisfaction problems (CSPs) and their logical generalization, MMSNP formulas. Third, we exploit these connections to obtain new results regarding (i) first-order rewritability and datalog-rewritability of ontology-mediated queries, (ii) P/NP dichotomies for ontology-mediated queries, and (iii) the query containment problem for ontology-mediated queries.
1. INTRODUCTION
The paper studies ontology-mediated queries for incomplete data, characterizing their expressive power and connecting them to disjunctive datalog, CSPs, and MMSNP. These connections yield results on complexity dichotomies, rewritability, and containment.
- Motivation: Ontology-mediated queries combine a database query with an ontology to answer queries over incomplete data using domain knowledge.Ontologies can enrich incomplete sources, such as inferring Lyme disease from Erythema Migrans.
- Aims: The paper aims to characterize ontology-mediated query expressiveness and classify data complexity, FO-rewritability, and datalog-rewritability.
- Expressiveness: (ALC,UCQ) matches monadic disjunctive datalog, while (GF,UCQ) and (GNFO,UCQ) match the more expressive frontier-guarded disjunctive datalog.
- CSP and MMSNP connections: (ALC,UCQ) and many other UCQ-based OBDA languages capture coMMSNP, linking ontology-mediated queries to descriptive complexity.
- Complexity: There is a PTIME/CONP dichotomy for (ALC,UCQ) exactly if the Feder-Vardi conjecture holds, while (ALCF,AQ) has no such dichotomy unless PTIME = NP.
- Atomic queries: For atomic queries, the paper connects ontology-mediated queries to CSP complements and obtains NEXPTIME-complete containment, FO-rewritability, and datalog-rewritability.
2. PRELIMINARIES
The preliminaries define schemas, instances, queries, ontologies, certain answers, and expressive equivalence. They introduce ontology-mediated queries as triples and illustrate their semantics and rewriting behavior.
- Basic definitions: A schema is a finite collection of relation symbols with arities, an instance is a finite set of facts, and queries return tuples from an instance's active domain.
- Query languages: FO, conjunctive, union-of-conjunctive, and atomic queries are introduced, with atomic queries having the form A(x).
- Expressiveness: Two queries are equivalent when they return the same answers on every instance, and expressive-power comparisons are defined through mutual representability.
- Ontology-mediated queries: Ontology-mediated queries are triples (S, O, q), where S is the data schema, O an ontology, and q a query over the combined vocabulary.
- Semantics: Certain answers are defined using finite models of the ontology, and finite controllability permits replacing finite structures with unrestricted ones for UCQs.
- Description logics: The ALC description logic uses concept and role names with constructors including negation, conjunction, disjunction, existential restriction, and universal restriction.
- Examples: An example shows that one ontology-mediated query is equivalent to a union of conjunctive queries, whereas another has a datalog rewriting but no first-order rewriting.
3. OBDA AND DISJUNCTIVE DATALOG
The paper characterizes ontology-mediated query languages through disjunctive datalog, with exact expressive-power correspondences for several description-logic and first-order settings. These correspondences also expose restrictions and extensions, including connectedness for atomic queries and frontier-guarded rules for guarded fragments.
- Many OBDA languages have natural fragments of negation-free disjunctive datalog with exactly the same expressive power.
- Description logics: (ALC,UCQ) has the same expressive power as MDDlog, while (ALC,AQ) corresponds to unary connected simple MDDlog.The same correspondence extends to several description-logic variants and concept-query formulations.
- Translation method: The translation from (ALC,UCQ) to MDDlog uses types and diagrams to represent suitable extensions of the database and enforce query matches.The construction introduces unary IDB predicates for types and establishes equivalence between the resulting MDDlog query and the ontology-mediated query.
- Description-logic extensions: (ALCU,AQ) and (SHIU,AQ) have the same expressive power as unary simple MDDlog, whereas adding transitive roles increases expressive power for UCQs but not for atomic queries.The universal role corresponds to dropping connectedness requirements on rule bodies.
- First-order ontologies: (UNFO,UCQ) has the same expressive power as MDDlog, while (GF,UCQ) and (GNFO,UCQ) have the same expressive power as frontier-guarded DDlog.The guarded-fragment result is obtained through translations involving frontier-guarded disjunctive datalog.
4. OBDA AND MMSNP
The paper identifies OBDA query languages with complements of MMSNP and uses this correspondence to transfer complexity and containment results. It also extends the correspondence to guarded settings, while leaving dichotomy and related classification questions open there.
- OBDA and MMSNP: MDDlog, the complement of MMSNP, provides a descriptive-complexity characterization of several OBDA languages based on UCQs.The paper establishes coMMSNP and MDDlog as expressively equivalent and uses this to characterize OBDA languages.
- Data complexity: The Feder–Vardi conjecture holds if and only if (ALC,UCQ), (ALCHIU,UCQ), and (UNFO,UCQ) have a PTIME/CONP dichotomy for query evaluation.This transfers the CSP/MMSNP dichotomy question to ontology-mediated query evaluation.
- Open problems: The paper leaves the computational power of (S,UCQ) open and identifies FO- and datalog-rewritability for UCQ-based OBDA as equivalent to definability questions for MMSNP or GMSNP.These are stated as future research directions rather than resolved classifications.
- Query containment: Query containment is decidable for (ALC,UCQ), (ALCHIU,UCQ), and (UNFO,UCQ).The result applies to UCQs, extending beyond earlier containment results restricted to atomic queries.
- Open problems: The guarded languages (GF,UCQ) and (GNFO,UCQ) capture coGMSNP, but whether they satisfy a PTIME/NP dichotomy under the Feder–Vardi conjecture remains open.The corresponding open question is equivalently about the complexity of GMSNP or MMSNP2.
- Guarded extensions: GMSNP generalizes MMSNP through guarded second-order quantification, and coGMSNP has the same expressive power as frontier-guarded disjunctive datalog.The paper also shows that coGMSNP is strictly more expressive than coMMSNP and that GMSNP and MMSNP2 are equivalent.
5. OBDA AND CSP
The paper connects ontology-mediated queries based on atomic queries with CSPs and their generalizations, yielding expressive-power correspondences and transferred complexity results.
- CSP connections: Ontology-mediated queries based on AQs capture CSPs and generalized CSPs, extending the Boolean coCSP connection to queries with constants.Generalized CSPs use finite sets of templates, while constant-symbol variants require homomorphisms to preserve designated elements.
- Expressive power: Theorem 12 equates several OBDA languages with MDDlog fragments and generalized coCSP variants, including ALCU and ALC query forms.The correspondences distinguish unary versus Boolean queries, connected versus unrestricted fragments, and the presence of constant symbols.
- CSP connections: Each ontology-mediated query or monadic datalog program yields a corresponding CSP template of at most exponential size, constructible in polynomial time in the template size.
- CSP connections: For every database instance and element, non-membership in the ontology-mediated query is equivalent to a homomorphism into one of the constructed pointed templates.This establishes equivalence between the ontology-mediated query and the associated generalized coCSP query.
- Complexity: The PTIME/CONP dichotomy for several AQ and BAQ languages is equivalent to the Feder–Vardi conjecture for CSPs.The result applies to (ALC,BAQ), (SHIU,AQ), and (SHIU,BAQ), with related consequences for (ALC,CQ).
- Decision problems: Query containment for (SHIU,AQ∪BQ) is NEXPTIME-complete, while FO- and datalog-rewritability are NEXPTIME-complete for the stated ALC cases and undecidable for ALCF.The corresponding CSP definability results provide the basis for these rewritability bounds.
6. CONCLUSION
The paper leaves several classification questions open, including CSP-style complexity for conjunctive-query OBDA and rewritability or complexity questions for UCQ-based languages.
- Open problems: Whether (ALC,CQ) has a natural characterization in terms of disjunctive datalog remains open.
- Open problems: The data complexity and query containment of (GF,UCQ) and (GNFO,UCQ) remain future research questions linked to the status of GMSNP and MMSNP2.
- Open problems: Deciding FO-rewritability and datalog-rewritability for UCQ-based ontology-mediated queries remains an open topic equivalent to definability questions for MMSNP or GMSNP formulas.
A.1 Proofs for Section 3.1
The section proves expressive-power correspondences between ontology-mediated query languages and MDDlog fragments, while establishing strict separations for several extensions. It also records equivalent formulations and adaptations for Boolean atomic queries.
- Expressive-power characterizations: (ALC,UCQ) and MDDlog have the same expressive power.The translation is established in both directions through type-based constructions and realizable diagrams.
- Expressive-power characterizations: (ALC,AQ) has the same expressive power as unary connected simple MDDlog.The proof establishes equivalence between certain answers and the goal predicate produced by the constructed program.
- Extensions and separations: ALCHIU with UCQs has the same expressive power as MDDlog and (ALC,UCQ), while (S,UCQ) and (ALCF,UCQ) are strictly more expressive than (ALC,UCQ).These results distinguish extensions that preserve the baseline expressive power from those that increase it.
- Extensions and separations: There are queries in (S,UCQ) and (ALCF,UCQ) that do not belong to MDDlog.The non-membership results use a forbidden-pattern characterization and a coloring-based sufficient condition for non-expressibility.
A.2 Proofs for Section 3.2
This section extends the expressive-power analysis to unary-negation and guarded fragments, identifying MDDlog and frontier-guarded disjunctive datalog as the corresponding target languages. It also proves a strict separation from MDDlog for a guarded-fragment query.
- Unary-negation fragment: (UNFO,UCQ) has the same expressive power as MDDlog.The proof uses type-coherent structures and inductive arguments over formulas in the closure of the ontology.
- Unary-negation fragment: The translation for UNFO relies on decomposing connected formulas and queries into subqueries handled within disjoint ontology models.Connectedness ensures that the relevant active-domain elements can be related through the constructed diagrams and subinstances.
- Guarded fragment: A Boolean query is definable in (GF,UCQ) but not in MDDlog.The separation is proved using explicit instances with different query values and a coloring argument satisfying the non-expressibility lemma.
- Guarded fragment: (GF,UCQ) and (GNFO,UCQ) have the same expressive power as frontier-guarded DDlog.The translations use frontier-guarded rules as GNFO implications and a guarded normal form for the reverse direction.
B. PROOFS FOR SECTION 4
The appendix begins by establishing a technical result for MMSNP with constant symbols, then uses it to lift containment and dichotomy results from MMSNP sentences to coMMSNP queries.
- Appendix roadmap: The appendix first proves a central technical result about MMSNP extended with constant symbols.This result supports the subsequent transfer of results from sentences to queries with free variables.
- Appendix roadmap: Section B.1 lifts key results from MMSNP sentences to coMMSNP queries with free variables.The stated targets include containment and dichotomy results.
- Appendix roadmap: Section B.2 provides proofs for the results stated in Section 4 of the main paper.
B.1 MMSNP with Constant Symbols
This section uses MMSNP with constants and forbidden-pattern problems as a bridge between coMMSNP queries and ordinary MMSNP, preserving polynomial relationships for evaluation and containment. It culminates in the coMMSNP dichotomy and containment results.
- Consequences: coMMSNP has a dichotomy between PTIME and CONP if and only if the Feder–Vardi conjecture holds, and containment is decidable.
- MMSNP with constants: MMSNP with constant symbols serves as a bridge between coMMSNP queries and MMSNP sentences.The construction proceeds through evaluation equivalence and polynomial containment reductions in both stages.
- MMSNP with constants: Evaluation of coMMSNP is polynomially equivalent to evaluation of MMSNPc, while coMMSNP containment polynomially reduces to MMSNPc containment.
- Forbidden-pattern problems: MMSNPc and FPPc have the same expressive power, and FPPc containment polynomially reduces to FPP containment.Forbidden-pattern problems are extended to structures with constant symbols before removing the constants through polynomial reductions.
- Forbidden-pattern problems: FPPc is polynomially equivalent to FPP through transformations between structures with constants and structures augmented by unary predicates.The transformations include collapse operations and homomorphism correspondences.
B.2 Proofs for Section 4
The section establishes that coGMSNP matches frontier-guarded disjunctive datalog and strictly extends coMMSNP, while proving a Feder–Vardi-equivalent dichotomy for several ontology-mediated query languages.
- (ALC,UCQ), (ALCHIU,UCQ), and (UNFO,UCQ) have a PTIME/CONP dichotomy if and only if the Feder–Vardi conjecture holds.
- coGMSNP has the same expressive power as frontier-guarded disjunctive datalog and is strictly more expressive than coMMSNP.
- GMSNP and MMSNP2 have the same expressive power.
- The translation from MMSNP2 to GMSNP introduces guarded second-order variables for atoms occurring in implication heads.The construction selects a guard for each head atom, replaces non-monadic atoms using guarded variables, and forms an equivalent sentence.
- The converse translation normalizes GMSNP sentences by guarding head variables, closing implications under variable identification, and separating variables across implications.These conditions support the subsequent construction of an equivalent MMSNP2 sentence.
- The equivalence proof constructs Φ′ from guarded implications and shows both directions of satisfaction preservation between Φ and Φ′.The proof uses assignments and injective variable mappings to transfer satisfied bodies and refuted heads between the two sentences.
C. PROOFS FOR SECTION 5
This section connects ontology-mediated query languages with generalized CSPs and derives results on expressiveness, rewritability, dichotomies, and containment, including NEXPTIME bounds and undecidability results.
- Expressive equivalences: (ALC,AQ), (ALC,BAQ), (ALCU,BAQ), and related MDDlog and generalized coCSP languages form matching expressive-power classes.The equivalences include unary and Boolean variants, with generalized coCSPs distinguished by whether templates share a constant interpretation.
- CSP connections: Ontology-mediated queries and monadic datalog programs yield CSP templates of at most exponential size, constructible in polynomial time in the template size.
- Containment: Query containment in (SHIU,AQ) is in NEXPTIME and is NEXPTIME-hard already for (ALC,AQ) and (ALC,BAQ).
- Rewritability: For finite obstruction sets, coCSP definability and datalog-definability transfer between individual templates and their combined query under mutual homomorphic incomparability.The transfer holds in both directions when all templates are mutually homomorphically incomparable.
- Rewritability: FO-rewritability is NEXPTIME-hard for (ALC,AQ) and (ALC,BAQ), while datalog-rewritability is NEXPTIME-hard for the same languages.
- Undecidability: Query containment, FO-rewritability, and datalog-rewritability are undecidable for (ALCF,AQ) and (ALCF,BAQ).