The co-existence of heterogeneous but complementary data sources, such as ontologies and databases describing the same domain, is the reality of the Web today. In this paper we argue that this complementarity could be exploited both for discovering the knowledge not captured in the ontology but learnable from the data, and for enhancing the process of ontological reasoning by relying on the combination of formal domain models and evidence coming from data. We build upon our previous work on knowledge discovery from heterogeneous sources of information via association rules mining, and propose a method for automated reasoning on grounded knowledge bases (i.e. knowledge bases linked to data) based on the standard Tableaux algorithm. The proposed approach combines logical reasoning and statistical inference thus making sense of heterogeneous data sources.
From the introduction of the Semantic Web view [
Another common situation is when existing ontologies describe domain aspects that
(partially) complement data in a database. In this case the concepts of the ontologies are
linkable to views of the DB. Also in this case it would be very useful to be able to
combine the knowledge contained in the two information sources, for example for enriching
the existing ontologies. Due to the heterogeneity of the information a crisp
representation of the correspondence between the DB data and the classes and relations of the
ontologies (such as the one adopted in OBDA) is not possible. A more flexible connection
between the two sources of knowledge should be adopted. An option could be to exploit
rules that are able to express a statistical evidence of the connection between the data in
a DB and the knowledge in the ontology. For giving the intuition for this solution, let us
consider the following scenario. Given an existing ontology describing people gender,
family status and their interrelations with Italian urban areas1 and a demographic DB
describing Italian occupations, average salaries, etc., a possible connection between the
two information sources can be described with rules as follows:
“clerks between 35 and 45 years old living in a big city are male and
earn between 40 and 50 e” with a confidence value of 0.75.
(1)
where bold face terms correspond to classes and relations in the ontology, non bold
face terms correspond to data in the DB. The confidence value can be interpreted as the
probability that the specified connection between the two sources occurs. Rules of the
form (1) are called semantically enriched association rules. They have been introduced
in our previous work [
In this paper, we revise the approach introduced in [
AGE = [0, 16] ⇒ ¬P arent 0.99 can be exploited to conclude that, with high probability, x is not a P arent.
The rest of the paper is structured as follows. In Section 2 we give basic
definitions necessary to set up the framework. In Section 3 we summarize and extend the
approach for learning association rules from heterogeneous sources of information
pre1 The concepts “male”, “parent”, “big city”, “medium-sized town”, and the relations
”lives in” are used in the ontology.
sented in [
Let D be a non empty set of objects and f1, . . . , fn be n feature functions defined on every element of D, with fi : D → Di. D is called the set of observed objects and fi(d) for every d ∈ D is the i-th feature observed on d. Notationally we use d for the elements of D and d1, . . . , dn to denote the values of f1(d), . . . , fn(d).
Let Σ be a DL alphabet composed of three disjoint sets of symbols, ΣC , ΣR and ΣI , the set of concepts symbols, the set of role symbols and the set of individual symbols. A knowledge base on Σ, is a set K of DL inclusion axioms and DL assertions (we assume ALC as DL language here). The elements of K are called axioms of K. An axiom can be of the form X v Y , where X and Y are ALC (complex) concepts, or X(a) where X is a (complex) concept and a an individual symbol, or R(a, b), and a = b , where R is a role symbol and a and b are individual symbols. We call X v Y a subsumption, and X(a), R(a, b), and a = b assertions. K is formally defined as a couple K = hT , Ai where T contains the inclusion axioms (T stands for Terminological part) and A contains the assertional axioms (A stands for Assertional part).
An interpretation of a DL alphabet Σ is a pair I = ΔI , ·I such that ΔI is a
non empty set, and ·I is a function that assigns to each concepts name a subset of ΔI ,
to each role name a binary relation on ΔI , and to each individual an element of ΔI .
The interpretation function can be extended to complex concepts in the usual way [
The “glue” between a dataset and a knowledge base is the so called grounding, which is a relation that connects the objects of the knowledge base with the data of the database. More formally: a grounding g of Σ on D is a total function g : D → ΣI . This implies that for every d ∈ D there is at least an element a ∈ ΣI with g(d) = a. Intuitively g(d) = a represents the fact that the data d are about/correspond to object a of the knowledge base. Please note that the grounding g refers to objects that are explicitly mentioned in D and K respectively. In our framework (see Sect. 3) we assume that the grounding between D and K is already given. 3
Association rules (ARs), originally introduced in [
In this section we recall how ARs can be extended to include information coming
from an ontological knowledge base and how they can be used to bridge the knowledge
contained in an ontology with that contained in a relational database. These rules are
called semantically enriched ARs [
Association rules [
Ai1 = a1 ∧ . . . ∧ Aim = am θ ⇒ ϕ (2) where θ and ϕ are itemsets. The frequency of an itemsets θ, denoted by freq (θ), is the number of cases in D that match θ, i.e.
freq (θ) = |{d ∈ D | ∀(A = a) ∈ θ : fA(d) = a}| where fA is the feature function for d w.r.t. the attribute A (see beginning of Sect.2).
The support of a rule θ ⇒ ϕ is equal to freq (θ ∧ ϕ). The confidence of a rule θ ⇒ ϕ is the fraction of items in D that match ϕ among those matching θ: conf (θ ⇒ ϕ) = freq (θ ∧ ϕ) freq (θ) A frequent itemset expresses the variables and the corresponding values that occur reasonably often together.
In terms of conditional probability, the confidence of a rule θ ⇒ ϕ, can be seen as
the maximum likelihood (frequency-based) estimate of the conditional probability that
ϕ is true given that θ is true [
Let K be a knowledge base on Σ, D a dataset and g a grounding of Σ on D.
A semantically enriched itemset is a set containing statements of the form fi = a, C = tv, R = tv where, fi is an attribute of D, a a value in the range of fi, C is a concept name of ΣC and R is a role name of ΣR and tv is a truth value in {true, false, unknown}. The elements of the itemset of the form fi = a are called data items, the elements of the form C = tv and R = tv are called semantic items.
A semantically enriched AR is an association rules made by semantically enriched itemsets. This means that for a certain set of individuals, both knowledge coming from the ontology and information coming from the database are available (see Sect. 3.3 for more details).
Coherently with ARs, it is possible to define the frequency of a semantically enriched itemset and the support of a semantically enriched AR. Given a grounding g of Σ on D, the frequency of a semantically enriched itemset θ = θd ∧ θk (in the following also called mixed itemset) is the following generalization of the definition of frequency given for a standard itemset.
freq (θd ∧ θk) = |F | where F is the following set: F = ∀(fi = a) ∈ θd, fi(d) = a ∀(C = true) ∈ θk, K |= C(g(d)) ∀(C = false) ∈ θk, K |= ¬C(g(d)) d ∈ D ∀(C = unknown) ∈ θk, K 6|= C(g(d)) & K 6|= ¬C(g(d)) ∀(R = true) ∈ θk, K |= ∃R.>(g(d)) ∀(R = false) ∈ θk, K |= ¬∃R.>(g(d)) ∀(R = unknown) ∈ θk, K 6|= ∃R.>(g(d)) & K 6|= ¬∃R.>(g(d))
The support and confidence of a semantically enriched AR can be defined similarly. 3.3
In [
The approach for learning semantically enriched ARs is grounded on the assumption that a dataset D and an ontological knowledge base K share (a subset of) common individuals, and a grounding g of Σ on D is already available (see the end of Sect. 2 for more details on the grounding function). This assumption is reasonable in practice since, in the real world, there are several cases in which different information aspects concerning the same entities come from different data sources. An example is given by the public administration, where different administrative organizations have information about the same persons but concerning complementary aspects such as: personal data, income data, ownership data. Another example is given by the biological domain where research organizations have their own databases that could be complemented with existing domain ontologies.
The proposed framework is sketched in the following. To learn semantically enriched ARs from a dataset D and a knowledge base K grounded by g to D, all the 2 http://en.wikipedia.org/wiki/Web_Ontology_Language information about the common domain of K and D are summarized (proposizionalized) in a tabular representation constructed as follows: 1. choose the primary entity of interest in D or K for extracting association rules and set this entity as the first attribute A1 in the table T to be built; A1 will be the primary key of the table 2. choose (a subset of) the attributes in D that are of interest for A1 and set them as additional attributes in T; the corresponding values are be obtained as a result of an SQL query involving the selected attributes and A1 3. choose (a subset of) concept names {C1, . . . , Cm} in K that are of interest for A1 and set their names as additional attribute names in T 4. for each Ck ∈ {C1, . . . , Cm} and for each value ai of A1, if K |= Ck(ai) then set to 1 the corresponding value of Ck in T, else if K |= ¬Ck(ai) then set the value to 0, otherwise set to 1/2 the corresponding value of Ck in T 5. choose (a subset of) role names {R1, . . . , Rt} in K that are of interest for A1 and set their names as additional attribute names in T 6. for each Rl ∈ {R1, . . . , Rt} and for each value ai of A1, if ∃y ∈ K s.t. K |= Rl(ai, y) then set to 1 the value of Rl in T, else if ∀y ∈ K K |= ¬Rl(ai, y) then set the value of Rl in T to 0, otherwise set the value of Rl in T to 1/2 7. choose (a subset of) the datatype property names {T1, . . . , Tv} in K that are of interest for A1 and set their names as additional attribute names in T 8. for each Tj ∈ {T1, . . . , Tv} and for each value ai of A1, if K |= Tj (ai, dataValuej ) then set to dataValuej the corresponding value of Tj in T, set 0 otherwise.
It is straightforward to note that for all but the datatype properties, the Open World
Assumption is considered during the process for building the tabular representation.
Numeric attributes are processed (as usual in data mining) for performing data
discretization [
The choice of representing the integrated source of information within tables allows
for directly applying state of the art algorithms for learning association rules. Indeed,
once a unique tabular representation is obtained, the well known APRIORI algorithm [
Our goal is to set up a modified version of the Tableaux algorithm whose output, if
any, is the most plausible model, namely the model that best fits the available data. This
means to set up a data driven heuristic that should allow reducing the computational
effort in finding a model for a given concept and should be also able to supply the model
that is most coherent with/match the available knowledge. In this way the variance
due to intended diversity and incomplete knowledge is reduced, namely, the number
of possible models that could be built (see [
Given: D, K, the set R of ARs, a (possibly complex) concept E of K, the individuals x1, . . . , xk ∈ K that are instances of E, the grounding g of Σ on D Determine: the model Ir for E representing the most plausible model given the K, D, g and R.
Intuitively, the most plausible model for E is the one on top of the ranking of the possible models Ii for E. The ranking of the possible models is built according to the degree up to which the models respect the ARs. The detailed procedure for building the most plausible model is illustrated in the following.
In order to find (or not find) a model, the standard Tableaux algorithm exploits a
set of transformation rules that are applied to the considered concept. A
transformation rule for each constructor of the considered language exists. In the following, the
transformation rules for ALC logic are briefly recalled (see [
C2(x) THEN A = A ∪ {C1(x), C2(x)} t-rule: IF A contains (C1 t C2)(x), but it does not contain neither C1(x) nor C2(x)
THEN A1 = A ∪ {C1(x)}, A2 = A ∪ {C2(x)} ∃-rule: IF A contains (∃R.C)(x), but there is no individual name z s.t. C(z) and R(x, z) are in A THEN A = A ∪ {C(y), R(x, y)} where y is an individual name not occurring in A. ∀-rule: IF A contains (∀R.C)(x) and R(x, y), but it does not contain C(y) THEN A = A ∪ {C(y)}
To test the satisfiability of a concept E, the algorithm starts with the ABox A = E(x0) (with x0 being a new individual) and applies to the ABox the consistency preserving transformation rules reported above until no more rules apply. The result could be all clashes, which means the concept is unsatisfiable, or an ABox containing a model for the concept E that means the concept is satisfiable.
The transformation rule for the disjunction (t-rule) is non-deterministic, that is, a given ABox is transformed into finitely many new ABoxes. The original ABox is consistent if and only if one of the new ABoxes is so. In order to save the computational complexity, the ideal solution (for the case of a consistent concept) should be to choose the ABox containing a model directly. Moving from this observation, in the following we propose an alternative version of the Tableaux algorithm. The main differences with respect to the standard Tableaux algorithm summarized above are: 1. the starting model for the inference process is given by the set of all attributes (and corresponding values) of D that are related to individuals x1, . . . , xk that are instances of E differently from the standard Tableaux algorithm where the initial model is simply given by the assertion concerning the concept of which the satisfiability (or unsatisfiability) has to be shown, 2. a heuristic is adopted in performing the t-rule, differently from the standard case where no heuristic is given, 3. the most plausible model for the concept E and individuals x1, . . . , xk is built with respect to the available knowledge K, D and R. The obtained model is a mixed model, namely a model containing both information from R and K. Differently, in the standard Tableaux algorithm the model that is built only refers to K and does not take into account the (assertional) available knowledge.
In the following these three characteristics are analyzed and the way for accomplish each of them is illustrated. First of all, the way in which the starting model Ir is built is illustrated. For each xi ∈ {x1, . . . , xk}, all attribute names Ai related to xi are selected4 4 As an example the following query may be performed: SELECT * FROM hTABLE NAMEi
WHERE Ai = xi. Alternatively, a subset of the attributes in D may be considered. jointly with the corresponding attribute values ai. The assertions Ai(ai) are added to Ir. For simplicity and without loss of generality, a single individual x will be considered in the following. The generalization to multiple individuals is straightforward by simply applying the same procedure to all individuals that are (or assumed to be) instances of the considered concept.
Once the initial model Ir is built, all deterministic expansion rules, namely all but t-rule, are applied following the standard Tableaux algorithm as reported above. Instead, for the case of the t-rule, a heuristic is adopted. The goal of such a heuristic is twofold: a) choosing a new consistent ABox almost in one step to save computational complexity if E(x) is consistent (see discussion above concerning the t-rule); b) driving the construction of the most plausible model given K and R. The approach for the assessing the heuristic is illustrated in the following.
Let C t D be the disjunctive concept to be processed by t-rule. The choice on C rather than D (or vice versa) will be driven by the following process.
– The ARs (see Sect. 3.2) containing C (resp. D) or its negation in the semantic items of the right hand side of the rules are selected. – Given the model under construction Ir, the left hand side of each selected rule is considered and the degree of match is computed. This is done by counting the number of (both data and semantic) items in the left hand side of a rule that are contained in Ir, and averaging this number w.r.t. the length of the left hand side of the rule. Items with uncertain (unknown) values are not taken into account. The degree of match for the rules whose (part of the) left hand side is contradictory w.r.t. to the model is set to 0. – After the degree of match is computed, the rules having the degree of match equal to 0 are discarded. – For each of the remaining rules the weighted confidence value is computed as weightedConf = ruleConf idence ∗ degreeOf M atch. – Rules that have the degree of match below a given threshold (e.g. 0.75) are discarded. – The rule having the highest weighted confidence value is selected; in case of equal weighted confidence value of different rules, a random choice is performed. – If the chosen rule contains C = 1 (resp. D = 1) in the right hand side, the model under construction Ir is enriched with C(x) (resp. D(x)), where x is the individual under consideration. – If the chosen rule contains C = 0 (resp. D = 0) in the right hand side, the model under construction Ir is enriched with D(x) (resp. C(x)). – In the general case the right hand side of the selected AR may contain additional items besides that involving C or D. Assertions concerning such additional items will be also added in Ir accordingly5.
If there are no extracted ARs (satisfying a fixed confidence threshold) containing neither C or D in the right hand side, the following approach may be adopted. 5 If a most conservative behavior of the heuristic has to be considered only the assertion concerning the disjunct C (resp. D) will be added in Ir while the additional items in the right hand side of the selected rules are not taken into account.
Given Ir, a corresponding item set is created by transforming each assertion Ai(ai) referring to an attribute in D as a data item Ai = ai, each concept and role assertion to a knowledge item. Specifically, each positive (not negated) assertion is transformed in concept/role name = 1, each negative assertion is transformed in concept/role name = 0. Let θ be the conventional name of such a built itemset. Four rules, θ ⇒ C = 1, θ ⇒ C = 0, θ ⇒ D = 1 and θ ⇒ D = 0 are created and their confidence value is computed (see Sect. 3.2). Then, the rule having the highest confidence (satisfying a given confidence threshold) value is selected and the corresponding right hand side will be used as a guideline for expanding Ir.
The presented approach for the case in which no rules are available could result to be computationally expensive. As an alternative, the following criterion, grounded in the exploitation of the prior probability of C (resp. D) could be used. Specifically, the prior probability is computed, by adopting a frequency-based approach, as: P (C) = |ext(C)|/|A| where ext(C) is the extension of C, namely the number of individuals that are instances (asserted or derived) of C and | · | returns the cardinality of the set extension. Similarly P (D) can be defined for D. The concept to be chosen for extending Ir will be the one having the highest prior probability.
In the cases discussed above, the disjunctive expression is assumed to be made by atomic concept names. However, in ALC, more complex expressions may occur as part of a disjunctive expression as: existential concept restrictions (i.e. ∃R.A t ∃R.B), universal concept restrictions (i.e. ∀R.A t ∀S.B), nested concept expression (i.e. ∃R.∃S.A or ∃R.(A u B)). To cope with these cases a straightforward solution is envisioned: new concept names are created for naming the cases listed above. In this way, a disjunction of atomic concept names is finally obtained. These new artificial concept names have to be added in the table representing the heterogeneous source of information (see Sect. 3.2) and the process for discovering ARs has to be run (see Sect. 3.2). This is because potentially useful ARs for treating the disjuncts may be found. It is important to note that the artificial concept names are not used for the process of discovering new knowledge in itself (as illustrated in Sect. 3.2) but only for the reasoning purpose presented in this section.
Now let us consider the following example concerning the demographic domain where the starting point for the inference is given in Tab. 3. Note that it is assumed that P arent is true for x2. In the following the expansion of (M ale t F emale)(x) for degreeOf M atch(rule2) = 0,
As processing a disjunct expansion we always add assertions coming from the evidence of the available knowledge, the proposed approach should ensure that the model built is the one mostly compliant with the statistical regularities learned from data. 5
To summarize, in this paper we make a step towards the framework for knowledge
representation and reasoning in which knowledge is specified by a mix of logical formulas
and data linked together. We revise the preliminary results we presented in [
Our proposed mixed inference imitates in a way the cognitive reasoning process performed by humans. Indeed a human usually performs a logic reasoning process when he/she has knowledge that is assumed to be complete for a certain domain, for example, the medical domain. This step is represented in our case by the standard deductive approach. If some degrees of uncertainty occur, for instance there are strange symptoms that do not allow for a straightforward diagnosis, then existing cases are analyzed to support a given diagnosis or an alternative one. The existing cases would represent our external source of information (DBs and/or ARs). The process for determining a diagnosis is now driven by the integration of the logic reasoning process and inductive reasoning process that takes into account the additional cases and tries to produce a reasonable diagnosis given the additional available evidence.
The most plausible model that we build may be enriched with additional knowledge coming from the external source of information. Specifically, given the selected rule for resolving a disjunction (see Sect. 3.3), the information on the left hand side concerning only the external source of information could be added as part of the model under construction thus applying a sort of abductive inference. Alternatively, this additional knowledge may be exploited during the matching process for preferring a rule rather than another one (besides of the condition concerning the confidence of the rule). Particularly, as an additional criterion the level of match between the rule and the model under construction may be considered. The same would be done for additional information on the right hand side of a rule even if this case appears to be a bit more problematic.
For the future we aim at implementing the extended Tableaux algorithm for experimental purpose.