Source-linked AI summary
The DL-Lite Family and Relations
Alessandro Artale, Diego Calvanese, Roman Kontchakov, Michael Zakharyaschev
TL;DR
DL-Lite extensions require a systematic account of how added constructs interact computationally. The article studies these interactions across a spectrum of logics and uses embeddings into one-variable first-order logic, finding major complexity increases for some combinations and data-complexity effects from selected constraints.
Problem
Existing DL-Lite dialects added conceptual-modeling constructs in somewhat ad hoc ways, leaving their combined effects on reasoning complexity insufficiently understood.
Method
The article classifies DL-Lite logics by five orthogonal features and embeds them into suitable fragments of one-variable first-order logic.
Results
Instance checking is P-complete for core and Horn logics and coNP-complete for Krom and Bool logics; combining role inclusions with number restrictions makes satisfiability ExpTime-complete.
Takeaways & Limitations
Embeddability into equality-free, function-free one-variable first-order logic characterizes the broader DL-Lite family and relates its reasoning complexity to corresponding logical fragments.
Takeaways & Limitations
The supported DL-Lite and OWL 2 coverage excludes nominals, Boolean operators on roles, and role chains.
Abstract
from arXiv · showhide
The recently introduced series of description logics under the common moniker DL-Lite has attracted attention of the description logic and semantic web communities due to the low computational complexity of inference, on the one hand, and the ability to represent conceptual modeling formalisms, on the other. The main aim of this article is to carry out a thorough and systematic investigation of inference in extensions of the original DL-Lite logics along five axes: by (i) adding the Boolean connectives and (ii) number restrictions to concept constructs, (iii) allowing role hierarchies, (iv) allowing role disjointness, symmetry, asymmetry, reflexivity, irreflexivity and transitivity constraints, and (v) adopting or dropping the unique same assumption. We analyze the combined complexity of satisfiability for the resulting logics, as well as the data complexity of instance checking and answering positive existential queries. Our approach is based on embedding DL-Lite logics in suitable fragments of the one-variable first-order logic, which provides useful insights into their properties and, in particular, computational behavior.
1. Introduction
The paper systematically studies how five orthogonal extensions of DL-Lite affect reasoning complexity while preserving its role in conceptual modeling. It identifies tight complexity results and uses one-variable first-order embeddings to explain the variants’ computational behavior.
- DL-Lite combines low-complexity inference with the ability to represent important conceptual-modeling constraints.It underlies OWL 2 QL, intended for applications with very large data volumes where query answering is central.
- The study varies role inclusions, concept-inclusion forms, numeric constraints, the unique name assumption, and standard role constraints.The concept-inclusion classes are core, Krom, Horn, and Bool; numeric constraints range from none through functionality to arbitrary number restrictions.
- For these variants, the paper analyzes combined and data complexity of satisfiability and instance checking, plus data complexity of query answering.The resulting tight complexity results are summarized in the paper’s complexity tables.
- The family is characterized by embeddability into equality-free, function-symbol-free one-variable first-order logic, linking its reasoning complexity to corresponding first-order fragments.This embedding supplies upper bounds and insight into the logical properties of individual DL-Lite variants.
- Role inclusions combined with number restrictions sharply increase complexity: instance checking becomes P-complete or coNP-complete, while satisfiability becomes ExpTime-complete.The instance-checking bounds depend on the concept-inclusion fragment: P-complete for core and Horn, coNP-complete for Krom and Bool.
- A restricted interaction between role inclusions and number restrictions preserves the one-variable embedding and the behavior of fragments using either feature alone.This extends the motivation behind DL-LiteA while retaining both kinds of constructs in a controlled form.
2. The Extended DL-Lite Family of Description Logics
Description logics provide knowledge-representation formalisms in which concepts describe classes, roles describe binary relationships, and knowledge is divided between TBox and ABox assertions.
- Description logics structure a domain into concepts, specify properties through roles, and construct complex expressions from concept and role names.The available constructs depend on the particular description logic.
- A TBox records intensional knowledge through axioms, whereas an ABox records extensional facts about objects and role connections.
- Standard reasoning services include satisfiability checking and query answering and rely on logic-based semantics.
2.1 Syntax and Semantics of the Logics in the DL-Lite Family
The extended DL-Lite languages are formed by restricting a broad language along Boolean operators, number restrictions, and role inclusions, with interpretations assigning concepts, roles, and object names semantic values.
- The extended family starts from DL-LiteHN_bool, described as the supremum of the original DL-Lite family in the lattice of description logics.
- Its knowledge bases contain a TBox of concept and role inclusions and an ABox of positive or negative concept and role assertions.The ABox assertions include concept membership, role connections, and their negations.
- Interpretations use a nonempty domain, map object names to domain elements, and interpret role names as binary relations.The unique name assumption is adopted unless results explicitly state otherwise.
- The family varies three axes: Boolean operators on concepts, number restrictions, and role inclusions or hierarchies.
- Krom, Horn, and core fragments restrict concept inclusions differently, with core TBoxes lying in the intersection of Krom and Horn.
- Functionality constraints permit only the restricted number restriction ≥2 R ⊑⊥, while DL-LiteHF variants are costly because role inclusions interact with functionality or number restrictions.A controlled limitation of this interaction provides a compromise for conceptual modeling.
DL-Lite(HN)
The extended DL-Lite family adds selected role constraints and qualified number restrictions under syntactic conditions designed to expand expressive power without changing the intended computational behavior.
- DL-Lite(HN): Additional constructs such as limited qualified existential quantifiers and role constraints increase expressive power without affecting computational properties.This claim applies to the languages with the specified restrictions on interaction between role inclusions and number restrictions.
- DL-Lite(HN): Qualified number restrictions may occur only positively, with their fillers restricted to conjunctions allowed on the right-hand side of concept inclusions.
- DL-Lite(HN): If a qualified number restriction occurs, negative occurrences of number restrictions are disallowed; analogous restrictions apply when a role has a proper sub-role.
- DL-Lite(HN): The family includes role disjointness, asymmetry, symmetry, irreflexivity, and reflexivity constraints in its extended languages.These constructs are motivated by their use in conceptual modeling and by OWL 2 QL.
- DL-Lite(HN): Transitivity is constrained so that number restrictions with q ≥2 apply only to simple roles, excluding transitive roles and roles with transitive sub-roles.
DL-Lite(HF)
The extended DL-Lite family combines role transitivity constraints with a spectrum of concept-inclusion and numeric-restriction choices, yielding 40 logics organized by feature combinations.
- DL-Lite(HF): Role transitivity constraints are included among the extensions considered for the DL-Lite family.
- DL-Lite(HF): The extended family contains 40 different logics formed by combining the left- and right-hand feature dimensions.The combinations vary concept inclusions and role or number restrictions, with the corresponding inclusions displayed in Figure 1.
- DL-Lite(HF): The family’s logics are positioned relative to earlier DL-Lite variants and OWL 2 QL before their computational properties are analyzed.
2.2 DL-Lite for Conceptual Modeling
DL-Lite can represent UML class diagrams by translating classes, attributes, relationships, cardinalities, and covering constraints into concept and role axioms. The full Boolean fragment is needed for the UML covering constraint.
- Conceptual modeling: DL-Lite represents UML class-diagram classes and relationships using concept inclusions and role axioms.The example models a company information system with managers, employees, projects, attributes, and relationships.
- Conceptual modeling: Functional attributes are modeled as roles to integer-valued concepts, without distinguishing abstract objects from data values.
- Conceptual modeling: Role axioms encode domains, ranges, and participation requirements such as employee-project and employee-boss relationships.
- Conceptual modeling: Cardinality and participation constraints express that top managers manage one project, projects have one top manager, and employees satisfy specified relationship requirements.
- Conceptual modeling: Only DL-LiteHN_bool can represent the complete UML class diagram because its covering constraint requires Boolean concept inclusions.All other translated concept inclusions belong to variants of the core fragments, except Manager ⊑ AreaManager ⊔ TopManager.
3. Reasoning in DL-Lite Logics
The article studies satisfiability, instance checking, and positive existential query answering across extended DL-Lite logics, deriving tight complexity results under varying language features and assumptions.
- Satisfiability: KB satisfiability asks whether an L-KB has a model and serves as a basis for reducing several other reasoning problems.
- Instance checking: Instance checking determines whether every model of a KB places a named object in a specified concept.
- Relationships among tasks: Satisfiability, instance checking, and query answering are linked by reductions, including instance checking as a special case of query answering.
- Query answering: Positive existential queries use conjunction, disjunction, and existential quantification over concept and role atoms.
- Reasoning tasks: The analysis covers combined and data complexity for KB satisfiability and instance checking, plus data complexity for query answering.
- Complexity results: Under the considered hierarchy, upper bounds for stronger DL-Lite variants transfer to their sublanguages.
- Complexity results: Adding equality without the UNA changes AC0 memberships to LogSpace-completeness, while role transitivity makes instance checking and query answering NLogSpace-complete.
4. The Landscape of DL-Lite Logics
The DL-Lite landscape balances conceptual-modeling expressiveness against reasoning complexity, with OWL 2 QL emphasizing large-data query answering. The UNA and added constructs materially affect complexity.
- Landscape: DL-Lite was designed to represent conceptual-modeling features while retaining tractable reasoning and AC0 data complexity for query answering.
- Landscape: DL-LiteA adds object-versus-data distinctions, roles versus attributes, role inclusions, and functionality for conceptual modeling.The object/data and concept/datatype distinctions do not affect reasoning in the reported results.
- Landscape: Role inclusions and functionality cannot be combined unrestrictedly without losing the family’s favorable computational properties.
- Landscape: DL-Lite variants differ in query-answering complexity, ranging from AC0 through P-complete to coNP-complete data complexity.
- DL-Lite and OWL 2: OWL 2 QL is based on a DL-Lite variant and targets very large instance datasets where query answering is the primary reasoning task.
- DL-Lite and OWL 2: Dropping the UNA interacts with number restrictions: instance checking for DL-LiteF_core rises from AC0 to P-complete data complexity.
- DL-Lite and OWL 2: OWL 2 QL excludes constructs that interfere with the UNA or cause higher complexity without it, including number restrictions and keys.
- Landscape: Role transitivity preserves combined satisfiability complexity but raises data complexity for instance checking and query answering to NLogSpace-completeness.
5. Satisfiability: Combined Complexity
The section establishes combined-complexity bounds for satisfiability across DL-Lite extensions, using embeddings into the one-variable fragment of first-order logic and reductions from alternating Turing machines. Complexity ranges from NLogSpace-complete and P-complete to NP-complete and ExpTime-complete, depending on the available constructs and their interaction.
- Functionality and role inclusions: Unrestricted combinations of functionality constraints and role inclusions make satisfiability ExpTime-hard, including for DL-LiteHF_core knowledge bases.The lower bound is established by simulating polynomial-space-bounded alternating Turing machines.
- First-order perspective: Embedding DL-Lite^N_bool and related fragments into QL1 yields NP-, P-, and NLogSpace-completeness results for combined satisfiability.The translations preserve satisfiability, and the target fragments of QL1 determine the corresponding upper bounds.
- First-order perspective: Satisfiability of DL-Lite^N_bool and DL-Lite_bool knowledge bases is NP-complete for combined complexity.This follows from the QL1 embedding and the ability of DL-Lite_bool to encode full propositional logic.
- First-order perspective: Satisfiability of core and Krom variants is NLogSpace-complete, while Horn variants are P-complete for combined complexity.These bounds apply to the indicated DL-Lite^N fragments and are obtained through the corresponding QL1 fragments.
6. Instance Checking: Data Complexity
This section distinguishes combined from data complexity and reduces reasoning over DL-Lite knowledge bases to first-order model checking. It establishes tight data-complexity bounds for satisfiability, instance checking, and related extensions.
- Data complexity treats only the ABox as input, whereas combined complexity treats the entire knowledge base as input.
- The reduction represents the ABox as a first-order model and constructs a TBox-dependent formula whose satisfaction is equivalent to knowledge-base satisfiability.The formula depends on the TBox but not on the ABox.
- Satisfiability and instance checking for DL-Lite_N^bool are in AC0 for data complexity.
- Role transitivity raises satisfiability and instance checking for DL-Lite_core to NLogSpace-hard for data complexity.The lower bound follows by encoding directed-graph reachability.
- Satisfiability and instance checking for DL-Lite(HN)+^bool with transitivity are NLogSpace-complete for data complexity.
- Instance checking and query answering are coNP-hard for DL-Lite_HN^core and DL-Lite_HF^krom, while they are P-hard for DL-Lite_HF^core.
7. Query Answering: Data Complexity
This section analyzes positive existential query answering through untangled and minimal Herbrand models, then rewrites bounded-depth query evaluation into first-order formulas. The resulting complexity depends on the DL-Lite fragment.
- Positive existential query answering is known to be data-complete for coNP in DL-Lite_HN^bool and data-complete for P in DL-Lite_HN^horn.
- The paper's main result places positive existential query answering for DL-Lite_N^horn in AC0 for data complexity.
- For a query with k existential variables, it suffices to search the minimal model up to depth m0 = k + |role±(T)|.
- The construction represents bounded-depth tree paths by pairs consisting of an ABox root and a sequence of role labels.
- The first-order translation preserves concept and role satisfaction between the bounded-depth model and the ABox representation.
8. DL-Lite without the Unique Name Assumption
This section studies DL-Lite without the unique name assumption, including equality and inequality constraints. It shows that complexity is often preserved, but object identification and transitivity can raise data complexity.
- Without the unique name assumption, object names may denote the same domain element, and equality and inequality constraints can be added to the ABox.
- Equality reasoning is LogSpace-reducible to reasoning without equality constraints by replacing names with representatives of their equality classes.
- Combined satisfiability is NLogSpace-complete for DL-Lite_H^core, P-complete for DL-Lite_H^horn, and NP-complete for DL-Lite_H^bool, even with several role constraints.
- Without the unique name assumption, satisfiability and instance checking for DL-Lite_H^bool are in AC0, but equalities raise them to LogSpace-complete and transitivity to NLogSpace-complete.
- With number restrictions, equality and inequality constraints make satisfiability NP-complete for both combined and data complexity across all four DL-Lite fragments.
- For functional-role fragments, satisfiability is P-complete for core, Krom, and Horn, while the Boolean fragment is NP-complete combined and P-complete for data complexity.
- Positive existential query answering for DL-Lite_H^horn remains in AC0 with several role constraints and inequalities, becoming LogSpace-complete when equalities are allowed.
9. Conclusion
The paper maps the computational boundaries of 40 extended DL-Lite logics across five orthogonal features and identifies how specific construct combinations affect reasoning complexity. Its results clarify when first-order rewritability and tractable reasoning are preserved, and where added constraints increase complexity.
- Interactions among constructs: Under the UNA without role inclusions, number restrictions do not increase reasoning complexity; without number restrictions, role inclusions are likewise compatible with UNA-insensitive complexity determined by concept inclusions.These observations isolate the combinations that preserve the core complexity behavior.
- Data complexity: In both preceding cases, instance checking is in AC0 for data complexity, corresponding to first-order rewritability.This supports the DL-Lite goal of efficient query access over large data.
- Data complexity: Without the UNA, and without disjunctions or role inclusions, functionality makes instance checking P-complete for data complexity, suggesting reducibility to Datalog.The result marks a concrete boundary for the tractability of functionality constraints.
- Role constraints: Role disjointness, symmetry, and asymmetry can be added without changing complexity, while transitivity raises data complexity of instance checking and query answering to NLogSpace-hardness.Combined satisfiability complexity remains unchanged under transitivity.
- Open problems and limitations: The paper identifies open scope around additional constructs, deeper interaction analyses, equality handling, and practical alternatives for query processing.Equality can lose first-order rewritability, while supplementary databases require updates whenever the ABox changes.