Building and maintaining ontologies is a laborious task, especially for large domains, where knowledge engineers and domain experts work together to transfer their knowledge into an explicit representation. In Description Logic, the ABox of an ontology is usually filled with observed symbolic data but constructing the TBox is a more complex endeavor. Assistance by automated or interactive methods is often valuable. To this end, we reconsider the Formal-Concept-Analysis-based approach to completely axiomatizing ℰℒ⊥ concept inclusions ⊑ from graph data [3, 4] and 1. thoroughly revise and simplify its technical description including proofs, 2. equip it with support for already known concept inclusions satisfied in the data (thus enabling it for ontology completion), 3. analyze its computational complexity, 4. explain how further types of TBox statements supported by ℰℒ++ that are not just syntactic sugar can be completely axiomatized, viz. role inclusions 1 ∘ · · · ∘ ⊑ and range restrictions ⊤ ⊑ ∀., 5. describe how it can be implemented eficiently, 6. introduce variations that dispense with the computation of disjointness statements 1 ⊓ · · · ⊓ ⊑ ⊥ or extremely large concept inclusions without practical relevance, thereby rendering the approach applicable in practice, albeit some completeness is lost, 7. and evaluate the implementation on real-world datasets. Formal Concept Analysis (FCA) [5] is a mathematical theory that represents data as formal contexts in which objects are described by their attributes. These attributes are similar to atomic statements in propositional logic and unary predicates in first-order logic. The canonical implication base is a complete set of implications, i.e. it entails all implications satisfied in the data [6, 7], and no complete set with fewer implications exists [8, 9]. In other words, the implication base axiomatizes data in form of a formal context by means of implications. We employ the description logic ℰℒ++ [10], but we ignore nominals to avoid overfitting in the axiomatization method and concrete domains (datatypes for strings, numbers, etc.) as no ℰℒ++ reasoner currently supports them. The Web Ontology Language includes ℰℒ++ as the profile OWL 2 EL. By exploiting the similarity between concept inclusions and FCA implications, a complete TBox of concept inclusions can be axiomatized from observed data, i.e. which entails all concept inclusions satisfied in the data. More specifically, as input we expect graph data in form of an interpretation ℐ, which includes knowledge graphs, graph databases, and RDF data: the concept names are the node labels and the role names are the edge labels. Preprocessing of a knowledge graph might be necessary, e.g. to correctly treat the metadata as well as to materialize the modelling conventions [11]. Further given may be an already existing TBox consisting of concept inclusions satisfied in ℐ and relative to which ℐ is to be
axiomatized, or rather, of which we compute a completion w.r.t. ℐ. The axiomatization result is called a concept inclusion base or a completion in the following sense. [1, Definition 4]. A TBox is complete for ℐ if it entails all concept inclusions satisfied in ℐ. A concept inclusion base of ℐ relative to is a TBox ℬ of which ℐ is a model and such that ℬ ∪ is complete for ℐ. We may also call ℬ a completion of w.r.t. ℐ as we obtain a complete TBox by adding all concept inclusions in ℬ to .
A canonical completion of w.r.t. ℐ can be computed in exponential time [1, Theorem 10] (see below). This complexity result is tight since there are finite interpretations without any polynomial-size base. 1 Moreover, if all concept inclusions in come in a particular normal form, then no base with fewer concept inclusions exists. In order to eficiently treat cycles in the input (both contained in ℐ or induced by ), the concept inclusions are formulated in an extension of ℰℒ⊥ that allows for non-tree-shaped concept descriptions. To obtain a usual ℰℒ++ TBox, the canonical concept inclusion base afterwards needs to be rewritten using variables.
In order to compute the canonical completion, the given interpretation ℐ is transformed into a formal
context Kℐ . Its finite attribute set M is specifically designed such that there is a concept inclusion base
involving only conjunctions over M, i.e. which consists of inclusions d C ⊑ d D for subsets C, D ⊆ M
[1, Lemma 9]. This setting is perfectly suited for FCA since all necessary computations happen in the
top-level conjunctions and there is no need to look inside the concept descriptions provided by M
(which FCA could not do anyway). In particular, we first use an eficient FCA algorithm [
Moreover, the formal context Kℐ is axiomatized relative to the implication set ℒℐ, . On the one hand, ℒℐ, contains the implication {} → { } for each two concept descriptions , ∈ M with ⊑∅ , viz. to avoid the axiomatization of tautological concept inclusions. On the other hand, the given TBox is taken into account by transforming all its inclusions into implications over M and adding these to ℒℐ, . [1, Theorem 10]. For each finite interpretation ℐ and each ℰℒs⊥i TBox of which ℐ is a model, the TBox Can(ℐ, ) := d Can(Kℐ , ℒℐ, ) is a concept inclusion base of ℐ relative to . It is called canonical concept inclusion base and can be computed in time that is exponential in Dom(ℐ) and polynomial in . If all concept inclusions in have the form ⊑ [ℐℐ], then it contains the fewest inclusions among all concept inclusion bases of ℐ relative to . Furthermore, there are finite interpretations that have no polynomial-size concept inclusion base.
In addition to concept inclusions, ℰℒ++ further supports role inclusions and range restrictions. The latter can easily be read of from the input: for each role name , we first compute the most specific concept description that has all -successors in ℐ as instances and we then add the range restriction ⊤ ⊑ ∀. to the TBox.
All role inclusions can be completely axiomatized by viewing ℐ as a finite automaton. Specifically
for objects , in ℐ we denote by A, the automaton with initial state and final state . Now a role
inclusion 1 ∘ · · · ∘ ⊑ is not satisfied in ℐ if. there are objects , in ℐ with (, ) ∈ (1 ∘ · · · ∘ )ℐ
but (, ) ̸∈ ℐ . By definition, (, ) ∈ (1 ∘ · · · ∘ )ℐ if. the automaton A, accepts the word 1 · · · .
So, the complement automaton of the union automaton of all A, with (, ) ̸∈ ℐ accepts the word
1 · · · if. the role inclusion 1 ∘ · · · ∘ ⊑ is satisfied in ℐ. Like for the concept inclusions, we
use variables to formulate the axiomatized role inclusions: ∘ ⊑ for each transition (, , ), and
⊑ for each initial state, and ⊑ for each final state. It is decidable whether there are equivalent
1Since each formal context can be seen as an interpretation without role names, this is an immediate corollary to a result in
FCA: there is a sequence of formal contexts with 3· objects and 2· +1 attributes for which the number of implications in
their canonical implication bases is exponential in [
A technical limitation is that completeness does not go together with the syntactic restriction on
the interplay of role inclusions and range restrictions in an ℰℒ++ TBox that ensures tractable
reasoning [
To ensure that the TBox is within ℰℒ++, we could weaken the range restrictions: for each role name , we obtain a suitable range restriction ⊤ ⊑ ∀. by computing the most specific concept description that has all -successors in ℐ as instances (as above) but also all -successors for each role name leading to a final state (since these represent role inclusions · · · ∘ ⊑ ).
Alternatively, we could remove all role inclusions that contribute to a violation of the syntactic restriction (by simply computing a language diference in the above automaton representation) and leave the range restrictions unchanged. To sum up, only two of the following goals can be achieved: the base satisfies the syntactic restriction, the base is complete for all range restrictions, the base is complete for all role inclusions.
Regarding eficient implementation, it is important to reduce the input interpretation by grouping together all objects that cannot be distinguished by any concept description. Thereby the interpretation can be made significantly smaller and all subsequent steps need less time. However, in first experiments several computations did not finish due to extremely large concept descriptions used in the concept inclusion base to ensure completeness. We conjecture that such huge parts in the concept inclusion base do not have practical relevance or sufer from overfitting, and thus we added parameters (conjunction size limit and role depth bound) to dispense with the computation of these irrelevant huge parts but also to control the loss of completeness. Experiments further revealed that often more than half of the computation time is required for generating disjointness statements 1 ⊓ · · · ⊓ ⊑ ⊥. We explain how intermediate computation steps can be stopped early in order to avoid computing them.
We implemented the method in the programming language Scala and we evaluated the prototype with the plethora of ontologies from real-world applications used in the ORE 2015 Reasoner Competition. This collection is split into OWL 2 EL and OWL 2 DL ontologies. The former are all expressible in ℰℒ++. For the latter, we syntactically transform as many axioms as possible into ℰℒ++ and remove the others. The goal then was to compute, for each such ontology, the completion of the TBox w.r.t. the interpretation ℐ obtained by viewing the respective ABox under closed-world assumption. To ensure that ℐ is a model of , we saturate ℐ by means of the inclusions in if necessary. Altogether we obtained 614 test datasets with up to 747,998 objects, of which 446 (72.64 %) are acyclic. The average number of triples per object varies from slightly over 0 up to 25.39. Computation of concept inclusion bases finished for all reduced datasets with no more than 100 objects. For reduced datasets with up to 1,000 objects, the first errors due to insuficient computing resources occurred without restrictions. Between 1,000 and 10,000 objects, computations failed without restrictions, but otherwise succeeded in the majority of cases. Reduced datasets with more than 10,000 objects could only sometimes be axiomatized with very restricted settings, given 8 hours time and 80 GB memory on a twelve-year-old computer server. However, we did not implement the rewriting of the concept inclusion base into ℰℒ++, nor the axiomatization of role inclusions and range restrictions.
That the theoretical approach itself can be extended to more expressive description logics has already
been proven [
An interesting question for future research would be whether one can give any kind of completeness
guarantee if a conjunction size limit is used, as already done for the role depth bound [
Furthermore, the computation can be speed-up with even faster FCA algorithms for enumerating
closures. The employed FCA algorithm [
A concept inclusion ⊑ is confident if the ratio |( ⊓ )ℐ |/|ℐ | exceeds a pre-defined limit
but need not be 100 %. A confident inclusion base extends the canonical inclusion base [
We have not considered keys supported by the OWL 2 EL profile. Learning of keys from RDF data
using FCA has been addressed [
Acknowledgments This work has been supported by Deutsche Forschungsgemeinschaft (DFG) in Projects 430150274 (Repairing Description Logic Ontologies) and 389792660 (TRR 248: Foundations of Perspicuous Software Systems), and has further been supported by the Saxon State Ministry for Science, Culture, and Tourism (SMWK) by funding the Center for Scalable Data Analytics and Artificial Intelligence (ScaDS.AI). [9] Felix Distel. Learning description logic knowledge bases from data using methods from formal concept analysis. Doctoral thesis. Technische Universität Dresden, 2011. url: https : / / nbn resolving.org/urn:nbn:de:bsz:14-qucosa-70199.