Links constitute the core of Linked Data philosophy. With the high growth of data published in the web, many frameworks have been proposed to deal with the link discovery problem, and particularly the identity links. Finding such kinds of links between different RDF data sets is a critical task. In this position paper, we focus on link key which consists of sets of pairs of properties identifying the same entities across heterogeneous datasets. We also propose to formalize the problem of link key discovery using Pattern Structures (PS), the generalization of Formal Concept Analysis dealing with non binary datasets. After providing the proper definitions of link keys and setting the problem in terms of PS, we show that the intents of the pattern concepts correspond to link keys and their extents to sets of identity links generated by their intents. Finally, we discuss an implementation of this framework and we show the applicability and the scalability of the proposed method.
Data interlinking is the task of finding the same entities described in different RDF
datasets. To perfom this task, it has been proposed to use link keys [
Copyright c 2019 for this paper by its authors. Copying permitted for private and academic purposes.
The question of using Formal Concept Analysis (FCA) to extract such kind of keys
has naturally arisen, given that the set of link key candidates is an ordered structure. A
first formalization is given in [
Notations and definitions An RDF dataset is a set of triples: hsub ject; property; ob jecti 2 (U [ B) U (U [ B [ L), where U is a set of IRIs (Internationalized Resource Identifier), B a set of blank nodes and L a set of literals, i.e., values depending on datatypes. In this work, we consider only objects which are literals. To avoid confusion with PS objects, we refer to ”object” in an RDF triple as ”rdf object”. Let D; D0 be two RDF datasets, we aim to discover link keys between two specific classes C, C0 from D; D0 respectively. C = fsjhs,rdf:type,Ci 2 Dg and C0 = fs0 jhs0 ,rdf:type,C0 i 2 D0 g are the sets of instances of the classes C and C0 respectively. P = fpj9s; o; hs; p; oi 2 Dg and P0 = fp0 j9s0 ; o0 ; hs0 ; p0 ; o0 i 2 D0 g are the sets of properties from D and D0 respectively. Unlike databases, the properties in RDF are not functional i.e. for one property, an instance may have more than one value i.e. rdf object. Here, p(s) = foj9s; p; hs; p; oi 2 Dg is the set of the values of an instance s for the property p. Figure 1 represents an example of two datasets represented by instances of the classes Person and Inhabitant respectively. The goal here is to find a link key which identifies the same entities described in both classes. One may expect to identify that z1 is the same entity as i1 i.e. the link hz1; i1i as well as the links hz2; i2i and hz3; i3i. o1 : Person o1:firstName
Dupont Thomas Dubois Durand Lisa o2:name o2:given o2:given o2:name o2:name o2:name o1:given o2 : Inhabitant o2 : i1 o2 : i2 o2 : i3
A link key is a statement of the form:
fhp1; p01i; ::; hpk; p0kigfhp1; p01i; ::; hpk; p0ki; ::; hpn; p0nig linkkey hC;C0 i meaning that for all pairs of instances hs; s0 i 2 C C0 , if s and s0 have the same values, i.e. rdf objects, for each pairs of properties p1;::;k and p01;::;k respectively, and share at least one value for each pair of properties pk+1;::;n and p0k+1;::;n respectively, then they represent the same entity i.e. (hs; owl:sameAs; s0 i): Definition 1 (Link key expression). Let Eq and In be sets of pairs of properties hp; p0 i 2 P P0 where Eq In. K = hEq; In; hC;C0 ii is called a link key expression over two classes C;C0 . Notice that Eq and In may be empty.
Since Eq In, we write K = Eq; In n Eq for short. Which means that when a pair of properties belongs to the Eq part, we don’t represent it in the In part. As example of link key expression over the two classes Person and Inhabitant, we have: 0/ ; fhlastName; namei; h f irstName; givenig where Eq is empty.
Definition 2 (Satisfaction of a link key expression). We say that a link hs; s0 i 2 C satisfies the link key expression K = Eq; In and we write K j= hs; s0 i iff: 8hp; p0 i 2 Eq=)p(s) = p0 (s0 ) 6= 0/ and 8hp; p0 i 2 In=)p(s) \ p0 (s0 ) 6= 0/ C0 Notice that a link may satisfies more than one link key expression.
The set L(K) = fhs; s0 i 2 C C0 jK j= hs; s0 ig is the set of all links satisfying K and called the link set generated by K.
Definition 3 (meet, join, subsumption of link key expressions). Let K1 = Eq1; In1 and K2 = Eq2; In2 two link key expressions. The meet u and join t of K1 and K2 are defined respectively as follow:
K1 u K2 = Eq1 \ Eq2; In1 \ In2 and K1 t K2 = Eq1 [ Eq2; In1 [ In2
We say K2 subsumes K1 and we write K1 v K2 iff K1 u K2 = K1 where v is a partial order between link key expressions. 3
Link key extraction with Pattern Structure
We propose here to formalize the problem of link key candidate extraction using PS [
Definition 4 (Pattern Structure for link key extraction). A Pattern Structure for link keys extraction is a triple (C C0 ; (D; u; t); d ) where, C C0 is the set a pair of instances hs; s0 i 2 C C0 . D is a set of link key expressions over the two classes C and C0 . d is a mapping associating each pair of instances hs; s0 i 2 C C0 to its description K, defined as the maximal link key expression satisfied by hs; s0 i i.e. the join of the link key expressions satisfied by hs; s0 i. Formally, d (hs; s0 i) = tfKjK j= hs; s0 ig. (D; u; t) is a lattice. The meet, join and subsumption of two link key expressions are defined as in Definition 3. From the previous example of datasets represented in Figure 1, we obtained the Pattern Structure in Table 1. Here for example, to find d (hz1; i1i), we have computed the join of all link key exepressions satisfied by the link hz1; i1i and we obtained the description d (hz1; i1i) = fhlastName; namei; h f irstName; givenig; fg.
Notice that we omit pairs of instances for which descriptions correspond to the empty link key expression K = 0/ ; 0/ .
Derivation operators : are defined as follows for A C C0 and K 2 D:
A = uhs;s0 i2Ad (hs; s0 i) and K = fhs; s0 i jK v d (hs; s0 i)g (A; K) is a pattern concept if A = K and K = A. We say that a pattern concept (A; K) is subsumed by another pattern concept (A1; K1) if A A1 (or equivalently if K1 v K). We aim here to extract link key candidates using the PS defined above. Definition 5 (Link key candidate). A link key expression K is a link key candidate over two classes C;C0 if L(K) 6= 0/ and there is no link key expression H such as H v K that generates the same link set as K i.e. L(K) 6= L(H) One can see that, if (A; K) is a pattern concept, then its intent K represents a link key candidate and its extent is the link set generated by this link key candidate. Figure 2 represents the pattern concept lattice generated from the PS in Table 1. For example, the pattern concept:fhz1; i1i; hz2; i2i; hz3; i3ig, fh f irstName; givenig; fhlastName; nameig, identify the link key candidate in the intent, which generates the link set in the extent. This link key candidate can be applied as a link key. In fact, it generates the expected links. For example the instances z3 and i3 represent the same person since both of them had the same first name and share at least one family name. The class Inhabitant gives, for example, the birth name and the married name while the class Person gives just one of these two. hhzz32;;ii23ii fhlastNam0/e;nameig fhlastNafmge;nameig Fig. 2. The resulting lattice from the pattern hz3;i3i fh f irstName;givenig fhlastName;nameig structure in Table 1. 4
Tool Description
We have implemented a prototype tool called Linkex 1, which aims to extract link
key candidates using PS. It starts from two RDF data sets and computes a PS, then
generates a pattern concept lattice using a modified version of AddIntent algorithm
[
To demonstrate the applicability and the scalability of the proposed tool, we have experimented with two bibliographical datasets. The first one2 is produced by BnF, the ”Bibliothe`que nationale de France”. The second one3 is produced by ABES, ”Agence Bibliographique de l’Enseignement Supe´rieur”. BnF and ABES, have provided us with two samples of data for the experiments. The first sample is an extraction of authors instances (and their books instances) that have a combination firstname, name which is in the top 1000 most frequent homonyms. The second sample is an extraction of all authors instances (and their book instances) that have a name starting with letter ’A’. We aim here to find link key candidates between instances of the classes representing authors contained in both datasets. As showed in Table 2, we got short running times comparing to the size of processed data. Notice that, the processing time is correlated to the size of datasets. Yet, the most interesting result here is the number of the obtained pattern concepts i.e. the number of link key candidates represented by the column #PsConcepts in Table 2. For example, in sample 1, from 1,564,495 pattern structure descriptions, we got only 155 link key candidates. As a direct consequence of this, is that an expert could easily navigate these link key candidates and evaluate them. Thus, we can say that the proposed method implemented as Linkex is applicable and scalable. l Samples #BnF #ABES #PsEntries #PsConcepts Processing time . Sample 1 8,162 15,421 1,564,495 155 2m10
Sample 2 18,637 142,571 12,348,012 186 6m50 5
Conclusions In this work, we formalize the problem of extracting link key candidates using PS and we propose a tool allowing to automatically build a pattern concept lattice where each pattern concept intent is a candidate link key. We aim to extend this work to consider interdependent classes i.e when rdf objects are instances of other classes and we plan also to relax equality constraints used to compare literals by considering similarity measures instead.
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. 2 https://data.bnf.fr 3 https://www.idref.fr