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 buys is the data complexity, which is where the size actually lies.

Symbols.

Metatheory. FO-rewritable. AC⁰ data complexity for conjunctive query answering; NP-complete in combined complexity, the hardness inherited from query evaluation rather than from the ontology. TBox reasoning is PTIME. Complete for ontology-based data access.

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

Limitations. Very limited expressiveness. No qualified restrictions. No conjunction in subsumption. Tradeoff for tractability.

© 2026 Lingenic LLC