Ontology Languages

Origin. The Knowledge Interchange Format (Genesereth and Fikes, 1992) and Ontolingua supplied a first-order interlingua for sharing ontologies but no decidable reasoning. The Semantic Web line began with RDF and RDF Schema, passed through SHOE, OIL and DAML+OIL (2001), and produced OWL as a W3C Recommendation in 2004, deliberately built on description logic so that each species could be given a known complexity bound. OWL 2 followed in 2009, adding qualified cardinality, property chains, keys and a richer datatype map, and introducing three tractable profiles. Common Logic (ISO/IEC 24707, 2007) carries the unrestricted first-order tradition forward alongside.

Models. An ontology is a vocabulary equipped with a model theory: classes denote subsets of the domain, properties denote binary relations on it, individuals denote elements, and axioms constrain which interpretations count as models. The reasoning tasks are subsumption, classification, consistency and instance retrieval. Two assumptions distinguish an ontology from a database schema: the world is open, so a missing assertion is unknown rather than false, and names are not assumed to denote distinct things.

Formalism.

Vocabulary: Class(C) ObjectProperty(R), DataProperty(U) Individual(a)

Class axioms: SubClassOf(C, D) EquivalentClasses(C, D) DisjointClasses(C, D)

Class constructors: C ⊓ D (intersection) C ⊔ D (union) ¬C (complement) ∃R.C (some values from) ∀R.C (all values from) ≥n R.C, ≤n R.C (qualified cardinality) {a, b, c} (enumeration / nominals) ∃R.Self (self restriction, OWL 2)

Property axioms: SubPropertyOf(R, S) SubPropertyChainOf(R ∘ S, T) (OWL 2) InverseOf(R, S) TransitiveProperty(R), SymmetricProperty(R) FunctionalProperty(R), InverseFunctionalProperty(R) ReflexiveProperty(R), IrreflexiveProperty(R), AsymmetricProperty(R) Domain(R, C), Range(R, D) HasKey(C, R) (OWL 2)

Individual axioms: ClassAssertion(C, a) PropertyAssertion(R, a, b) SameIndividual(a, b) DifferentIndividuals(a, b)

Species and their description logics: OWL Lite ≈ SHIF(D) OWL DL ≈ SHOIN(D) OWL 2 DL ≈ SROIQ(D) OWL Full / OWL 2 Full: no layering, undecidable.

OWL 2 profiles: OWL 2 EL ≈ EL++: polynomial classification. OWL 2 QL ≈ DL-Lite_R: first-order rewritable, query-optimized. OWL 2 RL: forward-chaining rule implementation.

Two semantics for OWL 2: Direct Semantics: on OWL 2 DL, DL model theory. RDF-Based Semantics: on all of RDF, undecidable. Correspondence theorem links them one way only.

Open world: Unknown ≠ false. No unique name assumption. Distinctness must be asserted.

Symbols.

Metatheory. The OWL family is layered over description logic, so each species inherits the metatheory of the logic beneath it. Under the Direct Semantics an ontology is read as a DL knowledge base over interpretations I = (Δᴵ, ·ᴵ), and reasoning is sound and complete for that reading. OWL Lite corresponds to SHIF(D) and is ExpTime-complete — its name was a poor guide to its cost; OWL DL corresponds to SHOIN(D) and is NExpTime-complete; OWL 2 DL corresponds to SROIQ(D) and is N2ExpTime-complete (Kazakov 2008). The three OWL 2 profiles trade expressiveness for tractability along different axes: OWL 2 EL is EL++, with polynomial classification (Baader, Brandt and Lutz 2005); OWL 2 QL is DL-Lite_R, first-order rewritable with AC⁰ data complexity; OWL 2 RL is designed so that forward chaining over a fixed rule set computes the ground consequences in polynomial data complexity. OWL 2 also carries an RDF-Based Semantics defined over all of RDF, where entailment is undecidable; the correspondence theorem guarantees only that Direct-Semantics entailments carry into it, not the converse.

Applies to. Semantic Web. Biomedical ontologies. Enterprise knowledge. Data integration. AI reasoning.

Limitations. The layering that secures decidability is fragile. OWL Full and the RDF-Based Semantics let one name denote a class, a property and an individual at once and allow classes to be members of classes; both are undecidable, and OWL 2 DL recovers decidability only by punning, keeping the several denotations formally separate. The profiles are not closed under union: an ontology in OWL 2 EL combined with one in OWL 2 QL can lie in no profile, so tractability is a property of a given ontology and not compositional. Reasoning is open-world and monotone, so nothing follows from an absent assertion, defaults and exceptions cannot be stated, and distinctness of individuals must be asserted pair by pair. Properties are binary, so n-ary relations require reification. Datatypes enter only through a restricted, decidability-preserving map, with no arithmetic or aggregation over them, and unrestricted rules over variables, as in full SWRL, are undecidable.

© 2026 Lingenic LLC