OWL 2 Profiles: EL, QL, RL, and DL

📍 Where we are: Part II · Description Logic — Chapter 6. The EL Family showed one small logic — conjunction and existentials — classifying enormous terminologies in polynomial time; now we zoom out and ask why the standard ships four such dialects and how to choose among them.

The Web Ontology Language (OWL, the W3C standard for writing machine-readable ontologies) is, underneath, a description logic — and a very expressive one. Expressive logics are slow to reason in, sometimes ruinously so. So the standard does something pragmatic: alongside the full language it defines three smaller, official sub-languages called profiles, each a deliberately restricted fragment tuned so that one particular reasoning task runs fast with a mathematical guarantee [1]. This chapter is about those three profiles — EL, QL, and RL — plus the full DL language they carve out of, and about the single skill that matters: picking the right one for the job in front of you.

The simple version

Imagine a print shop with three specialist machines and one do-everything workhorse. One machine only prints giant catalogues, but does it blindingly fast. One only fills in mail-merge forms straight from a spreadsheet. One only stamps items on a fast assembly line. The workhorse in the corner can print anything — but you never know whether a job will take a minute or a week. OWL 2's profiles are the three specialists: each is limited on purpose so that its one job is guaranteed quick. Full OWL 2 DL is the workhorse. You choose a profile by the task you must do quickly, not by which language feels most powerful.

What this chapter covers

• A profile is a bargain — you give up expressive constructors and get back a worst-case guarantee on one task; you pick by the task, not by taste.
• EL, the terminology profile — conjunction and existentials only; classification in polynomial time; the logic of SNOMED CT and of the academic world.
• QL, the database profile — the DL-Lite core; answers conjunctive queries by rewriting them into SQL, so a database does the work; first-order rewritable, ideal over huge data.
• RL, the rule profile — a fragment that maps axiom-for-rule onto a forward-chaining Datalog engine, connecting straight to the rule reasoning of Part IV.
• A side-by-side table — constructors kept and dropped, the efficient task, the complexity class, and the typical use, with the crucial fact that the profiles overlap but none contains another.
• Where the academic world lands — its real TBox uses ⊓, ∃, ⊥, and a role chain, so it lives in OWL 2 EL; we quote the axioms and name exactly which ones would exile it from QL and RL.
• Why the lines fall where they do — the honest answer is computational complexity, which the next chapter opens up.

A profile is a bargain: expressivity traded for a guarantee

Start from the thing being cut down. Full OWL 2 (its logical core is the description logic $\mathcal{SROIQ}$) piles up constructors: conjunction ⊓, disjunction ⊔, negation ¬, universal ∀ and existential ∃ restrictions, number restrictions, inverse roles, role chains, and nominals. That richness is why deciding whether one class subsumes another in the full language is worst-case N2ExpTime-complete [1] — a doubly-exponential blow-up, the kind of cost that can make a single query outlive the person who asked it.

A profile is a syntactic restriction: a grammar that says which constructors may appear, and where they may appear — to the left of a ⊑, to its right, or in either position. The bargain is exact. You promise to write only axioms the grammar allows; in return the standard promises a complexity class for one reasoning task. Formally, if $\mathcal{L}$ is the fragment and $\mathrm{task}$ its guaranteed-cheap job, membership in the profile buys you a bound

$$\text{axioms} \in \mathcal{L} \quad\Longrightarrow\quad \mathrm{task} \in \mathcal{C},$$

where the arrow $\Longrightarrow$ reads "guarantees" and $\mathcal{C}$ is a tractable complexity class (PTIME, or lower). Three profiles exist because there are three different jobs worth guaranteeing — classifying a terminology, querying a database, running a rule engine — and no single fragment makes all three cheap at once. The next three sections take them one at a time.

OWL 2 EL: conjunction, existentials, polynomial classification

EL is named for its two core constructors: existential restriction and conjunction (as a logic it is written $\mathcal{EL}$, and its standardized extension $\mathcal{EL}^{++}$ is the profile's real basis). Read its concept grammar as: a concept is an atomic name $A$, the top concept ⊤ ("everything"), the bottom concept ⊥ ("nothing"), a conjunction $C \sqcap D$ ("both a $C$ and a $D$"), or an existential $\exists r.C$ ("related by role $r$ to some $C$"):

$$C, D \;::=\; A \;\mid\; \top \;\mid\; \bot \;\mid\; C \sqcap D \;\mid\; \exists r.C .$$

That is the whole language of concepts — no ∀, no ¬, no ⊔. EL's distinctive strength is that it allows conjunction ⊓ and qualified existentials $\exists r.C$ freely on both sides of a ⊑. The right-hand existential — being able to conclude Professor ⊑ ∃advises.Student ("every professor advises some student"), not merely assume it — EL shares with QL; what QL cannot match is EL's left-hand richness: a qualified existential or a conjunction in the subclass position, where QL admits only a bare $\exists r.\top$. (The head-existential itself is banned only by RL, as we will see.) The companion module states the design intent directly (ontology.py lines 28–30):

EL (the logic behind the OWL 2 EL profile) keeps exactly ⊓ and ∃, which is why
subsumption stays decidable in *polynomial* time — the pay-off the completion
algorithm in ``el_completion.py`` cashes in.

The guarantee is the headline: in EL, deciding subsumption ($A \sqsubseteq B$, "is every $A$ necessarily a $B$?") and classifying the entire ontology is PTIME-complete — solvable in time bounded by a polynomial in the size of the TBox [2]. The mechanism that cashes that in is the completion (or saturation) algorithm: normalize every axiom to one of four fixed shapes, then fire a small set of completion rules until a fixpoint. The from-scratch reasoner in el_completion.py (rules CR1 through CRχ, lines 25–30) is exactly this, and its docstring is blunt about the reward (lines 38–40): the algorithm "runs in time polynomial in the size of the TBox — the property that makes OWL 2 EL usable on ontologies with hundreds of thousands of concepts (SNOMED CT, the Gene Ontology)." SNOMED CT (Systematized Nomenclature of Medicine — Clinical Terms), with over 350,000 concepts, is an OWL 2 EL ontology because EL is the profile whose classification cost stays polynomial as the terminology grows. So is the academic world, as we will confirm below.

OWL 2 QL: DL-Lite and answering queries by rewriting

QL points at "query" — its purpose is answering conjunctive queries (the database-style "find all $x$ such that…" pattern-match) over ontologies whose data sits in a large relational database. Its logical basis is DL-Lite, a family engineered so that a query never forces the reasoner to touch the data at all [3]. QL is spare on the left of a ⊑ — the subclass position allows only an atomic name or an unqualified existential $\exists r.\top$ ("has some $r$-successor at all") — but it adds inverse roles ($r^-$) and negation on the right, and it forbids two things EL loves: conjunction on the left, and role chains.

The trick QL buys with that restraint is first-order rewritability. Given a conjunctive query $q$ and a QL TBox $\mathcal{T}$, the reasoner rewrites $q$ into a new (usually larger) first-order query $q_{\mathcal{T}}$ — a union of conjunctive queries, i.e. plain SQL — such that for every ABox $\mathcal{A}$ the certain answers over the ontology equal the answers of the rewritten query run directly on the data as an ordinary database:

$$\mathrm{cert}(q, \mathcal{T}, \mathcal{A}) \;=\; \mathrm{ans}(q_{\mathcal{T}}, \mathcal{A}).$$

Read this as: fold all the ontological reasoning into the query once, then let the database engine answer it with no reasoner in the loop. The consequence is a complexity result at the very bottom of the scale. Measured in data complexity (the cost as a function of the ABox size, holding the query and TBox fixed), conjunctive query answering in QL is in $\mathrm{AC}^0$ [3] — the class of problems a fixed first-order query already lives in, which sits below LOGSPACE and far below PTIME. That is precisely the complexity of evaluating a SQL statement, which is why QL is the profile of choice for ontology-based data access: put a lightweight ontology on top of a billion-row database and every query still runs at database speed.

OWL 2 RL: the rule-friendly fragment

RL points at "rule." It is the fragment whose axioms translate, one for one, into Datalog rules — Horn clauses a forward-chaining engine can fire — so an RL ontology is reasoned over by exactly the immediate-consequence loop of Part IV, no description-logic reasoner required. Its restrictions mirror that target. RL is generous on the left of a ⊑ (the body of a rule): it allows conjunction, and existentials that bind the role's successor. It even permits the universal ∀ on the right (a valid rule: everything reached by $r$ from a $C$ is a $D$). But it is strict on the one thing that would break the translation: RL forbids an existential $\exists r.C$ in the superclass position — the head of the rule.

The reason is the same one the Fixpoints chapter met as the chase: an axiom like Professor ⊑ ∃advises.Student in the head demands that every professor have an advisee, and if none is on record a rule engine would have to invent a fresh anonymous individual — which forward chaining over Datalog cannot do. Ban head-existentials and every axiom becomes a safe rule whose body reads existing facts and whose head asserts a fact about existing individuals. RL reasoning is then just Datalog evaluation: PTIME-complete in data complexity, implementable on any forward-chaining rule/Datalog engine (industrial ones such as RDFox), and scaling to graphs with billions of edges by the same least-fixpoint climb you already know.

Three profiles, side by side

Here is the whole bargain in one view. Each row is a profile; the columns are the constructors it keeps, the constructors it drops, the task it makes cheap, the resulting complexity, and where it earns its keep.

Profile	Logic	Keeps	Drops	Efficient task	Complexity	Typical use
EL	$\mathcal{EL}^{++}$	⊓, ∃ on both sides, ⊥, role chains, ABox	∀, ¬, ⊔, inverse roles, cardinality	classification / subsumption	PTIME-complete	large terminologies (SNOMED CT, Gene Ontology)
QL	DL-Lite	∃r.⊤ on the left, ∃r.C and ¬ on the right, inverse roles	⊓ on the left, role chains, qualified ∃ on the left	conjunctive query answering	$\mathrm{AC}^0$ (data), first-order rewritable	querying huge databases
RL	DLP / pD*	⊓ and ∃ in bodies, ∀ in heads, ⊥, role chains	∃ in the head (superclass position)	rule / Datalog reasoning	PTIME-complete (data)	scalable rule reasoning over instance data
DL	$\mathcal{SROIQ}$	(almost) everything	— the full language	— no tractability guarantee	N2ExpTime-complete	maximal expressivity

The most important fact about this table is easy to miss: the three tractable profiles overlap, but none contains another [1]. Role chains live in EL and RL but not QL. Inverse roles live in QL and RL but not EL. Existentials in the head live in EL and QL but not RL — RL alone forbids them. So there is no "biggest" tractable profile you could always default to; each is a genuinely different corner of the full language, and an ontology can sit in one, two, all three, or none of them. That is the sense in which you choose by the task: the profiles are not a ladder of power but three tools with different edges.

Where the academic world lands

Now place our running example. The ontology reports its own shape (ontology.py, summary, lines 216–220):

10 named concepts, 6 roles, 14 TBox axioms; ABox: 13 concept assertions, 18 role assertions over 13 individuals.

Printing the TBox (ontology.py, the axioms at lines 125–174) shows exactly which constructors it leans on:

Professor ⊑ Researcher
Student ⊑ Researcher
Researcher ⊑ Person
Professor ⊑ ∃advises.Student
∃advises.⊤ ⊑ Researcher
Professor ⊓ Student ⊑ ⊥
advises ∘ advises ⊑ grandAdvisor
Dean ⊑ Professor
Dean ⊑ ∃advises.Professor
TenuredStudent ⊑ Professor
TenuredStudent ⊑ Student
TenuredStudentAdvisor ⊑ ∃advises.TenuredStudent
∃advises.∃authored.Paper ⊑ Person
Person ⊓ ∃authored.Paper ⊑ Researcher

Run your eye down the constructors: subclass chains ($A \sqsubseteq B$), conjunction (Professor ⊓ Student, Person ⊓ ∃authored.Paper), existentials on both the right (Professor ⊑ ∃advises.Student) and the left (∃advises.⊤ ⊑ Researcher, ∃advises.∃authored.Paper ⊑ Person), the bottom concept ⊥ for disjointness, one role chain (advises ∘ advises ⊑ grandAdvisor), and an ABox of concept and role assertions. Every one of those is an $\mathcal{EL}^{++}$ constructor, and nothing here is anything else — no ∀, no ¬, no ⊔, no inverse role. The academic world is an OWL 2 EL ontology. That is why the polynomial completion reasoner in el_completion.py decides it outright, saturating to a fixpoint in three rounds and reading off the classification:

saturation reached a fixpoint in 3 rounds
  round : |S| |R|  (derived subsumers, derived role pairs)
      0 :  23   0
      1 :  34   7
      2 :  39   7
      3 :  39   7

The role chain is not idle decoration: among the seven derived role pairs, the completion prints grandAdvisor: [('Dean', 'Student'), ('TenuredStudentAdvisor', 'Student')] — pairs produced only by firing advises ∘ advises ⊑ grandAdvisor. That single axiom is the sharpest fault line to QL, which has no role chains at all. Now the instructive part: which axioms would exile this ontology from the other two tractable profiles?

• It would fall out of QL on three counts. The role chain advises ∘ advises ⊑ grandAdvisor (line 147) is flatly outside DL-Lite — QL has no role chains. The left-hand conjunctions Professor ⊓ Student ⊑ ⊥ (line 143) and Person ⊓ ∃authored.Paper ⊑ Researcher (line 173) put a ⊓ in the subclass position, which QL forbids so that queries stay first-order rewritable. (This is a syntactic point, not lost power: QL can still state the disjointness itself as Professor ⊑ ¬Student, since negation is a legal QL superclass — it is only this particular ⊓-on-the-left form that QL rejects.) And the qualified left-existential ∃advises.∃authored.Paper ⊑ Person (line 168) breaks QL too — the subclass position wants a bare $\exists r.\top$, not a qualified filler.
• It would fall out of RL on the head-existentials. Professor ⊑ ∃advises.Student (line 133), Dean ⊑ ∃advises.Professor (line 152), and TenuredStudentAdvisor ⊑ ∃advises.TenuredStudent (line 163) each assert existence in the superclass position, and a Datalog rule cannot invent the required advisee. The role chain, by contrast, is fine for RL — RL keeps property chains — so it is the existentials in the head alone that block it.

The disjointness axiom is the tidiest illustration of the overlap-but-no-containment picture: Professor ⊓ Student ⊑ ⊥ is native to EL and expressible in RL, yet its left-conjunction form is illegal in QL (which would have to rephrase the same disjointness as Professor ⊑ ¬Student). One tiny written axiom, legal in two profiles and not the third.

The full OWL 2 DL language with its three tractable profiles as overlapping regions, each tagged by the one task it makes efficient, and the academic world pinned inside EL with the exact axioms that would push it out of QL and RL. Original diagram by the authors, created with AI assistance.

The unsolved part

The profiles look like three arbitrary lines drawn through one language — keep ⊓ but drop ∀ here, allow ∃ on the left but not the right there. Why these lines? The honest answer this chapter cannot fully give is that the boundaries are not chosen for elegance; they are the exact frontiers at which a reasoning task tips from tractable to intractable. Adding a single forbidden constructor back can move classification from PTIME to ExpTime, or move query answering out of $\mathrm{AC}^0$ so that no SQL rewriting exists and a database engine can no longer answer for you. The open, deeper question is why one extra constructor should cost so much — why the cliffs sit precisely where the profile grammars put their fences. That is not a question about syntax at all; it is a question about computational complexity, and it is the subject of the next chapter.

Why it matters

For neuro-symbolic AI, the profiles are a lesson in engineered guarantees that the neural side conspicuously lacks. A learned model gives you an answer of unstated cost and unstated correctness; an OWL 2 EL ontology gives you a promise — classification in polynomial time, sound and complete — that holds no matter how the terminology grows. When later volumes bolt a learner onto a reasoner, the profile is what fixes the reasoner's half of the contract: choose EL and you can classify a learned or extended ontology at scale; choose QL and you can answer queries over learned assertions at database speed; choose RL and your symbolic layer is literally a differentiable-friendly rule engine. Knowing which profile a task needs is knowing which guarantee you get to keep when you add the neural part — and which constructors you must not let creep back in if you want to keep it.

Key terms

• Profile — an official syntactic fragment of OWL 2 (EL, QL, or RL) restricted so one reasoning task has a tractable worst-case guarantee.
• OWL 2 EL — the fragment of conjunction ⊓ and existential ∃ (logic $\mathcal{EL}^{++}$); classification is PTIME-complete; the profile of SNOMED CT and the academic world.
• OWL 2 QL — the DL-Lite fragment; conjunctive query answering is first-order rewritable, so queries reduce to SQL over the raw data, in $\mathrm{AC}^0$ data complexity.
• OWL 2 RL — the rule fragment; axioms map to Datalog rules run by forward chaining, PTIME-complete in data complexity; bans existentials in the head.
• OWL 2 DL — the full language (logic $\mathcal{SROIQ}$); maximally expressive but N2ExpTime-complete, with no tractability guarantee.
• First-order rewritability — the property (QL's) that a query plus TBox can be rewritten into a plain first-order/SQL query answered directly over the ABox, $\mathrm{cert}(q,\mathcal{T},\mathcal{A}) = \mathrm{ans}(q_{\mathcal{T}},\mathcal{A})$.
• Data complexity — cost measured as the ABox grows, with the query and TBox held fixed; the yardstick that separates QL ($\mathrm{AC}^0$) from RL and EL (PTIME).
• Overlap but no containment — the three tractable profiles share constructors pairwise, yet none is a superset of another, so you cannot pick a single most-powerful one.

Where this leads

Every claim in this chapter — polynomial here, $\mathrm{AC}^0$ there, doubly exponential for the full language — was quoted as a fact and left unexplained. The next chapter, The Complexity of Reasoning, makes those complexity classes precise and shows why the profile boundaries fall exactly where they do: what it means for subsumption to be PTIME-complete, why one extra constructor can trigger an exponential blow-up, and how the same completion loop that classified the academic world in three rounds is the concrete reason EL earns its polynomial promise. The profiles are the what; complexity is the why.