Glossary

📍 Where we are: The back-of-the-book reference for all of Volume 2 — every recurring term of symbolic reasoning, in plain words. Keep it open in a second tab and come back whenever a word stops making sense.

Symbolic reasoning has a precise vocabulary, most of it inherited from logic and databases and then sharpened here around one small academic world. Below are the volume's recurring terms, in plain language, listed alphabetically so they are easy to find. Each entry is a starting point; the chapter it points to gives the full, exact picture.

ABox — the assertion box: the ground facts about named individuals, split into concept assertions like Professor(alice) and role assertions like advises(alice, bob). The data half of a knowledge base; the academic world's has 13 concept and 18 role assertions over 13 individuals. (See TBox and ABox: Schema versus Data.)

ABox / TBox split — the clean division of a knowledge base into data and schema: the ABox states facts about individuals ("alice is a professor"), the TBox states axioms about kinds ("every professor is a researcher"). Reasoning is the act of joining the two. (See TBox and ABox: Schema versus Data.)

Allen's interval algebra — the classification proving that any two time intervals stand in exactly one of thirteen basic relations (before, meets, overlaps, during, starts, finishes, their six inverses, and equals); the backbone of qualitative temporal reasoning. (See Temporal Reasoning: Allen's Algebra and PyReason.)

Annotated logic — logic whose facts carry a label drawn from a lattice — a confidence in [0,1], a time interval, a provenance token — and whose rules combine those labels as they fire; the crisp true/false fixpoint engine runs over the richer values unchanged. (See Annotated Logic: Intervals, Lattices, and Confidence.)

Basic concept — the leaf pieces a normal-form axiom is allowed to contain: a concept name, ⊤ (top), or ⊥ (bottom), with no constructor stacked on top. (See Normalization: Reducing to Normal Forms.)

Canonical model — one interpretation built directly from a reasoner's saturated tables that both satisfies the TBox and falsifies every subsumption the rules did not derive; the witness that turns "not derived" into "not entailed," and so proves completeness. (See Soundness and Completeness: Why the Rules Suffice.)

Certain answer — a query answer that holds in every model of the knowledge base, not merely in one; under the open world this is the only kind of answer a reasoner may assert, and only tuples of real constants (alice, bob) qualify. (See Certain Answers: Query Answering as Homomorphism.)

Chase (oblivious / restricted) — forward chaining for existential rules: match a rule body and mint a fresh null for each thing the head says must exist. The oblivious chase fires on every match; the restricted chase skips a firing when a witness already exists, so it invents fewer nulls and halts on more inputs. (See Existential Rules and the Chase.)

Completion rule — one of the fixed inference rules — CR1–CR4, the bottom rule CR⊥, and the role-chain rule — that an EL reasoner fires over its subsumer and edge ledgers; iterated to a fixpoint, they compute the entire class hierarchy. (See Completion Rules: CR1–CR4 and the Bottom Rule.)

Concept — a class of things, a unary predicate: Professor, Student, Researcher. The first of description logic's three vocabularies, alongside roles and individuals. (See Description Logic: Concepts, Roles, and Individuals.)

Concept assertion — an ABox fact placing a named individual in a class, written C(a) — Professor(alice); drawn in a graph as a type edge from an individual up to its class. (See TBox and ABox: Schema versus Data.)

Confidence lattice — the interval [0,1] ordered by ≤, with meet ⊓ = min (a conjunction is only as strong as its weakest link) and join ⊔ = max (the best of several derivations wins); the value space annotated logic reasons over. (See Annotated Logic: Intervals, Lattices, and Confidence.)

Conjunction (⊓) — the concept constructor for "in both classes at once": C ⊓ D denotes the individuals that belong to C and to D. One of EL's three building blocks. (See Description Logic: Concepts, Roles, and Individuals.)

Consequence-based reasoning — deciding entailment by deriving entailed consequences forward until a round adds nothing (a saturation), with no hypothesis to refute and no backtracking; the paradigm behind the EL completion algorithm and reasoners like ELK. (See Consequence-Based Reasoning: PTIME Classification.)

Datalog — function-free Horn logic: a finite set of rules "head :- body" whose only terms are constants and variables, given meaning by a least-fixpoint loop. The common ancestor of forward chaining, EL completion, and the query engines behind real knowledge graphs. (See Datalog: Rules, the T_P Operator, and Least Fixpoint.)

Description logic (DL) — a decidable fragment of first-order logic built from concepts, roles, and individuals and closed under a small, carefully chosen set of constructors that restrict how quantifiers nest; the formal language behind OWL and the ontologies of this volume. (See Description Logic: Concepts, Roles, and Individuals.)

Disjointness — the axiom that two concepts cannot overlap, written C ⊓ D ⊑ ⊥ ("nothing is both a professor and a student"); it needs the bottom concept, and is how a DL states a genuine negative. (See The EL Family: Small Logic, Big Ontologies.)

EL — the lightweight description logic with exactly three constructors: conjunction (⊓), existential restriction (∃r.C), and top (⊤). No negation, disjunction, or universal restriction — the omissions that keep reasoning polynomial. (See The EL Family: Small Logic, Big Ontologies.)

EL++ — EL extended with the bottom concept (hence disjointness), role inclusions and role chains, nominals, and an ABox; still tractable, and the logic behind the OWL 2 EL profile that the academic world implicitly inhabits. (See The EL Family: Small Logic, Big Ontologies.)

Existential restriction (∃) — the constructor ∃r.C, "related by role r to at least one member of C"; EL's one way to reach across a role, as in ∃advises.Student, "someone who advises a student." (See Description Logic: Concepts, Roles, and Individuals.)

Existential rule (TGD) — a rule, formally a tuple-generating dependency, whose head asserts that something exists without naming it; firing it invents a fresh individual, which is exactly what lets the chase run forever. (See Existential Rules and the Chase.)

Fixpoint — a set the immediate-consequence operator leaves unchanged: fire every rule once more and nothing is added. Forward chaining, completion, and the chase all stop precisely when they reach one. (See Datalog: Rules, the T_P Operator, and Least Fixpoint.)

General concept inclusion (GCI) — a TBox axiom C ⊑ D, "everything in C is in D," satisfied by an interpretation when C's set sits inside D's and entailed when that holds in every model; the hierarchy Professor ⊑ Researcher ⊑ Person is three of them. (See Description Logic: Concepts, Roles, and Individuals.)

Homomorphism — a variable assignment that lands every atom of a query pattern onto a real atom of the data; the single primitive underneath both conjunctive-query evaluation and the chase's "is this already satisfied" test. (See Certain Answers: Query Answering as Homomorphism.)

Immediate-consequence operator (T_P) — one sweep of forward chaining: fire every rule whose body currently holds and add all the resulting heads. It is monotone, so iterating it from the empty set climbs to a least fixpoint. (See Datalog: Rules, the T_P Operator, and Least Fixpoint.)

Individual — one specific named thing the knowledge base talks about (alice, p1, mit); a constant, and the third of description logic's three vocabularies. (See Description Logic: Concepts, Roles, and Individuals.)

Knowledge graph — a database of facts drawn as a labelled directed graph: individuals are the nodes and relations are the labelled edges, so a set of triples is a graph. The symbolic object reasoning composes and closes. (See Triples and Graphs: Facts as a Network.)

Least fixpoint (lfp) — the smallest set closed under the immediate-consequence operator, equal to the limit of iterating it from the empty set; for a Datalog program it is the least model — everything the rules force and nothing more. (See Datalog: Rules, the T_P Operator, and Least Fixpoint.)

Normal form (NF1–NF4) — the four allowed axiom templates every EL TBox is rewritten into — A ⊑ B, A₁ ⊓ A₂ ⊑ B, A ⊑ ∃r.B, and ∃r.B ⊑ A — with every slot a basic concept; the shapes the completion rules are built to match. (See Normalization: Reducing to Normal Forms.)

Normalization — rewriting a TBox so that every axiom is one of the four normal forms (plus role chains), coining fresh names for compound subconcepts along the way; a conservative step that adds no new consequences over the original vocabulary. (See Normalization: Reducing to Normal Forms.)

Null — a labeled null, a placeholder symbol (_n1) standing for a forced-but-unnamed individual the chase invented; disjoint from every real constant, so a query answer containing one is never certain, because different models fill it differently. (See Existential Rules and the Chase.)

Open-world assumption (OWA) — the DL/OWL default: an unstated, unentailed fact is unknown, not false, so a claim counts as true only if it holds in every model. The reason a reasoner abstains rather than guessing. (See Open-World and Inconsistency: Abstention and Repair.)

OWL 2 profile (EL / QL / RL / DL) — the official syntactic fragments of the Web Ontology Language, each trading expressive power for a tractable guarantee: EL for classification, QL for query rewriting, RL for rule engines, and full DL (the logic SROIQ) for maximum expressivity with no tractability promise. (See OWL 2 Profiles: EL, QL, RL, and DL.)

Provenance semiring — an algebra (K, ⊕, ⊗, 0, 1) whose values label facts with where they came from: ⊗ combines the inputs of a rule body, ⊕ combines alternative derivations, and the fixpoint loop threads these labels so a derived fact records the sources and paths it depends on. (See Provenance Semirings: Where Facts Come From.)

Role — a binary relation between individuals (advises, cites, affiliatedWith); the second of description logic's three vocabularies, and what existential restrictions reach along. (See Description Logic: Concepts, Roles, and Individuals.)

Role assertion — an ABox fact linking two named individuals under a role, written r(a,b) — advises(alice, bob); drawn in a graph as a data edge between the two individuals. (See TBox and ABox: Schema versus Data.)

Role chain — a complex role inclusion r ∘ s ⊑ t, "an r-step then an s-step counts as a t-step," as in advises ∘ advises ⊑ grandAdvisor; a feature of EL++ that plain EL lacks. (See Description Logic: Concepts, Roles, and Individuals.)

Saturation — firing a fixed set of inference rules over the current facts, round after round, until a whole pass adds nothing; the completion algorithm's fixpoint, and the same loop as forward chaining under a different name. (See Completion Rules: CR1–CR4 and the Bottom Rule.)

Soundness and completeness — the two halves of a correct reasoner: soundness derives only entailed consequences (it never guesses), completeness derives every entailed consequence (it never misses one). Together they make the derived hierarchy exactly the set of true subsumptions. (See Soundness and Completeness: Why the Rules Suffice.)

Subsumption — the core DL reasoning task: deciding whether one concept is necessarily contained in another, C ⊑ D, in every model of the TBox; computing all such relations between named concepts is classification. (See Description Logic: Concepts, Roles, and Individuals.)

TBox — the terminology box: the schema-level axioms about concepts and roles, naming no individual (every professor is a researcher; advising twice is grand-advising). The academic world's has 14. (See TBox and ABox: Schema versus Data.)

Triple — an ordered (subject, predicate, object) such as (alice, advises, bob); the atomic unit of symbolic knowledge, and one labelled edge of a knowledge graph. (See Triples and Graphs: Facts as a Network.)

Unsatisfiable concept — a concept forced to ⊥, so it can have no instance in any model (TenuredStudent, once professor and student are declared disjoint); a modelling error the reasoner catches rather than a fact about the world. (See The EL Family: Small Logic, Big Ontologies.)

If a term here still feels fuzzy, follow it back into the chapter where it lives, and it will make far more sense in context.