Introduction
In the field of Description Logics (DL), knowledge bases are traditionally constructed using a "top-down" approach where human experts define concepts. However, "bottom-up" knowledge engineering—where definitions are automatically generated from examples—is increasingly important for practical applications. This process relies on two fundamental operations: the Most Specific Concept (msc), which identifies the most detailed description for a single individual, and the Least Common Subsumer (lcs), which identifies the most specific description covering a set of concepts.
A significant challenge arises in the logic $\mathcal{EL}$ when individuals are involved in circular relationships. In such cases, the msc may not exist as a finite, tree-like description. This paper by Franz Baader addresses this limitation by introducing cyclic terminologies and greatest fixpoint semantics to ensure the existence and tractability of these operations.
Syntax and Semantics of $\mathcal{EL}$
The logic $\mathcal{EL}$ is a foundational description logic that supports conjunction and existential restrictions. It is widely utilized in large-scale medical ontologies, such as SNOMED CT, due to its favorable balance between expressivity and computational efficiency.
In standard $\mathcal{EL}$, concepts are interpreted as sets of individuals, and roles as binary relations. The "bottom-up" approach seeks to find concepts $C$ such that an individual $a$ is an instance of $C$ ($a \in C^\mathcal{I}$), where $C$ is as specific as possible.
The Challenge of Cycles
When an ABox (assertional knowledge) contains cycles—for instance, a relationship where "individual $a$ is related to $b$ via role $r$, and $b$ is related back to $a$ via $r$"—a standard tree-like description of $a$ would be infinitely deep. In traditional $\mathcal{EL}$ without cyclic TBoxes (terminological knowledge), the msc of such an individual does not exist as a finite concept.
Methodology: Graphs and Simulations
To overcome the existence problem, Baader proposes embracing cyclic terminologies (TBoxes) and interpreting them using greatest fixpoint (gfp) semantics. Under gfp-semantics, a concept can be defined by its position in a cycle, allowing the logic to capture infinite structures within finite definitions.
The paper represents these terminologies and individuals using description graphs, where nodes correspond to concepts or individuals and edges represent roles.
By mapping the logic to graph theory, the author utilizes simulation relations to determine subsumption. If one graph can "simulate" another, the corresponding concept is more specific. The lcs of two concepts is then computed using a product graph of their respective description graphs.
Key Results and Complexity
The primary contribution of the paper is proving that under gfp-semantics, both the msc and lcs are guaranteed to exist in $\mathcal{EL}$ with cyclic TBoxes. Furthermore, the paper establishes several critical results:
- Guaranteed Existence: Under gfp-semantics, the msc of an individual and the lcs of concepts are always well-defined in $\mathcal{EL}$ with cyclic TBoxes.
- Polynomial Complexity: The binary lcs (for two concepts) and the msc can be computed in polynomial time. This ensures that the bottom-up construction of knowledge bases remains computationally feasible for large datasets.
- Tractability vs. Value Restrictions: The paper notes a sharp contrast with logics like $\mathcal{FL}_0$ (which use value restrictions). In those logics, cycles make the mathematical treatment significantly more difficult, whereas in $\mathcal{EL}$, they remain manageable.
Conclusion
Franz Baader's work provides a robust mathematical framework for bottom-up knowledge engineering in $\mathcal{EL}$. By treating cycles as a feature rather than a limitation and leveraging graph-based algorithms, the paper demonstrates that complex, circular relationships can be formally and efficiently described. While the size of the lcs for multiple concepts can still grow exponentially, the guaranteed existence and polynomial time for binary operations mark a major advancement for practical DL applications.
Summary updated