A link key between two RDF datasets 1 and 2 is a set of pairs of properties allowing to identify pairs of individuals 1 and 2 through an identity link such axs1 owl ∶ sameAs x2. In this paper, relying on and extending previous work, we introduce an original formalization of link key discovery based on the framework of Partition Pattern Structurepsps(). Our objective is to study and evaluate the redundancy of link keys based on the fact thatowl:sameAs is an equivalence relation. In thpeps concept lattice, every concept has an extent representing a link key candidate and an intent representing a partition of instances into sets of equivalent instances. Experiments show three main results. Firstly redundancy of link keys is not so significant in real-world datasets. Nevertheless, the link key discovery approach based on pps returns a reduced number of non redundant link key candidates when compared to a standard approach. Moreover, thepps-based approach is eficient and returns link keys of high quality.
In this paper, we are interested in data interlinking whose objective is to discover identity
links across two RDF datasets over the web of data1,[
In particular, link keys which are under investigation in this paper are special kinds of rules allowing to infer identity links between two RDF datasets. More formally, a link key is composed of two sets of pairs of properties({( , )} , {( ′ , ′)} ) associated with a pair of classes( 1, 2). Then, whenever an instance1 of class 1 has the same (non empty) set of values as an instanc e1 of class 2, i.e. ( 1) = ( 1) for all pairs of properties in the first set (universal quantification), and shares at least one value for all pairs of properties in the second set (existential quantification), i.e. ′( 1) ∩ ′( 1) ≠ ∅, then 1 and 1 denote the same entity, i.e., an owl:sameAs relation can be established betwee n1 and 1. More concretely, the expression k=({(designation,title)},{(designation,title),(creator,author)}, (Book,Novel)) states that whenever an instance of classBook has the same non empty values for the property designation as an instance of the classNovel for title, and that and share at least one value for the propertiescreator and author, then and denote the same entity aowl:sameAs link can be established betweenand .
Link keys are not provided with the datasets and algorithms are designed for automatically
discovering such link keys9,[
Given two RDF datasets, FCA is applied in 1[0] to a binary table where rows correspond
to pairs of individuals and columns to pairs of properties. The intent of a resulting concept
corresponds to a link key candidate, which remains to be validated thanks to suitable quality
measures. The extent of the concept includes the potential identity links between individuals. A
generalization of the former approach is proposed i1n1[], which is based on pattern structures
[
Actually, “good” link key candidates over two RDF datasets have to generate diferent and maximal link sets, i.e., a mapping between individuals which is “close to a bijection”. However it appears that two diferent link key candidates may generate the same link set when the link set is considered as a partition w.r.t. thoewl:sameAs equivalence relation. This means that these two link key candidates present a certain redundancy, and then they can be considered as equivalent and merged in a way to be defined. This redundancy can be detected thanks to the properties ofowl:sameAs as an equivalence relation, i.e. reflexivity, symmetry, and transitivity. Then, the owl:sameAs relation generates partitions among pairs of individuals that can be used for reducing the number of potential link key candidates. Indeed, two candidates relying on the same partition are considered as redundant and can be merged. However, we do not have a concrete idea of the importance of such redundancy and we should find a way to measure it. This is one objective of this paper to try to materialize this redundancy and to measure its importance.
For doing so, taking inspiration from the work carried out i1n4][on the discovery of functional dependencies, we provide a formalization of link key discovery based on “partition pattern structures”p(ps), which allow us to take into account sets of equivalent individuals w.r.t. owl:sameAs as partitions. Then, a pattern concept represents a link key candidate and the related partition induced by the candidate. This approach is able to retrieve all link key candidates as a set of “non redundant” link keys. Moreover, this link key discovery process based on pps is operational and origin1a.lActually, this is the first time that the characteristics of owl:sameAs as an equivalence relation are considered, and that the related partitions of pairs of individuals are directly used for defining link key candidates. Thanksptpos, we are able to define redundancy of link key candidates and we also introduce a new measure based on the size of partitions for evaluating the quality of the discovered candidates. Finally, the experiments proposed in the last part of this paper provide three main results. Firstly, the redundancy of link keys in real-world datasets appears to be not so significant. Nevertheless, the current link key discovery approach based onpps is eficient and returns a reduced number of non redundant link key candidates. Moreover, thpisps-based approach returns link keys of very high quality when compared to competitors.
The summary of the paper is as follows. Sectio2npresents some basics about link keys. Then the discovery of non-redundant link keys based on pattern structures and partition pattern structures is made precise in Sectio3n. A running example illustrates all these constructions. New quality measures related to non redundant link keys are defined in Secti4o.nFinally, experiments in Section5 show the capability and eficiency of the pps-based approach in link key discovery.
This section introduces the basic definitions relative to data interlinking with link keys. We recall what an RDF dataset is and then we introduce two forms of link keys, namely link key expressions and link key candidates.
Definition 1 (RDF Dataset). Let denote a set of IRIs, i.e., “Internationalized Resource Identifiers”, a set of blank nodes, i.e., “anonymous resources”, and a set of literals, i.e., “string values”.
An RDF dataset is a set of triples (, , ) ∈ ( ∪ ) × × ( ∪ ∪ ) .
Let be an RDF dataset,() = { | ∃ , (, , ) ∈ } denotes the set of individual identifiers, () = { | ∃ , (, , ) ∈ } the set of property identifiers, and () = { | ∃ (, rdf:type, ) ∈ } the set of class identifiers.
Moreover, () = { | ∃ (, rdf:type, ) ∈ } denotes the set of instances of ∈ () while () = { | (, , ) ∈ } denotes the set of objects –or values– associated wit hthrough property .
An identity link is an RDF triple of the for(m, owl:sameAs, ) stating that the IRIs and are referring to the same entity, alternativelaynd are denoting the same individual. Example 1. In Figure1, the RDF datasets 1 and 2 include( 1) = { 1, 2, 3, 4} and ( 2) = { 1, 2, 3, 4} as sets of property identifiers, and( 1) = { 1} and ( 2) = { 2} as class identifiers. In addition, ( 1) = { 1, 2, 3, 4, 5} and ( 2) = { 1, 2, 3, 4, 5} denote respectively the sets of instances of class1 and class 2. Finally, considering subjec3t and property 2, the related set of objects or the “value” of 3 for property 2 is 2( 3) = { 8, 9}. 1The present paper extends a short preliminary version published1i5n].[ with instances of class 1 while on the right-hand side the dataset 2 is populated with instances of class 2.
Link keys are logical constructions allowing to infer identity links between instances of two classes lying in two RDF datasets. In the following we introduce two syntactic definitions of link keys, namely “link key expressions” and “link key candidates”. A definition of a link key and its semantics using Description Logics interpretation is proposed 1in6].[ However, in this paper we will stick to these two syntactic definitions for the sake of simplicity.
Intuitively, alink key expression = (, , (
properties, i.e. , and , where
is based on equality and on non empty intersection, while links are generated between instances of class1esand 2. More formally we have: Definition 2 (Link key expression.) Let 1 and 2 be two RDF datasets, = (, , ( 1, 2)) is a link key expressionover 1 and 2 if ⊆ ( 1) × ( 2), ⊆ , 1 ∈ ( 1) and 2 ∈ ( 2).
The set of links generated by is denoted by () and includes a set of pairs of instances (, ) ∈ (
1) × ( 2) satisfying: (i) for all (, ) ∈ (ii) for all (, ) ∈ ⧵ , () = ()
and () ≠ ∅ , , () ∩ () ≠ ∅
.
The number of link key expressions may be exponential w.r.t. the number of properties. To reduce the search space, algorithms for link key discovery only consider “link key candidates”, i.e., link key expressions which generate at least one link and which are “maximal” among the set of link key expressions.
PS objects (g) The pattern structure related to dataset s 1 and 2 given in Fig. 1.
Definition 3 (Link key candidate.) A link key expression 1 = ( 1, 1, ( 1, 2)) is a link key candidateif: (i) (
1) ≠ ∅, (ii) there does not exist another link key expression 2 = ( 2, 2, ( 1, 2)) over 1 and 2 such that 1 ⊂ 2, 1 ⊂ 2, and ( 1) = ( 2).
(i) 1 = ({( 1, 1)}, {( 1, 1), ( 2, 2)}, ( 1, 2)), (ii) 2 = ({( 1, 1)}, {( 1, 1)}, ( 1, 2)).
) = ( 2
) = {( 3, 3)}. Then 1 and 2 are both link key expressions but only 1 is a link key candidate as it is maximal on the link {s(e t3, 3)} while 2 is not.
The set of link key expressions is denoted blyke, the set of link key candidates bylkc, and
we have that lkc ⊆ lke. The definition of link key candidates is based on the idea of maximality
which involves a certain form of closure. This gave rise to a number of papers studying the
potential relations existing between Formal Concept Analysis (FC12A])[and the discovery of
link keys 9[
In this section we shortly recall how pattern structures can be used in the discovery of link
keys (details can be read in1[
Example 2. Let us consider the pattern structurlekps = (, (, ⊓), ) displayed in Table1. All details for buildinglkps and the associated pattern concept lattice are given i1n1][. In the rows (“PS objects”), includes pairs of related instances, i.(e .,, ) with ∈ ( 1) and ∈ ( 2), which correspond to the objects olfkps. The set of potential description(s, ⊓) includes all possible pairs of properties preceded either b∀yor ∃. For the sake of simplicity, the⊓ operator corresponds here to set intersection.
1 {( 4, 5), ( 5, 4)} 1 = {∀( 4, 4), ∃( 4, 4)}
2 {( 4, 4), ( 5, 5)} 2 = {∀( 3, 3), ∃( 3, 3)}
The mapping relates a pair of instance(s, ) ∈ ( 1) × ( 2) to a description as follows: (i) (, ) includes∀(, ) whenever() = () and () ≠ ∅ , (ii) (, ) includes∃(, ) whenever () ∩ () ≠ ∅ . Actually, such descriptions correspond to link key expressions w.r.t. the pairs of classes( 1, 2). In this work, we only consider the pair of clas se1sand 2, while dealing with several pairs of classes is explained i1n1][.
Based on Fig. 1, the description of( 1, 1) is given by{∃( 1, 1), ∃( 2, 2)} because 1( 1) ∩ 1( 1) ≠ ∅ and 2( 1) ∩ 2( 1) ≠ ∅, while( 2, 1) = {∃( 1, 1)} because 1( 2) ∩ 1( 1) ≠ ∅. Then, ( 1, 1) ⊓ ( 2, 1) = {∃( 1, 1)} and thus ( 2, 1) ⊑ ( 1, 1). This can be read in the pattern concept lattice displayed in Fi2gw.here the pattern concept 5 is subsumed by the pattern concept 4, i.e., the intent{∃( 1, 1)} of 4 is included in the inten{t∃( 1, 1), ∃( 2, 2)} of 5, while the extent{( 1, 1), ( 2, 2), ( 3, 3)} of 5 is included in the extent o f 4 which is {( 1, 1), ( 2, 1), ( 2, 2), ( 3, 3)}.
In this way, the set of all pattern concepts is organized within the pattern concept lattice in Fig. 2. Moreover, all link key candidates are lying in the intents of the pattern concepts.
3.2.1. Motivation: sameAs is an Equivalence Relation.
Having a careful look at Fig2., one can verify that more compact link keys could be designed. For example, in the extent o f 3, {( 1, 1), ( 1, 2), ( 2, 2), ( 3, 3)}, the three first pairs have a non empty intersection when considered in a particular order, i1.ei.s, shared by{( 1, 1), ( 1, 2)} and 2 is shared by{( 1, 2), ( 2, 2)}. Actually there exists a potentiaolwl:sameAs –or simplysameAs– relation between the elements in such pairs. Being an equivalence relastiaomneA,s generates an equivalence class. Hence, we can “merge” some of these pairs in such an equivalence class. For example( 1, 1) and ( 1, 2) can be merged, i.e.,a1 sameAs b1 and a1 sameAs b2 yieldb1 sameAs b2 (symmetry and transitivity osfameAs). Moreover( 1, 2) and ( 2, 2) can be merged because a1 sameAs b2 and a2 sameAs b2 yielda1 sameAs a2. Finally, froma1 sameAs a2 and a1 sameAs b1 it comes a2 sameAs b1. Then a1, a2, b1, b2, are in the same equivalence class w.rs.ta.meAs.
Two important facts should be noticed: (i) the linak2 sameAs b1, absent in 3 but present in 4, is inferred from the extent o f 3 thanks to the properties ofsameAs while in the same way a1 sameAs b2 could be inferred in 4, (ii) the equivalence clas{s( 1, 1, 2, 2)} which can be built in 3 and as well in 4, allows us to merge the link keys in3 and 4 because they have now the “same extent”. Relying on this observation, we define an equivalence relation over the extents of pattern concepts as follows.
Let us consider two RDF datasets 1 and 2, a link key , two classes 1 and 2, and the set of instances = ( 1) ∪ ( 2). Given 0 and ∈ , there exists achain of sameAs relations between 0 and if there exists a sequence of elements 1, 2, … , −1 such that x0 sameAs x1, x1 sameAs x2, … , xn−1 sameAs xn holds, where the symmetry ofsameAs may be used. Then, we define a relation between 0 and in w.r.t. the link key , denoted as 0 ≃ , if there exists a chain of sameAs relations between 0 and . It can be checked that ≃ is an equivalence relation assameAs itself is an equivalence relation. For example, ( 3)/≃∃( 2, 2) = {( 1, 1, 2, 2), ( 3, 3)} where ( 3) denotes the extent of 3. In the same way, ( 4)/≃∃( 1, 1) = {( 1, 1, 2, 2), ( 3, 3)}. Then the two link keys∃( 1, 1) and ∃( 2, 2) can be “identified” or “merged” because they have the same equivalence classes.
As a consequence, one may obtain more comparable sets of linked elements and thus minimize the number of possible link key candidates. Moreover, it can be noticed that an equivalence class determines a partition within the set of instances under study (singletons if any are omitted here). 3.2.2. The design of a PPS for “Non Redundant Link Keys”.
Hereafter, one main objective is to build a specific pattern structure where concepts are
related to unique equivalence classes and yield “non redundant link key candidates” denoted as
nrlkc. Here “non redundant” means any two elements ninrlkc are associated with diferent
equivalence classes. In addition, an equivalence class corresponds to a partition of the set of
instances. Accordingly, we define a “partition pattern structurep”p(s) based on descriptions
which are partitions and used to discover non redundant link key candidates. Indeed, in such
a pps, objects in the rows correspond to pairs of properties and descriptions correspond to
partitions. An example ofpps is proposed in [
Accordingly, we define a partition pattern structure over class e1s and 2 as a triple (lkc, (( ), ⊓ ), ) such as: • lkc is the set of all link key candidates w.r.t. class1esand 2 which are given by a pattern concept lattice (as displayed in Fig2.).
• (( ), ⊓ ) is the set of potential descriptions or partitions an⊓d is the “meet” of two partitions.
• maps a link key candidat e to the partition / ≃ , which is the quotient set of w.r.t.≃ .
As it can be seen in Table2, pps objects are the link key candidates already computed and lying in the intents of the pattern concept lattice. This means that link key candidates will compose pps-concept extents, while partitions involving elements are declared in the descriptions and thus will composepps-concept intents. Moreover, partitions reduced to a singleton are omitted in the descriptions of thepps objects.
Let us examine a concrete example opfps based on the pattern structure given in Table1. For 3, we have ( 3) = {( 1, 1), ( 1, 2), ( 2, 2), ( 3, 3)} and ( 3) = {∃( 2, 2)}. The related partition,( 3)/≃∃( 2, 2) = {( 1, 1, 2, 2), ( 3, 3)}, where singletons are omitted, is associated with row 3 ({∃( 2, 2)}) in Table2 . In the same way, considering 4 and {∃( 1, 1)}, ( 4)/≃∃( 1, 1) is associated with row 4 ({∃( 1, 1)}) in Table2. Moreover, ( 4)/≃∃( 1, 1) = {( 1, 1, 2, 2), ( 3, 3)} and is equal to( 3)/≃∃( 2, 2). As already observed, 3 and 4 are inducing the same partition and can be “merged”. The othpeprs objects, namely 1, 2, 5, and 6, are obtained from the corresponding pattern concepts in F2igi.n the same way. Finally, thepps over classe s1 and 2 related to the dataset s 1 and 2 is displayed in Table2.
The meet –or similarity– operation used to compare the rows in tphpes corresponds to the
meet of two partitions 1 and 2 over and is denoted by 1 ⊓ 2. This meet
operation is classically defined as the intersection of the respective equivalence classes, also
known as the “coarsest common refinement of the two partitions” (see1[
Based on this meet operation, thepps concept lattice is constructed and shown in Fi3g. .The extent of apps concept includes the and the parts of a link key candidat(e, , ( 1, 2)) inlkc. For example, the intent of 6 is {( 3, 3)} and its extent is 6, i.e., {∀( 1, 1), ∃( 1, 1), ∃( 2, 2)}. As all elements in the extents of thpeps concept lattice, 6 is an element ofnrlkc, i.e., a non redundant link key candidate. Moreov er6, corresponds to a closed set and thus verifies maximality, and it is non redundant w.r.t. the partition in the associated intent, i.e., no other link key candidate induces the same partition. 3.2.3. Discussion: From LKC to NRLKC.
We now discuss what is gained in relying on pattern structures and then on partition pattern structures. Actually, the discovery of link key candidatleksc() is based on the construction of the pattern concept lattice. Then the construction of tphpes concept lattice yielding the non redundant link key candidates should be considered as a “refinement” where equivalent link key candidates, i.e., link key candidates inducing the same partition, are merged. For example, both concepts 3 and 4 in Fig. 2 are merged into a single concept 34 in Fig. 3. The resulting pps concept lattice is of smaller size and more concise as link key candidates in the concept extents are non redundant.
The relations existing betweelnkc and nrlkc can be characterized as follows. By construction, nrlkc ⊆ lkc as the discovery of non redundant link keys is based olknc, i.e., the link key candidates lying in the intents of concepts in the pattern concept lattice. Then, the candidates which have the same equivalence classes w.r.t. thseameAs relation are merged to produce the non redundant link key candidates innrlkc. Thus, it comes thatnrlkc ⊆ lkc and that |nrlkc | ≤ |lkc | (where |X| denotes the cardinality of set X). In other words, a non redundant link key candidate is always a link key candidate while the converse is not true.
The definition of nrlkc allows us to introduce a new quality measure for evaluating and validating non redundant link key candidates. In the next section we make precise this new quality measure and we discuss the benefits related to the discovery of non redundant link key candidates. {|(, ) ∈ }
and 2() = {|(, ) ∈ } The discriminability of is () = .
(| 1()|, | 2()|) .
||
Not all link key candidates are eligible to be final link keys. Some candidates can be too general or related to noise in the data and thus they may generaotewl:sameAs links which are not correct or have a bad quality. For example the link key candida(t{e}, {(country,country)}, (Person,Human)) states that two individuals (subjects) sharing the same country represent the same person, and this is obviously not true. The candidat(e{}, {(name,title)}, (Person,Book)) may be discovered by chance and will generate non correct links as well.
An ideal link key candidate should be “correct” and “complete”, and specific “quality measures”
are defined for assessing these properties. In a supervised setting, when a set of reference links
is available, the correctness of a link key candidate is measured thanks to “precision” and the
completeness thanks to “recall”. In an unsupervised setting as this is the case here, the measures
of “coverage” and “discriminability” are defined over the set of links directly generated by a link
key candidate [
The coverage of a set of links over 1 and 2 is (, 1, 2) =
where 1() = | 1() ∪ 2()| | ( 1) ∪ ( 2)| Link Key Candidates
Singleton Partition
1 1{∀( 4, 4),∃( 4, 4)} {( 4, 5),( 5, 4)}
2 2{∀( 3, 3),∃( 3, 3)} {( 4, 4),( 5, 5)}
6 {( 3, 3)} 6{∀( 1, 1),∃( 1, 1),∃( 2, 2)} 7 ∅
5
Coverage and discriminability evaluate how close a set of links is to a total, respectively bijective, mapping. Coverage is maximum when all instances of the considered classes are linked to at least another instance, while discriminability is maximum when instances are linked to at most one instance. key candidate 34 = { 3, 4} interpreted as “3 or 4”.
In the present setting, we are interested in the “redundancy” of link key candidates, and we would like to evaluate the quality of “non redundant” candidates. A link key candidaiste said to be “redundant” in ⊆
lkc if there exists another link key candidaℎte∈ such that /≃ = /≃ ℎ, i.e., generates the same partition asℎ. This is the case in the running example for the link key candidates3 and 4. One main consequence of detecting redundancy is to reduce the number of candidates by merging candidates inducing the same partition. Then, since≃ 3 and ≃ 4 induce the same partition, 3 and 4 are merged into a non redundant link Accordingly, we introduce the new quality measur()e that is compliant with the semantics ofsameAs and defined w.r.t. the partition associated with the equivalence relatio≃n : { ∈ /≃ | || > 1 } | where = ( 1) ∪ ( 2) and /≃ is the quotient set of w.r.t.
3 ) = (
4) = |{( 1, 1, 2, 2), ( 3, 3)}| = 2. The lower bound o f() is 1 since generates at least one link. The upper bound (is| ( achieved when determines a 1-1 mapping. Moreover, pSize can be normalized i n(t)o = 1)|, | ( 2)|) and this is ()/| / ≃
|. Then ( this time singletons are counted.
3) = 2/6 as / ≃ 3 = {( 1, 1, 2, 2), ( 3, 3), 4, 4, 5, 5}, where
The normalized measure() evaluates how close are1 and 2 w.r.t. ≃ , and is maximal when all instances are linked. However, this is not always satisfactory, especially when the cardinalities of the two classes significantly difer (i.e., classes are not balanced). Then, it is more accurate to maximize the measure as soon as all instances of one class are linked as follows: () = ()/(| ( 1)/≃ |, | ( 2)/≃ |) (also known as the “Szymkiewicz–Simpson partition coeficient”). For example, ( 3) = 2/4 with: ( 3) = |{( 1, 1, 2, 2), ( 3, 3)}|/(|{( 1, 2), 3, 4, 5}|, |{( 1, 2), 3, 4, 5}|).
We run experiments on DB-Yago datasets provided in20[]. These datasets are used by the approaches to which we compare our results in the last series of experiments. They have been rewritten into Terse RDF Triple Language (Turtle) which is a syntax for expressing RDF data [21]. They are derived from DBpedia and Yago and organized into nine tasks. One particular task consists in finding links between instances of a class in DBpedia and instances of a class in Yago, e.g., db:Actor and yago:Actor. A set of reference links (i.eo.w,l:sameAs links) denoted by is provided for each task. The statistics of DB-Yago datasets are given in Tab3l.e
Experiments were run on a MacBook Pro 2018 with Intel Core i7-8850H@2,6 GHz, 16GB
of RAM. The link key candidates are provided by a tool callLeidnkex2 in which we have
implemented thelkps algorithm i.e. the link key discovery algorithm based on pattern structures
proposed in [
In Table3, column l|kc| represents the number of link key candidates discoveredlbkyps algorithm while columnnr|lkc| represents the number of non redundant link key candidates. In most of the tasks, we can observe thatn|rlkc| is equal to l|kc|, except for the tasksActor and Film where |nrlkc| is lower thanl|kc| by 1% and by 5% respectively. This means that, in general, link key candidates produce diferent partitions and only a few are redundant. By contrast, if redundancy does not significantly reduce the number of link key candidates, it gives a good idea of the compactness of partitions related to link key candidates.
Nevertheless, even if redundancy is not so significant, we decided to compare the quality of the resulting sets of candidates measured wit h and the results of competitors, namely keys and conditional keys as they are studied in20[].
The measure is used to evaluate and select the best link key candidates, –in this experiment the link key candidate ranked first– in every task listed in Tab3l.eThen, we compare recall, precision, and F-measure of the links generated by the best link key candidates selected by 2Linkex is available online at https://gitlab.inria.fr/moex/linkex. |lkc| against interlinking approaches providing classical keys and conditional keys as reported in [20].
In Figure4 we can observe that: (i) recall of link keys is significantly better than recall of classical and conditional keys, (ii) precision of classical and conditional keys is slightly better than precision of link keys in most of the tasks, (iii) F-measure is much higher for selected link key candidates than for classical and conditional keys.
Link keys have a better recall because they are more flexible than classical keys, i.e., a link key is not necessarily a pair of keys and an instance of cl a1ssmay be linked to many instances of class 2.
For summarizing, it can be concluded that considering the best link key candidates selected by will ensure a higher interlinking quality compared to classical and conditional keys. We also observe that the best link key according to discriminability and coverage is the same that the best non redundant link key selected thanks to . Actually, theActor dataset makes an exception: the link key candidate selected with obtains an F-measure of0.95 contrasting the score of0.34 obtained with coverage and discriminability. In addition, contrasting key-based approaches, link key discovery does not require any prior knowledge such as property or class alignments. |nrlkc| time
This paper introduces a formalization of link key discovery based on partition pattern structures (pps). This approach allows to discover the sentrlkc of link key candidates which are not redundant w.r.t. theowl:sameAs equivalence relation, while still being correct and complete. In addition, new appropriate quality measures are proposed.
Practically, we observe in experiments that the redundancy of link key candidates in public datasets is rather rare. Nevertheless, the experiments and the associated results show that link key based onpps obtain better F-measure values than two other key-based approaches to data-interlinking.
Among the perspectives, a first one is to consolidate the theory and practice of link key discovery based onpps introduced and detailed in this paper. A second and very important direction of investigation is related to the discovery of “fuzzy link keys”. We make the hypothesis that the redundancy of link key candidates is rather rare because we are using the crisp equality operator when we are building the link key candidates. Instead, in considering the discovery of link key candidates as depending on a similarity relation, i.e., reflexive and symmetric –also called a tolerance relation– rather than on an equality, then we could propose a formalization of fuzzy link key candidates in the spirit of approximate-matching dependencies as they are studied in [19]. We could also expect much more diferences between crisp and fuzzy link key candidates. In addition, a reduction of the size of the concept lattice relatednrtolkc could also be investigated thanks to similarities between partitions. Link Keys in an LKPS Concept Lattice, in: A. Braud, A. Buzmakov, T. Hanika, F. L. Ber (Eds.), Proceedings of the 16th International Conference on Formal Concept Analysis (ICFCA), Lecture Notes in Computer Science 12733, Springer, 2021, pp. 243–251. [19] J. Baixeries, V. Codocedo, M. Kaytoue, A. Napoli, Characterizing Approximate-Matching Dependencies in Formal Concept Analysis with Pattern Structures, Discrete Applied Mathematics 249 (2018) 18–27. [20] D. Symeonidou, L. Galárraga, N. Pernelle, F. Saïs, F. M. Suchanek, VICKEY: Mining Conditional Keys on Knowledge Bases, in: Proceedings of 16th International Semantic Web Conference (ISWC), LNCS 10587, Springer, 2017, pp. 661–677. [21] D. Beckett, T. Berners-Lee, E. Prud’hommeaux, G. Carothers, RDF 1.1 Turtle, W3C Recommendation, W3C, 2014.https://www.w3.org/TR/turtle./