In this paper, we are interested in the discovery of link keys among two different RDF datasets based on FCA and pattern structures. A link key identifies individuals which represent the same real world entity. Two main strategies are used to automatically discover link keys, ignoring or not the classes to which the individuals belong to. Indeed, a link key may be relevant for some pair of classes and not relevant for another. Then, discovering link keys for one pair of classes at a time may be computationally expensive if every pair should be considered. To overcome such limitations, we introduce a specific and original pattern structure where link keys can be discovered in one pass while specifying the pair of classes associated with each link key, focusing on the discovery process and allowing more flexibility.
RDF (Resource Description Framework) triples hsubject,property,objecti are the
basic bricks of the web of data. The elements in the triples are described using terms of
RDF Schema and OWL ontologies. The same real world entity can be represented in
different datasets by different individuals, i.e. subjects. Data interlinking is the task of
finding identity links across datasets. Two main approaches are proposed to perform this
task. The first one measures a similarity between subjects considering that the closest
the subjects, the more likely they are the same [
Usually link keys are not provided. For this reason, a first algorithm was proposed in
[
The question of using Formal Concept Analysis (FCA) to discover link keys has
arisen naturally, since a link key candidate presents some mathematical properties which
are similar to the ones of a formal concept in FCA [
To discover link keys candidates, the existing methods apply one of the following
strategies. The first one takes as input all the subjects from two datasets, ignoring the
classes to which the subjects belong to, e.g. Book. This strategy generates link key
candidates that apply to the whole datasets, i.e. it does not specify the pair of classes
associated with each link key candidate. These candidates are then evaluated considering
the whole datasets and again without taking into account the pair of classes. This
evaluation, however, is not accurate since a link key candidate may be relevant for a pair of
classes e.g. hBook, Dictionaryi and not relevant for another pair e.g. hBook, Noveli.
The second strategy consists in finding link key candidates for one particular pair of
classes at a time, then evaluating these candidates w.r.t. this particular pair. This
strategy repeats the same process for all the pairs of classes issued from the two datasets.
This allows a more accurate evaluation of the link key candidates. However, we do not
know in advance which classes to take as input at a time. Consequently, a naive
approach would be to consider all the pairs of classes from the Cartesian product of the
sets of classes of the given datasets, or to require a class alignment [
In this paper, we propose a method based on Pattern Structures, a generalization
of Formal Concept Analysis [
The plan of the paper is as follows. First we give some definitions and notations. Then, we present how the problem of link key discovery is encoded in FCA. After that, we formalize the problem with pattern structure and we show how to discover link keys from two datasets in one pass while specifing which pairs of class expressions are associated with these candidates. 2
An RDF dataset [
Given two datasets D1 and D2, we aim to discover identity links between these datasets. An identity link is a statement of the form hs1, owl:sameAs, s2i expressing that the subject s1 from D1 and the subject s2 from D2 represent the same real world entity. For example, given D1 and D2 as represented in Figure 1, the data interlinking task should discover the identity link ha13,owl:sameAs,b13i because the subjects a13 and b13 represent both the same book Les Mis´erables written by Victor Hugo. For short, we write ha13, b13i and we call this pair a link. A link key is used to generate such links.
We distinguish two notions related to link keys. The first one islink key expression
which is the syntactic form of a link key, i.e. it does not necessarily generate actual links.
The second one is link key candidate which is a link key expression that generates at
least a link and it is maximal w.r.t. its generated link set. Actually, link key discovery
methods find link key candidates and evaluate them thanks to adapted measures such as
proposed in [
The notion of a link key has been defined in [
Woman a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 Scientist
Book a11 a12 a13 a14 a15 given familyN familyN given given familyN given familyN given familyN
given familyN given familyN given familyN familyN given given familyN
date designation designation
date descirgenaattoiron
creator designation designation creator
Oprah Winfrey Kelly Grace Hopper Anita Borg
Ada Lovelace Katie Bouman Rosalind Franklin Marie Curie Pierre Alan Turing 2016 2009 The Merriam-Webster Dictionary
Les Mise´rables
Victor Hugo Notre-Dame de Paris
The Talisman Stephen King Peter Straub firnsatmNeame firstName
name firstName
name firstName
name firstName
name firstName name year year title title title author author title title author author
FemaleScientist b3 b4 b5 b6 b7 b8 Dictionary b11 b12 b13 b14 b15 Novel D1
D2
Fig. 1. Example of two RDF datasets. On the left-hand side, the dataset D1 populated with
instances of the classes: Woman, Scientist and Book. On the right-hand side, the dataset D2
populated with instances of the classes: FemaleScientist, Dictionary and Novel
expressions from description logics [
Firstly below we introduce the definition of a link key expression associated with a pair of class expressions.
us consider two datasets D1 and D2. Let Eq and In 6= 0/ be subsets of pairs of properties, such as, Eq ⊆ P(D1) × P(D2), In ⊆ P(D1) × P(D2), Eq ⊆ In. Let CE1 be a class expression over Cl(D1) and CE2 a class expression over Cl(D2). k = (Eq, In, hCE1,CE2i) is a link key expression associated with the pair of class expressions hCE1,CE2i over D1 and D2.
Actually we replace the pair of named classes in a link key expression as defined in [
A link key expression associated with a pair of class expressions may generate links among these class expressions. We define this link set as follows.
of class expressions). Given two datasets D1 and D2. Let k = (Eq, In, hCE1,CE2i) be a link key expression associated with the pair of class expressions hCE1,CE2i over D1 and D2. The link set generated by k is the subset Lk ⊆ (S(CE1) × S(CE2)) defined as Lk = {hs1, s2i ∈ S(CE1) × S(CE2)) | p1(s1) = p2(s2) 6= 0/ for all hp1, p2i ∈ Eq and p1(s1) ∩ p2(s2) 6= 0/ for all hp1, p2i ∈ In}.
As the properties in RDF are not functional, we compare the values of subjects in two ways (i) Eq are pairs of properties for which two subjects share all their values and (ii) In are those pairs of properties for which two subjects share at least one value. For example ha15, b15i ∈ Lk where: k = ({hdesignation,titlei}, {hdesignation,titlei, hcreator,authori}, hBook,Noveli) because ha15, b15i ∈ S(Book) × S(Novel) and designation(a15) = title(b15) 6= 0/ and creator(a15)∩author(b15) 6= 0/.
A link key candidate is a link key expression that generates at least a link and it is maximal on the link set that it generates. To define ”maximality” we have to define an order between link key expressions.
expressions). Given two datasets D1 and D2. Let k1 = (Eq1, In1, hCE11,CE21i) and k2 = (Eq2, In2, hCE12,CE22i) be link key expressions over D1 and D2. The meet u and the join t of k1 and k2 are defined as follows: k1 u k2 = (Eq1 ∩ Eq2, In1 ∩ In2, h(CE11 tDL CE12), (CE21 tDL CE22)i) k1 t k2 = (Eq1 ∪ Eq2, In1 ∪ In2, h(CE11 uDL CE12), (CE21 uDL CE2) ) 2 i The link set of a link key expression k1 u k2 is equal to the union of the link sets of k1 and k2. The less the number of pairs of properties to compare in a link key expression, the more the pairs of subjects satisfying these pairs of properties. Thus the larger the classes in a link key expression, and dually for k1 t k2.
As an example from the datasets represented in Figure 1, the meet of two link key expressions k1 = ({hgiven,firstNamei}, {hgiven,firstNamei}, hWoman,FemaleScientisti) and k2 = ({hgiven,firstNamei}, {hgiven,firstNamei, hname,familyNi}, h(WomanuDLScientist),FemaleScientisti) is k1 u k2 = ({hgiven,firstNamei}, {hgiven,firstNamei}, hWoman,FemaleScientisti) . The join k1 t k2 = ({hgiven,firstNamei}, {hgiven,firstNamei, hname,familyNi}, h(WomanuDLScientist),FemaleScientisti).
Now we formally define a link key candidate associated with a pair of class expressions.
consider two datasets D1 and D2. Let k = (Eq, In, hCE1,CE2i) be a link key expression associated with the pair of class expressions hCE1,CE2i over D1 and D2. k is a link key candidate for D1 and D2 if – L k 6= 0/, and – k = Fh∈[k] h such that [k] = {h | Lk = Lh}
Intuitively the link sets generated by link key expressions form a partition of the set
of link key expressions. Link key candidates are the maximal elements of the classes
of this partition. This definition matches the definition of a closed set. This explains
the use of Formal Concept Analysis [
The link key discovery based on Formal Concept Analysis is detailed in [
Link key discovery based on FCA takes as input one pair of classes at a time. To discover link key candidates, in one pass, we take as input the pair of classes howl:Thing, owl:Thingi, where owl:Thing is a class containing all the subjects. The generated link key candidates will be associated with the pair howl:Thing,owl:Thingi which means that they apply to the whole datasets. Figure 2 presents the concept lattice related to the LK−formal context associated with the pair of classes howl:Thing, owl:Thingi for the datasets D1 and D2 introduced in Figure 1.
k8 co=.50 di=.85 hm=.63
{ha2, b3i} {∀hgiven,firstNamei, ∃hgiven,firstNamei}
k7 co=.50 di=.85 hm=.63
{ha9, b8i} {∀hfamilyN,namei, ∃hfamilyN,namei} {ha3, b3i, ha4, b4i, ha5, b5i, ha6, b6i, ha7, b7i, ha8, b8i}
k9 co=.46 di=1 hm=.63
k0 S(D1) × S(D2) 0/
k1 co=.38 di=71 hm=.49 {ha11, b12i, ha12, b11i} {∀hdesignation,titlei, ∃hdesignation,titlei}
k2 co=.15 di=1 hm=.26 {ha11, b11i, ha12, b12i} {∀hdate,yeari, ∃hdate,yeari}
k10
It was shown in [
Now, to evaluate the quality of a link key candidate in terms of coverage and discriminability, let us consider L ⊆ (S(CE1)×S(CE2)) and π1(L) = {s1 ∈ S(CE1)|hs1, s2i ∈ L}, π2(L) = {s2 ∈ S(CE2)|hs1, s2i ∈ L}, where π1(L) is the set of instances of the class k3 co=.23 di=.60 hm=.33 {∃hcreator,authori} {ha15, b15i}
k4 co=.23 di=1 hm=.37 co=.15 di=.50 hm=.23 {ha13, b14i, ha14, b13i} {∀hcreator,authori} {ha13, b13i, ha14, b14i} k5 k6 co=.15 di=1 hm=.26 expession CE1 appearing in L and π2(L) is the set of instances of the class expession CE2 appearing in L.
The coverage of a link key candidate k associated with a pair of class expressions hCE1,CE2i is denoted by co(k) and defined as: co(k) = |π1(Lk) ∪ π2(Lk)|
|S(CE1) ∪ S(CE2)| The coverage is the proportion between the number of instances identified (linked) by k and the overall number of instances of the two class expressions. This means that the coverage measures how general a link key candidate is. When co(k) is equal to 1, this means that all instances from CE1 and CE2 are identified by the link key candidatek. The discriminability of a link key candidate k associated with a pair of class expressions hCE1,CE2i is denoted by di(k) and defined as: di(k) = min(|π1(Lk), π2(Lk)|)
|Lk| di(k) is the proportion of the minimum number of instances identified by k and the number of links generated by k. When di(k) is equal to 1, then the link key is perfectly discriminant, i.e. it generates one-to-one mappings.
Coverage and discriminability are aggregated by the harmonic mean denoted hm(k) and defined as: hm(k) = 2 + 1 co(k)
1 di(k) The coverage, discriminability, and harmonic mean of the link key cadidate k9 in the lattice in Figure 2, are respectively, co=0.46, di=1, hm=0.63. The link key discovery methods return as link keys the link key candidates whose harmonic mean value is the highest. In this example, they return the link key candidates k7, k8 and k9, because they have the highest hm. However, even if these candidates are relevant for the pair h(WomanuDLScientist),FemaleScientisti, they do not generate any links for the pair hBook,Dictionaryi. In fact for this latter pair, the link key candidate k2 is more relevant, because it generates only and all correct links, even if it has a low hm. For the pair hBook,Noveli, the candidate k4 is more relevant. Even if they are relevant, these link key candidates show a low hm because they are evaluated considering the whole datasets i.e. howl:Thing, owl:Thingi.
We propose in the following our main contribution which is a method based on pattern structures for discovering relevant link keys for given pairs of classes. 3
In the following, we propose a method based on pattern structures, a generalization of
FCA [
We define the pattern structure for link key candidates discovery where the set of objects is the set of pairs of subjects issued from two datasets. Actually these pairs correspond to potential links. In the pattern structure, the description of a potential link is given by the maximal link key expression that generates this link. Then the meet of two descriptions corresponds to the meet of link key expressions as introduced in Definition 3.
D1 and D2. The pattern structure for link key candidate discovery between D1 and D2, called hereafter the LK−pattern structure, is the triple (S(D1) × S(D2), (E, u), δ ) where: – The set of objects S (D1) × S(D2) is the set of pairs of subjects over D1 and D2. – E is the set of potential object descriptions. A description is a link key expression k = (Eq, In, hCE1,CE2i) over D1 and D2. – (E, u) is a meet semilattice where the meet u of two descriptions k1 = (Eq1, In1, hCE11,CE21i) and k2 = (Eq2, In2, hCE12,CE22i) is given in Definition 3: k1 u k2 = (Eq1 ∩ Eq2, In1 ∩ In2, h(CE11 tDL CE12), (CE1 2 tDL CE22)i).
The descriptions are partially ordered by v defined w.r.t. the similarity operator u.
If k1 u k2 = k1 ⇔ k1 v k2. – The mapping δ : S(D1) × S(D2) → E associates each pair of subjects hs1, s2i ∈ S(D1) × S(D2) to its description δ (hs1, s2i) = (Eq, In, hCE1,CE2i) where, Eq = {hp1, p2i|p1(s1) = p2(s2) 6= 0/ }, In = {hp1, p2i|p1(s1) ∩ p2(s2) 6= 0/ }, CE1 (resp.
CE2) is the conjunction of the classes of s1 (resp. s2) over Cl(D1) (resp. Cl(D2)). The LK−pattern structure for the datasets in Figure 1 is given in Table 1. The set of objects is the set of pairs of subjects from S(D1)×S(D2). The set of potential object descriptions E is the set link key expressions over D1 and D2. For example, such a description is given by k = ({hdesignation,titlei}, {hdesignation,titlei},hBook,Dictionaryi). We may calculate the description of the pair ha8, b8i ∈ S(D1) × S(D2) as follows: δ (ha8, b8i) = ({hgiven,firstNamei, hfamilyN,namei}, {hgiven,firstNamei, hfamilyN,namei}, h(WomanuDLScientist),FemaleScientisti) The meet of the two descriptions k1 and k2 can be calculated as follows: k1 = ({hgiven,firstNamei, hfamilyN,namei}, {hgiven,firstNamei, hfamilyN,namei}, h(WomanuDLScientist),FemaleScientisti) k2 = ({hgiven,firstNamei}, {hgiven,firstNamei}, hWoman,FemaleScientisti) k1 u k2 = ({hgiven,firstNamei}, {hgiven,firstNamei}, hWoman,FemaleScientisti) k1 u k2 = k2, hence, k2 v k1
The derivation operators . form a Galois connection between 2S(D1)×S(D2) and E and defined as follows: L = d
δ (hs1, s2i) hs1,s2i∈L k = {hs1, s2i ∈ S(D1) × S(D2)|k v δ (hs1, s2i)} L ⊆ S(D1) × S(D2) k ∈ E
Objects Descriptions S(D1) × S(D2)Eq In hCE1,CE2i ha2, b3i {hgiven,firstNamei} {hgiven,firstNamei} hWoman, FemaleScientisti ha3, b3i h{fhgaimvielny,Nf,inrasmteNi}amei, h{fhgaimvielny,Nf,inrasmteNi}amei, hF(eWmoamlaenSucDiLeSnctiiesnttiist), ha4, b4i h{fhgaimvielny,Nf,inrasmteNi}amei, h{fhgaimvielny,Nf,inrasmteNi}amei, hF(eWmoamlaenSucDiLeSnctiiesnttiist), ha5, b5i h{fhgaimvielny,Nf,inrasmteNi}amei, h{fhgaimvielny,Nf,inrasmteNi}amei, hF(eWmoamlaenSucDiLeSnctiiesnttiist), ha6, b6i h{fhgaimvielny,Nf,inrasmteNi}amei, h{fhgaimvielny,Nf,inrasmteNi}amei, hF(eWmoamlaenSucDiLeSnctiiesnttiist), ha7, b7i h{fhgaimvielny,Nf,inrasmteNi}amei, h{fhgaimvielny,Nf,inrasmteNi}amei, hF(eWmoamlaenSucDiLeSnctiiesnttiist), ha8, b8i h{fhgaimvielny,Nf,inrasmteNi}amei, h{fhgaimvielny,Nf,inrasmteNi}amei, hF(eWmoamlaenSucDiLeSnctiiesnttiist), ha9, b8i {hfamilyN,namei} {hfamilyN,namei} hScientist, FemaleScientisti ha11, b11i h{dhdeastieg,nyaetairoin,,titlei} hdesignation,titlei} hBook,Dictionaryi
{hdate,yeari, ha11, b12i {hdesignation,titlei}{hdesignation,titlei}hBook,Dictionaryi ha12, b11i {hdesignation,titlei}{hdesignation,titlei}hBook,Dictionaryi ha12, b12i h{dhdeastieg,nyaetairoin,,titlei} hdesignation,titlei} hBook,Dictionaryi
{hdate,yeari, ha13, b13i h{dhcerseiagtnoart,iaount,htoirtil,ei} hdesignation,titlei} hBook,Noveli
{hcreator,authori, ha13, b14i {hcreator,authori} {hcreator,authori} hBook,Noveli ha14, b13i {hcreator,authori} {hcreator,authori} hBook,Noveli ha14, b14i h{dhcerseiagtnoart,iaount,htoirtil,ei} hdesignation,titlei} hBook,Noveli
{hcreator,authori,
ha15, b15i {hdesignation,titlei}h{dhcerseiagtnoart,iaount,htoirtil,ei} hBook,Noveli
As usual, L is a closed set if L = L and k is a closed set if k = k. Then a pattern
concept verifies:L = k and k = L. The link key expression k is a link key candidate
for the two datasets D1 and D2 if and only if (L, k) is a pattern concept of the LK−pattern
structure for D1 and D2.
Figure 3 represents the pattern concept lattice generated from the LK−pattern structure
in Table 1. Each intent of a pattern concept represents a link key candidate
associated with a pair of class expressions. For example the link key candidate k9 is
associated with the pair of class expressions h(WomanuDLScientist),FemaleScientisti. It
should be noticed that the link key candidate k9 in Figure 3 corresponds to the link
key candidate k9 in Figure 2 (calculated with plain FCA). In the pattern concept
lattice we can see that the link key k9 is associated with the pair of class expressions
h(WomanuDLScientist),FemaleScientisti, whereas this was not possible using plain
FCA (see [
k1a co=1 di=.71 hm=.83 {hdesignation,titlei}, {hdesignation,titlei} hBook,(DictionarytDLNovel)i appearing in such link key candidates are used to describe subjects belonging to different classes. For example, the property title appearing in k1a and k1b is used to describe the instances of the classes Dictionary and Novel. Furthermore, we may notice that one pair of classes can be associated with more than one link key candidate. For example, we can see the pair of classes hBook,Noveli (in orange) which is associated with four link key candidates k3, k4, k5 and k6. This means that there are four possible choices to select a link key candidate for the pair hBook,Noveli among the four candidates k3, k4, k5 and k6.
Specifying the pairs of classes associated with a link key candidate is a critical task to properly evaluate this candidate. For example, the link key candidate k4, in Figure 2, shows a low harmonic mean hm=0.37, because it is evaluated on the whole datasets. Consequently, k4 is poorly ranked by a system based on FCA. This means that k4 will not be returned as a relevant candidate despite the fact that it generates all the correct links between the classes Book and Novel while no other candidate is able to generate those links. By contrast, in Figure 3, k4, shows a good harmonic mean hm=0.85 because it is evaluated on the ”right pair” of classes hBook,Noveli. The candidate k4 will be returned by a LK−pattern structure as a relevant candidate for the pair of classes hBook,Noveli. Hence, we can appreciate the importance of introducing the notion of
LK−pattern structure and the discovery of link key candidates associated with pairs of classes. 4
Link keys are used to discover identity links across RDF datasets. In this paper, given two datasets, we propose a method based on pattern structures and introduce the notion of LK−pattern structure to discover link key candidates. An added value of the present method is to allow the discovery of link key candidates while specifying the classes to which they apply. This is a substantial improvement for properly evaluating the discovered link key candidates. For future work we plan to study the scalability and the efficiency of the method by running experiments on real-world datasets.We also intend to extend this research work by taking advantage of domain ontologies related to the datasets under study.
This work has been supported by the ANR project Elker (ANR-17-CE23-0007-01) and the BnF in the context of the agreement between Inria and Ministe`re de la culture.