On the relation between keys and link keys for data interlinking

1.Introduction

There are large amounts of RDF data available on the Web, in the form of knowledge graphs or as part of linked open data. Interoperability between RDF datasets largely relies on links between resources from different RDF datasets and especially links asserting the identity of resources bearing different IRIs, specified using the owl:sameAs property [20]. Since RDF datasets tend to be large, the automatic discovery of owl:sameAs links between RDF datasets is an important and challenging task. This task is usually referred to as data interlinking and different algorithms and tools for data interlinking have been proposed [18,25].

Among the state-of-the-art approaches to data interlinking, some are based on finding keys [2,9,17,31] or link keys [7,8] across RDF datasets. Both keys and link keys are devices characterising what makes two resources to be identical. Hence, it is natural to exploit them for discovering links across datasets. Even though both techniques have been proven to be effective in data interlinking scenarios, their relationship has not been formally established yet.

The objective of this paper is to clarify the relationship between keys and link keys. For this, we first provide the semantics of (RDF) keys and link keys. More specifically, we formalise how a key, in its different versions, can be combined with an alignment between ontologies for data interlinking. Then, we define the semantics of six kinds of link keys – weak, plain and strong link keys, and their in- and eq-variants – and we logically ground the usage of link keys for data interlinking. Finally, we establish the conditions under which link keys are equivalent to keys and show that data interlinking with keys and ontology alignments can be reduced to data interlinking with link keys, but not the other way around.

The contribution of this paper focuses on the specific features of keys and link keys. It does it, to the extent possible, independently from the underlying ontological schema and the logical constructors used for describing or constraining class and property expressions. This is the reason why computational issues are left for further interesting research.

In the remainder, Section 2 presents the context and related work of the paper. Section 3 introduces the notations used throughout the paper. Section 4 recalls two different semantics of keys and Section 5 logically justifies their use for data interlinking. Section 6 defines link keys. Section 7 logically grounds the use of link keys for data interlinking. The relations between keys and link keys are established in Section 8, both with respect to their logical entailment and the links they produce. Section 9 concludes the paper and discusses future work.

All definitions are illustrated with concrete examples taken from real-world datasets.

2.Context and related work

Data interlinking refers to the process of finding pairs of IRIs of different RDF datasets representing the same entity [18,25]. The result of this process is a set of same-as links to be specified by the owl:sameAs property. To decide whether two IRIs represent the same entity or not is mainly based on comparing their values for selected properties. Data interlinking is reminiscent of the task of record linkage in databases [14], but it is applied to RDF data described with RDFS/OWL ontologies.

Link discovery platforms such as SILK [22,33] and LIMES [26] enable users to process link specifications to generate links. Link specifications express the properties to be used for generating owl:sameAs links between two RDF datasets. They also specify the similarity measures to be used for comparing datatype property values, the aggregation functions for combining similarity values, and the similarity thresholds beyond which two values are considered equal. Link specifications may be directly set by users or they may be built (semi-)automatically, for example, using machine learning techniques [27,29].

A key is a set of (datatype or object) properties that uniquely identify the instances of a class within a dataset. For example,

Key-based approaches to data interlinking first extract key candidates from RDF datasets and then select the most accurate candidates according to different quality measures [2,9,17,31]. When the data of two RDF datasets are described using the same ontology, then keys, if available, can be directly used for interlinking the datasets, but if the data are described using different ontologies, then they need to be combined with ontology alignments [16] relating the properties and classes of the data. For example, the previous key could be combined with the alignment correspondences creator≡auteur, title≡titre and Book≡Livre to interlink the books of English and French libraries.

Keys can be used to build link specifications or can be translated into logical rules to perform data interlinking. The latter allows to take advantage of logical reasoning [3,4,21]. Key extraction algorithms discover either S-keys [2,17,31] or F-keys [9,30]. There are two kinds of keys since RDF properties are multivalued, contrary to relational attributes, which are monovalued. If a set of properties form an S-key for a class, it is enough that two instances of the class share one value for each of the properties of the key to infer that they are the same (e.g. email property for the AssistantProfessor class). But if the properties form an F-key then the instances must share all values (e.g. hasPoem property for the PoemAnthology class because two different poem anthologies may have a poem in common but will unlikely contain exactly the same poems).

When datasets are described with different ontologies, alignments must be used, either during the key extraction process or later when performing data interlinking. For example, the approach proposed in [31] searches in a source dataset for S-keys over classes which are equivalent to classes in a target dataset and then selects among the discovered S-keys those composed of properties which are equivalent to properties of the target dataset.

Link keys generalise the combination of keys and ontology alignments for data interlinking [7,16]. A link key is a set of pairs of properties that uniquely identify the instances of two classes of two RDF datasets. For example,

Unlike [31], the key-based approaches to data interlinking proposed in [2,17] aim to discover S-keys that hold not only in the source dataset, but in both source and target datasets. It is assumed that the datasets are described using the same vocabulary, possibly resulting from merging different ontologies with an alignment, again composed of equivalence correspondences only. Link keys do not require the properties that compose them to be equal or semantically aligned. In addition, as we will show in this paper, the kind of keys discovered in [2,17] correspond to strong link keys, although data interlinking may be possible with weak link keys (the kind of link keys considered in [7,16]) when strong link keys do not exist.

The formal semantics of S-keys and F-keys have been given in [6] using rules, but the combination of S-keys and F-keys with ontology alignments for data interlinking is not formally addressed. In this paper, we address it using description logics.

Different approaches to incorporate keys and functional dependencies to description logics have been proposed. Keys may be treated as a new concept constructor [11,32] or as global constraints in a separate key box (KBox) [12,13,23,24], which is the option that we follow in this paper. The goal of these approaches is to study the decidability of reasoning with keys or functional dependencies in specific description logics. Here, we do not address automated reasoning with link keys. Instead, we use the formalism of description logics to provide the semantics of keys and link keys. This allows us to ground their legitimacy in generating links across RDF datasets. In addition, it gives us the means to compare keys and link keys on the basis of their entailments and the links they generate.

3.Preliminaries

This section introduces minimal notions and notations used throughout the entire paper. We assume that the reader is familiar with the basics of description logics (DLs) [28].

In this paper, ontologies will be the combination of a schema and a dataset, and they will be modelled as DL knowledge bases.

Thus, a schema is modelled as a set of terminological axioms, i.e. a set of subsumption, equivalence and disjointness axioms between classes and properties: C1RC2 and p1Rp2 with R∈{⊑,⊒,≡,⊥}. A dataset is a set of assertions about individuals, i.e. a set of class and property assertions and equality statements: C(a), p(a1,a2) and a1≈a2.11 Classes, properties and individuals (C1,p1,a1,…) define the vocabulary of an ontology. Notice that we make no restriction on the language, i.e. the classes and properties of ontologies may be built with any DL constructor. The semantics of ontologies is inherited from the model-theoretic semantics of knowledge bases using DL interpretations I=(ΔI,·I).

Alignments relate entities – classes, properties, individuals – that belong to different ontologies [16]. Alignment relations between classes and properties are subsumption, equivalence and disjointness. In the case of individuals, they are related by equality. Alignment statements between classes and properties are referred to as correspondences, whereas equality statements in alignments will be called links.

We will also model alignments as knowledge bases. The difference with ontologies is that, in the case of an alignment, the TBox and ABox use two ontologies’ vocabularies. In addition, the ABox contains equality statements (links) only.

Different semantics for alignments may be found in the literature [10,34]. Here, though, we will consider the axioms of two ontologies and the correspondences and links of an alignment between them to be part of one single global ontology. Without loss of generality, we can assume that the vocabularies of O and O′ are disjoint.

In what follows, given an ontology O, we will use the letters C and p (possibly with subscripts or superscripts) to denote class and property expressions of O, respectively, and, in case another ontology O′ is considered, we will use D and q for O′. In this way, C1RC2 and p1Rp2 will be used as general axioms in O, while CRD and pRq as general correspondences in an alignment A between O and O′ (R∈{⊑,⊒,≡,⊥}).

4.Two kinds of keys in description logics

In order to compare keys and link keys, we start by reformulating the semantics of keys [6] as description logic axioms. We distinguish between several types of keys which apply in this context. Instead of S-keys and F-keys, we will speak of in-keys and eq-keys, respectively. The prefixes in- and eq- are shortened forms of intersection and equality. These notations are related to the conditions (1) and (2) in Definitions 3 and 4.

5.Data interlinking with keys and alignments

So far, we have considered keys independently from their use for data interlinking. Keys are able to identify duplicate resources within the same dataset and links between resources from different datasets described using the same ontologies. But as soon as the datasets do not share the same schema, keys alone are not enough for performing data interlinking, and alignments are required.

In this section, we uncover the implicit role of alignments in the process of data interlinking with keys. We show that data interlinking can be expressed as a direct logical consequence of the semantics of keys and alignments. We also highlight the need for completion when interlinking data with eq-keys.

Data interlinking can be formulated as an inference problem: for two given ontologies O=⟨S,D,K⟩ and O′=⟨S′,D′,K′⟩ equipped with keys and an alignment A=⟨C,L⟩ between O and O′, the problem is to check, for any pair of individual names a and b of O and O′, respectively, if the following entailment holds:

In the following, we give conditions on the schemas S and S′, the datasets D and D′, the set of class and property correspondences C, and the set of (known) links L, that, in the presence of a key κ∈K, are sufficient for inferring a (new) link a≈b. These conditions change depending on whether κ is an in-key or an eq-key, as specified in Theorem 1 and Theorem 2 below. These two theorems provide the logical grounds of data interlinking with keys and alignments.

Theorem 1 logically grounds data interlinking with in-keys and ontology alignments: if we know that the properties p1,…,pk are an in-key for a class C in O, and that, according to an alignment A, C subsumes a class D of O′ and p1,…,pk pairwise subsume properties q1,…,qk of O′, then, for every pair of instances a of C and b of D, the key will generate a same-as link between a and b if, for all i∈{1,…,k}, a has for pi a value ci which is equal to a value di that b has for qi.

Theorem 2 provides the logical basis of data interlinking with eq-keys and alignments. Note that unlike Theorem 1, p1,…,pk are required to be pairwise equivalent to q1,…,qk. Moreover, in order to generate a same-as link between a and b, we need to know all the values that a and b may have for pi and qi, respectively, and that these values are the same. This local completeness is expressed as axioms in the ontology schemas S and S′.

Notice that in both theorems we only address the case when property values are individuals, i.e. when keys are composed of object properties only. The case when property values are literals, i.e. keys with datatype properties, does not make a difference for our purpose (although, in this case, the comparison of property values is based on equality and not on an initial set of known same-as links L). Also, the case when instances are related to the same individual name – e.g. p(a,c), q(b,c) – is covered by the theorem too, as it is enough to add links of type c≈c to L.

Another remark on Theorems 1 and 2 is that only one key of O and no key of O′ is needed to infer links. Actually, under the assumptions of the theorems, by Proposition 5, {q}i=1k is guaranteed to be an in-key (in Theorem 1) or an eq-key (Theorem 2) for the class D.

Even though Theorems 1 and 2 are not difficult to prove, they highlight some peculiarities of data interlinking with keys and alignments that have not received attention in the literature: the fact that equivalence of properties is not required for interlinking with in-keys, and that local completeness is necessary for interlinking with eq-keys.

It is possible to provide semantic versions of Theorems 1 and 2 in which the antecedent axioms are not asserted in the ontologies and alignments but inferred from them (e.g. O,O′,A⊧({p1,…,pk}keyinC) instead of ({p1,…,pk}keyinC)∈K). We have decided to present the asserted versions to stress the nature of every axiom (mapping, data, schema knowledge or links).

We finish this section with the definition of the link set generated by a key.

In the following sections, we will introduce link keys and formalise data interlinking with link keys in the same manner. We will then show that data interlinking with link keys is more general than data interlinking with keys and alignments.

6.Link keys

We define three different types of link keys: weak, plain and strong link keys. They all allow to find links between two datasets, but they differ on whether they allow the existence of different resources (duplicates) satisfying the key conditions within each of the datasets: weak link keys allow them; plain link keys allow them only among the non-linked resources; strong link keys disallow them all.

This distinction provides us with the right framework in which to compare link keys and keys and alignments: keys and alignments correspond to strong link keys (Theorem 5), though data interlinking may be possible with weak link keys when strong link keys do not exist (Theorem 6). Plain link keys fill the gap between weak and strong link keys.

The distinction between weak, plain and strong link keys is important in practice too: weak link keys can be used for data interlinking; strong link keys can be used for both data interlinking and duplicate detection, i.e. for discovering same-as statements between individuals of the same dataset; plain link keys lie between weak and plain link keys, as they can be used for data interlinking and for finding duplicates among the linked individuals.

6.1.Semantics of link keys

The semantics of link keys considered in [19] is reproduced in Definition 7. It is natural to extend this semantics to eq-keys too, and we do so in Definition 8. These kinds of link keys will be referred to as weak link keys.

Definition 7

Definition 7(Weak in-link key).

A weak in-link key assertion, or simply a weak in-link key, has the form

({⟨p1,q1⟩,…,⟨pk,qk⟩}linkkeyinw⟨C,D⟩)

where p1,…,pk and q1,…,qk are properties and C and D are classes.

An interpretation I satisfies ({⟨p1,q1⟩,…,⟨pk,qk⟩}linkkeyinw⟨C,D⟩) if, for any δ∈CI and η∈DI,

p1I(δ)∩q1I(η)≠∅,…,pkI(δ)∩qkI(η)≠∅impliesδ=η.

Note that the above definition does not specify to which ontology vocabulary the classes and properties of a link key belong. In practice, though, the classes C and D, and the properties {pi}i=1k and {qi}i=1k belong to different ontology schemas, and the instances of C and D to different datasets. This will become explicit in Section 7 when we formalise data interlinking with link keys. In addition, note that the definition does not say that the properties and classes of a link key are semantically aligned, neither via an equivalence relation nor via a subsumption relation.

Weak eq-link keys are defined below.

Definition 8

Definition 8(Weak eq-link key).

A weak eq-link key assertion, or simply a weak eq-link key, has the form

({⟨p1,q1⟩,…,⟨pk,qk⟩}linkkeyeqw⟨C,D⟩)

where p1,…,pk and q1,…,qk are properties and C and D are classes.

An interpretation I satisfies ({⟨p1,q1⟩,…,⟨pk,qk⟩}linkkeyinw⟨C,D⟩) if, for any δ∈CI and η∈DI,

p1I(δ)=q1I(η)≠∅,…,pkI(δ)=qkI(η)≠∅impliesδ=η.

It is worth noting that every key can be expressed as a link key. Indeed, ({p1,…,pk}keyxC) is equivalent to ({⟨p1,p1⟩,…,⟨pk,pk⟩}linkkeyxw⟨C,C⟩), with x∈{in,eq}.

Weak link keys are called weak because they are not necessarily composed of keys. Instead, strong link keys, introduced below, always embed two keys. For this reason, they are closely related to keys and alignments, as we formally state in Theorem 5. We only give the definition of strong in-link keys, as strong eq-link keys can be defined analogously.

Definition 9

Definition 9(Strong in-link key).

A strong in-link key assertion, or simply a strong in-link key, has the form

({⟨p1,q1⟩,…,⟨pk,qk⟩}linkkeyins⟨C,D⟩)

where p1,…,pk and q1,…,qk are properties and C and D are classes.

An interpretation I satisfies ({⟨p1,q1⟩,…,⟨pk,qk⟩}linkkeyins⟨C,D⟩) if

• 1. I⊧({⟨p1,q1⟩,…,⟨pk,qk⟩}linkkeyinw⟨C,D⟩)

• 2. I⊧({p1,…,pk}keyinC)

• 3. I⊧({q1,…,qk}keyinD)

Both strong and weak link keys enable to find links between two different datasets, but strong link keys do more. Indeed, since the properties of a strong link key are keys for the classes separately then they can be used for finding same-as statements between individuals of the same dataset, i.e. for identifying duplicates.

Fig. 1.

Two datasets and links generated depending on the type of link keys (double = weak, dashed = plain, waved = strong).

Finally, we introduce plain link keys, which are intermediate between weak and strong link keys. Plain link keys allow to find links and to identify duplicates of the instances that are linked. As before, we only give the definition of a plain in-link key, since plain eq-link keys are defined analogously.

Definition 10

Definition 10(Plain in-link key).

A plain in-link key assertion, or simply a plain in-link key, has the form

({⟨p1,q1⟩,…,⟨pk,qk⟩}linkkeyinp⟨C,D⟩)

where p1,…,pk and q1,…,qk are properties and C and D are classes.

An interpretation I satisfies ({⟨p1,q1⟩,…,⟨pk,qk⟩}linkkeyinp⟨C,D⟩) if, for any δ∈CI and η∈DI,

p1I(δ)∩q1I(η)≠∅,…,pkI(δ)∩qkI(η)≠∅

implies:

• 1. δ=η,

• 2. for any δ′∈CI, p1I(δ)∩p1I(δ′)≠∅, …,pkI(δ)∩pkI(δ′)≠∅ implies δ=δ′,

• 3. for any η′∈DI,

  q1I(η)∩q1I(η′)≠∅, …,qkI(η)∩qkI(η′)≠∅ implies η=η′.

Figure 1 shows the differences between weak, plain and strong link keys on two datasets D and D′:

D={p(a1,c1),p(a1,c2),C(a1),p(a2,c2),C(a2),C(a3),p(a3,c3),C(a4),p(a4,c3)}D′={q(b1,d1),q(b1,d2),D(b1),q(b2,d2),D(b2),D(b3),q(b3,d3),D(b4),q(b4,d3)}

with the initial set of links L={c1≈d1}. Consider the in-link key ({⟨p,q⟩}linkkeyiny⟨C,D⟩). Depending on the value of y, it will generate:

weak:	a1≈b1 (double-line arrow),
plain:	plus a1≈a2 and b1≈b2 (dashed arrows),
strong:	plus a3≈a4 and b3≈b4 (wave arrows).

The question may be raised whether it is justified to link resources by key-like conditions when these conditions are not considered as keys (as in weak and plain link keys). This is for the same reason that in some context it may be enough to call people by their first name (e.g. in a nuclear family), in some another to call them by their last name (e.g. in a student class), and yet in other contexts, first name and last name may not be sufficient and birth date and birth place have to be used too (e.g. in a country). Here, the context is provided by what belongs to both datasets. It is not necessary that such a link key exists (there may be two students with the same last name in a class), but sometimes it does. In such cases, there would be no reason to prevent using it.

Fig. 2.

Fragments of the Insee and IGN ontologies and their alignment.

As it was done for keys in Definition 5, it is possible to define hybrid weak, plain and strong link keys by bringing together the in- and eq-conditions:

({⟨pi,qi⟩}i=1k{⟨rj,sj⟩}j=1llinkkeyy⟨C,D⟩)

with y∈{w,p,s}.

Alignments may be naturally extended to include a set of link keys. From here on, given two ontologies O and O′ equipped with keys, an alignment A between O and O′ will be a triple A=⟨C,L,LK⟩ which, in addition to a set of class and property correspondences C and a link set L, has a set LK of link keys between the vocabularies of O and O′ as a third component.

Below we give examples of link keys in real datasets.

Example 2

Example 2(Insee-IGN).

The Insee dataset includes links to the IGN dataset (French National Geographic Institute).55 There exist owl:sameAs links between the resources representing the French communes, arrondissements, departments and regions, gathered together in the two datasets using the same class names. These links can be found by comparing the Insee codes, which are declared in both datasets – using the ins:codeINSEE property in the Insee dataset and ign:numInsee in the IGN dataset.66 The considered fragment of the IGN ontology is depicted in Fig. 2.

We have checked the different link key conditions for the property pair ⟨ins:codeINSEE,ign:numInsee⟩ on the union of the Insee and IGN datasets taking into account the existing owl:sameAs links. They are strong in-link keys for ⟨ins:Com,ign:Com⟩, ⟨ins:Arr,ign:Arr⟩, ⟨ins:Dép,ign:Dép⟩ and ⟨ins:Rég,ign:Rég⟩. Formally:

I∗⊧({⟨ins:codeINSEE,ign:numInsee⟩}linkkeyins⟨ins:Com,ign:Com⟩)I∗⊧({⟨ins:codeINSEE,ign:numInsee⟩}linkkeyins⟨ins:Arr,ign:Arr⟩)I∗⊧({⟨ins:codeINSEE,ign:numInsee⟩}linkkeyins⟨ins:Dép,ign:Dép⟩)I∗⊧({⟨ins:codeINSEE,ign:numInsee⟩}linkkeyins⟨ins:Rég,ign:Rég⟩)

where I∗ is a canonical interpretation of the RDF graph resulting from the union of the Insee and IGN datasets whose linked individuals are merged.

Let us consider the other properties of Example 1. The property rdfs:label is used in the IGN dataset in the same way as ins:nom is used in the Insee dataset. Instead of ins:subdivisionDe, however, IGN uses the three properties ign:arr, ign:dpt and ign:region to declare the arrondissement, department and region an administrative unit belongs to. We have checked the different link key conditions for the combinations of these properties in the scope of the class pairs ⟨ins:Com,ign:Com⟩, ⟨ins:Arr,ign:Arr⟩, ⟨ins:Dép,ign:Dép⟩ and ⟨ins:Rég,ign:Rég⟩. This has been performed in the graph resulting from the union of the Insee graph, extended by transitivity of subdivisionDe, and the IGN graph, and again considering the owl:sameAs links. This generalises to the fully inferred RDF graph, as no other axiom of neither the Insee ontology nor the IGN ontology may have an impact on the satisfiability of the examined link key axioms. As one would expect, the property pair ⟨ins:nom,rdfs:label⟩ is a strong in-link key for ⟨ins:Dép,ign:Dép⟩ and ⟨ins:Rég,ign:Rég⟩. The property pairs ⟨ins:subdivisionDe,ign:arr⟩ and ⟨ins:subdivisionDe,ign:dpt⟩ with ⟨ins:nom,rdfs:label⟩ constitute weak (and plain) in-link keys for the class pairs ⟨ins:Com,ign:Com⟩ and ⟨ins:Arr,ign:Arr⟩, respectively. They are not strong link keys because, as explained in Example 1, subdivisionDe must be used as an eq-key. They are not eq-link keys either because ign:arr (as well as ign:dpt) refers to a single administrative unit, though subdivisionDe refers to several administrative units due to transitivity. Formally:

I∗⊧({⟨ins:nom,rdfs:label⟩,⟨ins:subdivisionDe,ign:arr⟩}linkkeyinw⟨ins:Com,ign:Com⟩)I∗⊧({⟨ins:nom,rdfs:label⟩,⟨ins:subdivisionDe,ign:dpt⟩}linkkeyinw⟨ins:Arr,ign:Arr⟩)I∗⊧({⟨ins:nom,rdfs:label⟩}linkkeyins⟨ins:Dép,ign:Dép⟩)I∗⊧({⟨ins:nom,rdfs:label⟩}linkkeyins⟨ins:Rég,ign:Rég⟩)

where I∗ is a canonical interpretation of the aforesaid RDF graph whose linked individuals are merged.

Obviously, the above link keys could be used for rediscovering the links.

At present, there exist tools for discovering weak in-link keys [7] and hybrid weak link keys [8].