DL-Lite

Origin. Calvanese et al. (2007). Lightweight description logic. Polynomial query answering. Foundation for OWL 2 QL. Designed for databases with ontologies.

Models. Restricted expressiveness for tractability. Conjunctive query answering in AC⁰. First-order rewritable. Ontology-based data access.

Formalism.

DL-Lite_core: Concepts: A, ∃R, ∃R⁻ Left side of inclusion: B ::= A | ∃R | ∃R⁻ Right side: C ::= B | ¬B Inclusions: B ⊑ C

DL-Lite_R (with roles): Role inclusions: R ⊑ S Disjointness: Disj(R, S) Role inverses.

DL-Lite_F (functional roles): (funct R): R is functional At most one R-successor.

Restrictions: No full existentials ∃R.C No conjunction on left of ⊑ No universal ∀R.C

Query answering: Input: TBox T, ABox A, query q Output: certain answers cert(q, T, A) Answers true in all models.

First-order rewritability: Query q over T rewrites to FOL query q'. cert(q, T, A) = eval(q', A) Use SQL on database.

Complexity: TBox reasoning (satisfiability, subsumption): PTIME Conjunctive query answering: AC⁰ in data complexity Conjunctive query answering: NP-complete in combined complexity The NP-hardness is inherited from plain relational query evaluation — evaluating a conjunctive query against a database is already NP-complete when the query counts toward the input — so it is not a cost the ontology imposes. What DL-Lite improves is the data complexity, which is where the size actually lies.

Symbols.

Symbol	Unicode	Name	Meaning
∃	U+2203	Existential	Unqualified: has some R-successor
⁻	U+207B	Superscript minus / Inverse	Converse of a role
⊑	U+2291	Inclusion	Concept or role subsumption
¬	U+00AC	Negation	Admitted only on the right of ⊑
⁰	U+2070	Superscript zero	Level marker in the circuit class AC⁰
::=	—	BNF definition	Grammar for basic and general concepts
\|	—	Alternation	Separates alternatives in the grammar
Disj	—	Role disjointness	The two roles share no pair
funct	—	Functionality	At most one R-successor
cert	—	Certain answers	Tuples holding in every model of the KB
eval	—	Evaluation	Running the rewritten query on the ABox as a database
AC⁰	—	Circuit class	Constant depth, unbounded fan-in; where FO evaluation sits

Metatheory. DL-Lite is sound and complete for the standard interpretation semantics, and certain answers coincide with the answers over a canonical model obtained by chasing the ABox with the TBox. That model is generally infinite, but a conjunctive query cannot look arbitrarily deep into it, which is what makes rewriting possible. Calvanese, De Giacomo, Lembo, Lenzerini and Rosati (2007) proved first-order rewritability: the PerfectRef algorithm turns a conjunctive query q and a TBox T into a union of conjunctive queries q′ depending on q and T alone, so that cert(q, T, A) = eval(q′, A) with the ABox treated as a plain relational instance. Since q′ is first-order, data complexity is in AC⁰ and no reasoner is invoked at query time; combined complexity is NP-complete, inherited from ordinary conjunctive query evaluation rather than imposed by the ontology, while TBox satisfiability and subsumption are polynomial. Combining functionality with role inclusions without restriction destroys rewritability, which is why DL-Lite_A forbids specialising a functional role. DL-Lite_R underlies OWL 2 QL.

Applies to. OWL 2 QL. Database integration. SPARQL over relational. Large-scale ontologies. Enterprise data.

Limitations. The expressiveness is minimal by construction. Existential restrictions are unqualified — ∃R is available, ∃R.C is not — so "has a child who is a student" cannot be written. Conjunction is barred from the left of an inclusion, universal restriction is absent, and negation occurs only on the right, so the logic states disjointness but nothing requiring case analysis. There is no transitivity and no transitive closure, so reachability is outside the language. Each of qualified existentials, left-hand conjunction, and unrestricted functionality combined with role inclusions costs first-order rewritability, the one property the family exists to protect. The AC⁰ result is data complexity alone: the rewriting can produce a union of conjunctive queries exponentially larger than the input query, so the cost reappears in the size of the SQL sent to the database.