TL;DR
This paper investigates the compatibility of "cross products" (a way to relate all instances of one concept to all instances of another) with guarded ontology languages, which are crucial for efficient data access. The authors find that while binary cross products are compatible for ontology satisfiability, they render ontology-mediated query answering undecidable in general. However, decidability can be regained by restricting queries to acyclic forms or by using guarded existential rules.
What Problem Does This Paper Address?
Ontology-based data access (OBDA) systems allow users to query data using a high-level conceptual view (an ontology) without needing to know the underlying data sources' specifics. This relies on ontologies that balance expressivity with computational tractability. Guarded ontology languages, like Description Logics (DLs) and existential rules, are popular choices because they offer good reasoning properties.
However, these languages often lack certain expressive features useful for modeling. Two such features are transitivity (e.g., "if A is a descendant of B, and B is a descendant of C, then A is a descendant of C") and cross products (e.g., "all elephants are bigger than all mice"). While transitivity has been extensively studied in the context of guarded languages, cross products have received less attention. This paper specifically tackles the compatibility of cross products with guarded ontology languages, focusing on two key reasoning tasks: ontology satisfiability (whether an ontology has at least one valid interpretation) and ontology-mediated query (OMQ) answering (retrieving data based on an ontology and a query). The core question is whether adding cross products to existing guarded languages breaks their decidability and tractability.
Methods
The paper uses the guarded fragment (GF) of first-order logic as a unifying framework for guarded ontology languages. They extend this framework with cross products, denoted as GF×. The authors then analyze the complexity of satisfiability and OMQ evaluation for these extended languages.
For satisfiability, they first consider ternary cross products (GF×3) and demonstrate its undecidability by reducing the problem of satisfiability for guarded fragments with transitivity (GFtr) to it. They then focus on binary cross products (GF×2) and show that satisfiability is decidable and 2EXPTIME-complete. This is achieved by developing a complex transformation of GF×2 ontologies into equivalent GF ontologies, involving a "normalization" process and a sophisticated simulation of cross product applications using guarded rules.
For OMQ evaluation, the paper shows that even with binary cross products and the two-variable fragment of GF (GF×22), the problem remains undecidable. This is a significant negative result, indicating a fundamental incompatibility for query answering. To recover decidability, they explore two avenues:
- Restricting Queries: They show that OMQ evaluation becomes decidable (2EXPTIME-complete combined, coNP-complete data complexity) when queries are restricted to acyclic UCQs (AUCQ).
- Restricting Ontology Language: They demonstrate that OMQ evaluation is decidable (2EXPTIME-complete combined, PTIME-complete data complexity) when using guarded existential rules (GER) extended with binary cross products.
Datasets
Not discussed in the paper. The paper focuses on theoretical complexity analysis rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Cross products are a powerful modeling feature, but they come at a cost: While intuitive for expressing relationships, they significantly impact the decidability of reasoning tasks, especially for query answering.
- The decidability frontier is sharp: Satisfiability for guarded languages with cross products is decidable for binary cross products but becomes undecidable with just ternary ones. This highlights the critical role of the arity of cross products.
- Query answering is more sensitive than satisfiability: The paper reveals a stark contrast: while satisfiability with binary cross products is decidable, OMQ evaluation remains undecidable even for the restricted two-variable fragment. This suggests that the structure of queries interacting with cross products is particularly problematic.
- Decidability can be salvaged through careful restrictions: The research provides a roadmap for using cross products in practical systems by identifying specific restrictions on queries (acyclic UCQs) or ontology languages (guarded existential rules) that restore decidability.
- The "guarded property" is key: The paper's analysis of dangerous cross product applications hinges on how they can violate the "guarded property" in chase procedures, leading to disconnected components in models and breaking the expected structure.
Key Results
- Satisfiability:
- Sat(GF×3) is undecidable.
- Sat(GF×2) is 2EXPTIME-complete.
- OMQ Evaluation:
- Eval(GF×22, CQ) is undecidable.
- Eval(GF×2, AUCQ) is 2EXPTIME-complete (combined), coNP-complete (data complexity).
- Eval(GER×2, UCQ) is 2EXPTIME-complete (combined), PTIME-complete (data complexity).
Limitations and Future Work
- Bounded Arity: The exact complexity of Sat(GF×2) for bounded arity relations remains open, though it is shown to be NEXPTIME-hard.
- Query Rewritability: The authors suggest studying query rewritability for the ontology languages that are compatible with binary cross products as an interesting future research direction.
- Practical Implementations: While theoretical results are provided, the paper doesn't delve into the practical implementation challenges or performance of systems that might incorporate these extended languages.
Summary updated