The description logic EL has been used to support ontology design in various domains, and especially in biology and medicine. EL is known for its efficient reasoning and query answering capabilities. By contrast, ontology design and query answering can be supported and guided within an FCA framework. Accordingly, in this paper, we propose a formal transformation of ELI (an extension of EL with inverse roles) ontologies into an FCA framework, i.e. KELI , and we provide a formal characterization of this transformation. Then we show that SPARQL query answering over ELI ontologies can be reduced to lattice query answering over KELI concept lattices. This simplifies the query answering task and shows that some basic semantic web tasks can be improved when considered from an FCA perspective.
Relying on Semantic Web (SW) languages and principles, several ontologies have been created in various domains, especially, in biology and medicine. In addition to that, since the conception of linked data publishing principles, over 295 linked (open) datasets have been produced1. Querying these data is mainly done through the W3C recommended query language SPARQL2.
In parallel, knowledge discovery in data represented by means of objects and
their properties can be done using formal concept analysis (FCA) [
In this work, we focus particularly on E LI (an extension of E L with inverse
roles) ontologies. E L is one of OWL 2 profiles (OWL 2 E L). In fact, OWL 2
E L is used mainly for designing large biomedical ontologies such as
SNOMEDCT3, and the NCI thesaurus4. A common feature of these ontologies is that they
possess large concept hierarchies that can be queried with SPARQL. Answering
SPARQL queries is done by binding variables of the query into terms of the
queried ontology. However, including inferred data in the query answers requires
either a reasoner to infer all implicit data or query rewriting using regular
expression patterns (that enable navigation in a hierarchy) [
Overall, in this paper, we work towards (i) a formal characterization of the translation of ontologies into a formal context, (ii) minimizing the difficulty of SPARQL query answering over ontologies into LQL (Lattice Query Language) query answering over concept lattices, and finally (iii) providing organization of SPARQL query answers with the use of concept lattices.
Outline: after presenting the basics of E LI, SPARQL and FCA (§2), we show how to transform E LI ontologies into formal contexts (§3). We then present a query language for concept lattices called LQL (§4). Therefore, SPARQL query answering over E LI ontologies can be reduced to LQL query answering over KELI concept lattices (§5). Finally, we present the related works (§6) along with a summary of concluding remarks (§7). 2
In this section, we provide a very brief and intuitive introduction of the
description logic E LI and FCA. For a detailed discussion, we refer the readers
to [
In E LI, classes are inductively defined from a set NC of class names, a
set NR of role names, and a set NI of individual names (NC, NR, and NI are
finite), using the constructors: >, C u D, and ∃R.C are classes. Where C and D
refer to classes, R refers to a role name or its inverse R−, and in the assertion
C(a), a refers to an individual. In this paper, we consider ∃R.C classes with
C ∈ NC, i.e, C is an atomic concept in the expression of ∃R.C. The TBox of
a E L knowledge base contains a set of class inclusion axioms such as C v D.
The ABox contains class and role assertions: C(a) and R(a, b). The semantics
of E LI is broadly discussed in [
SPARQL is a W3C recommended query language [
A SPARQL SELECT query can be formed according to the following syntax: SELECT W FROM O WHERE {q}. The FROM clause identifies the queried ontology O on which the query will be evaluated, WHERE contains a query pattern q that the query answers should satisfy and SELECT singles out the answer variables W ∈ V from the query pattern. For this work, we consider only AND and UNION SPARQL queries.
A formal context represents data using objects, attributes, and their
relationships. Formally, it is a triple K = (G, M, I) where G a set of objects, M
a set of attributes, and I ⊆ G × M is a relation. A derivation operator (0) is
used to compute formal concepts of a context. Given a set of objects, the
operator derives common attributes of these objects and vice versa. A set of formal
concepts ordered with the set inclusion relation form a concept lattice [
In the next section, we show the transformation of E LI ontologies into formal contexts. 3
Transforming E LI Ontologies into Formal Contexts
In the following, we introduce some terms and notions that we use.
Materialization (closure) refers to computing the deductive closure of an ontology
(alternatively, making all implicitly stored data explicit by using inference) [
Motivation Example 1. Consider the following ELI ontology O = hT , Ai:
T = {ActorsFromNewYork v Actor, FilmProducer v Artist,
Actor v Artist, Artist v Person}
A = {tomCruiseI ∈ ActorsFromNewYorkI } In order to compare graphical representations of DL ontologies and their corresponding concept lattices, we represent O and its respective materialization O0 as graphs as shown below:
tomCruise FilmProducer
Starting with Example 1, one can ask whether it is possible to obtain a formal context from the ontology O while maintaining its semantics. The problem here is that DLs and FCA work on different assumptions, i.e, while DL languages are based on the open world assumption (OWA), FCA relies on the closed world assumption (CWA). The former permits to specify only known data whereas the later demands all data should be explicitly specified. To slightly close the gap between these two worlds: – one can generate the formal context from the closure of the ontology. However, this approach fails when it is not possible to compute the closure of the ontology as this is the case for ontologies created from a DL language equipped with negation and disjunction constructs5, and – before transforming the ontology into a formal context, complete the ontology. A drawback of the second approach is that it adds unnecessary data, consequently, giving unwanted results when querying. 5 http://www.w3.org/TR/owl2-primer/ Person
Artist FilmProducer
Actor To this end, our main objective is to come up with an approach which transforms an ontology into a formal context while maintaining the semantics. Accordingly, a formal context corresponding to the ontology in Example 1 has an associated lattice that looks like the one in Figure 1a. From this onwards, when we speak of this lattice, we refer to it as the target lattice. The target lattice maintains the semantics because: the class hierarchy of the ontology (TBox) is the same as that of the lattice, and the instance (ABox) and schema (TBox) part of the ontology are treated separately as discussed in Section 3.2.
In the following, we provide various formal contexts associated with the ontology in Example 1. For the sake of readability, we shorten concept and individual names as: ActorsFromNewYork (AFNY), FilmProducer (Prd), Actor (Act), Artist (Art), Person (Per), and tomCruise (tC). Consider the following transformations:
AFNY Prd Act Art Per
tC
x
x
x
x
x
This formal context is obtained from the materialized ABox of the ontology. It
does not include subclass relations as they can be acquired using attribute
exploration [
(b)
This formal context is produced by taking all the subclass hierarchy of all
atomic concepts C and all nominal concepts {a} for all individuals a.
Formally, a formal context is constructed using: (i) aI ∈ CI into {a}, C ∈ G, M ,
and ({a}, {a}), (C, C), ({a}, C) ∈ I, and (ii) C v D into C, D ∈ G, M , and
(C, D), (C, C), (D, D) ∈ I. The context is a transformation of the materialized
ontology (both the closures of the ABox and TBox are computed as depicted in
the right-hand graph of Example 1). The concept lattice of this formal context
is shown in Figure 2a. As it can be seen, it does not maintain the semantics
because the concept hierarchy is different from that of our target lattice (in
Figure 1a). In other words, the concept hierarchy of the concept lattice is different
from that of the ontology (in Example 1). Everything is mixed: attributes are
also objects and vice versa. Obviously, it is possible to find several other ways of
transforming an ontology into a formal context. To avoid any semantic loss, we
propose an another approach, where we separately manage the transformation
of ABox and TBox assertions. In FCA, attribute exploration is used to discover
implicit knowledge. In that, given a concept lattice, a domain expert is asked a
series of questions to produce implications that correspond to DL like inclusion
axioms. Ontologies contain instance and schema data, where the latter is similar
to implications of concept lattices. Hence, when transforming, individuals in the
ABox to become objects and concept names to become attributes, besides,
assertions in the ABox are transformed into relations. Additionally, class inclusions
of the TBox become background implications. The overall transformation
procedure leads to a formal context with respect to existing knowledge (this is also
known as background implications according to [
Proposal To transform a E LI knowledge base KB = hT , Ai into a formal context K = (G, M, I), the schema axioms in the TBox become background implications L((G, M, I)) and the ABox assertions become objects, attributes and relations. To elaborate, in K, individuals in the ABox constitute objects G, class names in the ABox and TBox yield attributes in M , and ABox assertions create relations between objects and attributes I ⊆ G × M . Here, we consider acyclic TBoxes so as to avoid class names becoming objects in a context.
Definition 2 (Transforming E LI Ontologies into Formal Contexts). We define the transformation of KB = hT , Ai into a formal context (G, M, I) thanks to a transformation function σ as follows: – An axiom C v D in T corresponds to an implication in L((G, M, I)), i.e., the set of implications based on (G, M, I): C v D 7−→ C → D ∈ L((G, M, I)). – Concept expressions C (class name), ∃R.C, and ∃R−.C, correspond respectively to attributes C, ∃R.C, and ∃R−.C in M . – An individual a in A corresponds to an object a in G. – When a is an instance of C resp. ∃R.C, ∃R−.C, then (a, C) ∈ I resp.
(a, ∃R.C) ∈ I, (a, ∃R−.C) ∈ I.
– When a is related to b through R, then (a, ∃R.>) ∈ I and (b, ∃R−.>) ∈ I. Example 2. The translation of the ontology in Example 1 into a formal context K and its background implications L are shown below:
K AFNY Prd Act Art Per tC x
L = { AFNY → Act, Prd → Art,
Act → Art, Art → Per }
Construction of concept lattices: there are several algorithms that can compute
concept lattices associated with a formal context. Some of these are discussed
in the literature [
Next we show that concept lattices associated with E LI ontologies can be queried by LQL – lattice query language.
SPARQL query answering over E LI ontologies can be considered as lattice query answering over KELI concept lattices. To do this, we need to introduce a query language for concept lattices. Each node in a lattice can be seen as a query formed by a conjunction of: a concept intent and a concept extent. Intuitively, querying concept lattices amounts to fetching the objects given a set of attributes as query constants, alternatively, fetching the attributes given a set of objects as query constants or terms. Query terms can be connected using the logical operators: AND and OR to form a complex term. A term is either a set of objects called object term (OT) or a set of attributes called attribute term (AT). Definition 3 (Object and Attribute Terms). Given a formal context K = (G, M, I), an object term (OT) and an attribute term (AT) are defined inductively as:
OT = {g} | OT1 AND OT2 | OT1 OR OT2, where g ∈ G
AT = {m} | AT1 AND AT2 | AT1 OR AT2, where m ∈ M The expression OT1 AND OT2 denotes the greatest lower bound (GLB) in the concept lattice B(G, M, I). The expression OT1 OR OT2 denotes the least upper bound (LUB) in B(G, M, I). Dually, the expression AT1 AND AT2 denotes the GLB in the concept lattice B(G, M, I) (keeping the orientation of B(G, M, I) based on the extents). Finally, the expression AT1 OR AT2 denotes the LUB in B(G, M, I).
Based on the definitions of object and attribute terms, we introduce LQL queries. In this paper, we do not address the problem of negation in the query (and thus set difference).
Definition 4 (LQL - Lattice Query Language). Given an object term OT, an attribute term AT, and variables x, y ∈ V where V is a finite set of variables, an LQL query can take the following forms:
q(y) = (OT, y); q(x) = (x, AT); q() = (OT, AT ) q(y), q(x), and q() do not necessarily correspond to formal concepts, only when OT and AT are closed sets. If OT is a closed set in q(y) = (OT, y), then y corresponds to the intent associated with OT. The same thing happens with x when AT is a closed set in q(x) = (x, AT). For evaluating x and y in every possible case we do the following: – if OT = {g}, then y = {g}0, i.e., all attributes that are associated with the object g. – if OT = {g1} AND {g2}, then y = {g1, g2}0 – if OT = {g1} OR {g2}, then y = {g1}0 ∪ {g2}0 Similarly, the evaluation of q(x) = (x, AT) is given as follows: – if AT = {m}, then x = {m}0, i.e., all objects that are associated with the attribute m. – if AT = {m1} AND {m2}, then x = {m1, m2}0 – if AT = {m1} OR {m2}, then x = {m1}0 ∪ {m2}0 Finally, the evaluation of q() = (OT, AT) is:
– true if OT = AT0 or AT = OT0 and false otherwise.
Example 3. Let us consider querying the concept lattice shown in Figure 3. – For q1(x) = (x, {actor} AND {comedian} AND {writer}), we have x = {J errySeinf eld}. – q2(x) = (x, {writer} OR {director}), we have x = {DavidSchwimmer,
W illSmith, J errySeinf eld}. – q3(y) = ({J ustinT imberlake} AND {W illSmith}, y), we have y = {actor, musician}. – q4(y) = ({DavidSchwimmer} OR {J ustinT imberlake}, y), we have y = {actor, director, musician}.
The complexity of answering LQL queries is polynomial in the size of the formal context, i.e., O|(G, M, I)|. The advantage of LQL over SPARQL is that, it allows to compute the least upper bound and greatest lower bound of query answers. We now present one important part of this work which is reducing SPARQL query answering over ELI ontologies into LQL query answering over KELI concept lattices.
Recently, SPARQL has been extended with different entailment regimes and
regular path expressions6. The semantics of SPARQL relies on the definition of basic
graph pattern matching that is built on top of simple entailment [
? x WHERE {? x a A r t i s t . }
Under simple entailment evaluation of a SPARQL query, the answers of Q over
O is empty, i.e., Q(O) = ∅. For the reason that, simple entailment is based on
graph matching which requires the variable ?x in the query to be bound with a
term in the graph. Since there is no term where it can be bound to, the result is
empty. However, under higher entailment regimes (such as the RDFS entailment
[
? x WHERE {? x a /v∗ A r t i s t . } This query Q0 selects all instances of Artist and that of its subclasses by navigating through the subclass relation (v∗). The rewriting can be evaluated over O to obtain Q0(O) = {tomCruise}.
In summary, materialization requires a reasoner to expand the knowledge base, the complexity of this task depends on the type of the schema language. On the other hand, query rewriting requires modifying query patterns using SPARQL 6 http://www.w3.org/TR/sparql11-query/ property paths. This also results in a further jump in the complexity of query answering.
As described above, unlike SPARQL query answering over ontologies, query answering over a concept lattice is relatively easier. Due to the fact that once the concept lattice is obtained from the ontology, LQL can be used to query the lattice. Consequently, alleviating those expensive tasks. The above SPARQL query can be converted into an LQL query as: q(x) = (x, Artist). The evaluation of this query over a concept lattice obtained from O is as expected Q0(O) = {tomCruise}.
The complexity of SPARQL query answering over E LI ontologies is larger than that of LQL query answering over KELI concept lattices. Since, the expressive power of SPARQL is superior than that of LQL. For E LI ontologies a query language like LQL is sufficient to retrieve individuals (or objects) and classes (or attributes). 6
To date, several studies have been carried out to assess the relevance and
benefits of FCA for DL [
In this work, firstly, we have proposed a formal transformation of E LI ontologies into formal contexts. This enables to benefit from some advantages that FCA may offer to the DL world. Then we have shown that SPARQL query answering over E LI ontologies can be considered as lattice query answering over KELI concept lattices. This alleviates some reasoning and query rewriting tasks that are required for SPARQL query answering.
Moreover, even if there already exist substantial work relating DL, semantic web and FCA, there remains a lot of research work to be carried out. Such a research work is concerned with the correspondence between concept lattices from FCA and DL-based class hierarchies, query answering and information retrieval, and scalability as well. In addition, as FCA could benefit from DLbased reasoning capabilities, semantic web and DL-driven applications can take advantage of FCA-based ontology design, data analysis and knowledge discovery capabilities of FCA.
In the future, we plan to extend and experiment with the proposed approach. We will investigate how well it scales, given the size of ontologies.