TL;DR
This paper investigates the computational complexity of querying data integrated with ontologies when some predicates are treated as "closed" (meaning their interpretation is strictly limited to what's explicitly stated). The authors show that for simpler ontology languages (DL-Lite, EL), this "closed world" assumption often leads to intractable query answering, even when the ontology itself is simple. However, for more expressive languages (ELI), this intractability can be avoided.
What Problem Does This Paper Address?
Ontology-Based Data Access (OBDA) aims to provide a unified way to query data that might be scattered across various sources, using an ontology to provide a shared understanding. A common assumption in OBDA is the Open World Assumption (OWA), where information not explicitly stated is assumed to be unknown. However, in many real-world scenarios, especially when data originates from relational databases, it's more natural to assume a Closed World Assumption (CWA) for certain predicates. This means that if a fact isn't explicitly present, it's considered false.
The challenge arises because applying CWA to even simple ontology languages can drastically increase the computational cost of answering queries, pushing it into intractable complexity classes like CONP. This paper delves into when this intractability occurs for specific ontology languages (DL-Lite and EL) and when it can be avoided, particularly by considering more expressive languages like ELI. They aim to map out the precise boundaries of tractability when mixing open and closed predicates.
Methods
The paper employs a "non-uniform" complexity analysis, meaning they analyze the complexity for specific ontologies rather than for the entire logic. They introduce the concept of "safeness" for ontologies with closed predicates, which acts as a crucial indicator of tractability.
- Safeness Definitions: They define "safeness" for DL-Litecore, DL-Lite, and EL ontologies with closed predicates. These definitions essentially capture conditions that would lead to non-convexity and, consequently, CONP-hardness.
- Convexity: A key property they leverage is "convexity." An ontology is convex if the disjunction of two query answers implies that at least one of the answers must hold. Non-convexity is a strong indicator of intractability.
- Complexity Classes: They analyze query answering complexity in terms of standard classes like PTIME (polynomial time) and CONP (co-non-deterministic polynomial time).
- Proof Techniques: The proofs often involve constructing specific ABoxes and queries to demonstrate non-convexity and CONP-hardness. For tractability, they rely on canonical models and show that satisfiability of ABoxes can be decided efficiently.
Datasets
Not discussed in the paper. The paper focuses on theoretical analysis and uses abstract examples rather than specific datasets.
Key Insights and Ideas
- "Inherently Intractable (Sometimes)": The core finding is that for simpler DLs like DL-Lite and EL, adding closed predicates often makes query answering intractable, even if the ontology itself is simple. This intractability is "inherent" in the sense that if a tractable case exists, it's often equivalent to treating all predicates as open.
- The Dichotomy: For DL-Lite and EL, the paper establishes a clear dichotomy: query answering is either tractable (in AC⁰ or PTIME, respectively) or CONP-hard. There's no intermediate complexity.
- Safeness as a Predictor: The newly introduced concept of "safeness" for ontologies with closed predicates is a powerful tool. If an ontology is "safe," query answering remains tractable and often coincides with the open-world case. If it's "unsafe," expect CONP-hardness.
- ELI's Advantage: More expressive languages like ELI, which support inverse roles, can avoid this inherent intractability. They show that ELI ontologies with closed predicates can have tractable query answering that doesn't necessarily coincide with the open-world assumption, offering more flexibility.
- Beyond CQs: The paper also suggests that for "safe" ontologies, closed predicates can enable the use of more expressive query languages (like first-order queries) without increasing data complexity, which is a significant practical benefit.
Key Results
- DL-Litecore & DL-Lite:
- If an ontology is "unsafe," CQ answering is CONP-hard.
- If an ontology is "safe," CQ answering coincides with the open-world case and is in AC⁰.
- This establishes a dichotomy between AC⁰ and CONP for DL-Lite variants.
- EL:
- If an ontology is "unsafe," CQ answering is CONP-hard.
- If an ontology is "safe," CQ answering coincides with the open-world case and is in PTIME.
- This establishes a dichotomy between PTIME and CONP for EL.
- ELI:
- CQ answering with closed predicates is not inherently intractable.
- There exist ELI ontologies where CQ answering is in PTIME but differs from the open-world case.
- Safeness Decidability: Safeness for EL TBoxes with closed predicates can be decided in PTIME.
Limitations and Future Work
- Limitations: The paper focuses on specific DLs (DL-Lite, EL, ELI) and conjunctive queries (CQs). The results for DL-Litecore are presented as a stepping stone to DL-Lite. The "inherent intractability" for simpler DLs is a significant finding but highlights a practical challenge.
- Future Work:
- Extend the study to other ontology languages, including more expressive Horn DLs and Datalog-based languages.
- Fully understand the phenomenon of intractability in ELI, specifically investigating whether a PTIME vs. CONP dichotomy exists for ELI TBoxes with closed predicates.
- Characterize ELI TBoxes where CQ answering with closed predicates coincides with the open-world case.
Summary updated