On the relation between keys and link keys for data interlinking

Abstract

Both keys and their generalisation, link keys, may be used to perform data interlinking, i.e. finding identical resources in different RDF datasets. However, the precise relationship between keys and link keys has not been fully determined yet. A common formal framework encompassing both keys and link keys is necessary to ensure the correctness of data interlinking tools based on them, and to determine their scope and possible overlapping. In this paper, we provide a semantics for keys and link keys within description logics. We determine under which conditions they are legitimate to generate links. We provide conditions under which link keys are logically equivalent to keys. In particular, we show that data interlinking with keys and ontology alignments can be reduced to data interlinking with link keys, but not the other way around.

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, $$\begin{array}{c}\{\mathsf{creator}\mathrm{,}\mathsf{title}\}\mathrm{key}\mathsf{Book}\end{array}$$ states that, if two instances of the class Book match on values for the properties creator and title then the two instances are the same.

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 $\mathsf{creator}\equiv \mathsf{auteur}$ , $\mathsf{title}\equiv \mathsf{titre}$ and $\mathsf{Book}\equiv \mathsf{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, $$\begin{array}{c}\{⟨\mathsf{creator}\mathrm{,}\mathsf{auteur}⟩\mathrm{,}⟨\mathsf{title}\mathrm{,}\mathsf{titre}⟩\}\mathrm{linkkey}⟨\mathsf{Book}\mathrm{,}\mathsf{Livre}⟩\end{array}$$ states that, if two instances of the classes Book and Livre, respectively, match on values for the properties creator and auteur, and for the properties title and titre, then they are the same instance. Unlike the previous key, this link key could be directly used to interlink the books of English and French libraries without the need of any ontology alignment.

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.

Definition 1 (Ontology).

An ontology is a knowledge base $\mathcal{O}=⟨\mathcal{S}\mathrm{,}\mathcal{D}⟩$ made up of a terminological box (TBox) $\mathcal{S}$ and an assertional box (ABox) $\mathcal{D}$ . $\mathcal{S}$ and $\mathcal{D}$ will be referred to as the schema and dataset of $\mathcal{O}$ .

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: ${\mathit{C}}_1\mathcal{R}{\mathit{C}}_2$ and ${\mathit{p}}_1\mathcal{R}{\mathit{p}}_2$ with $\mathcal{R}\in \{⊑\mathrm{,}⊒\mathrm{,}\equiv \mathrm{,}\perp \}$ . A dataset is a set of assertions about individuals, i.e. a set of class and property assertions and equality statements: $\mathit{C}\mathrm{(}\mathit{a}\mathrm{)}$ , $\mathit{p}\mathrm{(}{\mathit{a}}_1\mathrm{,}{\mathit{a}}_2\mathrm{)}$ and ${\mathit{a}}_1\approx {\mathit{a}}_2$ .1

¹

Notice that “≈” is a symbol of the language, which is interpreted as equality. More specifically, for any DL interpretation $\mathcal{I}$ , $\mathcal{I}\vDash \mathit{a}\approx \mathit{b}$ iff ${\mathit{a}}^{\mathcal{I}}={\mathit{b}}^{\mathcal{I}}$ .

Classes, properties and individuals ( ${\mathit{C}}_1\mathrm{,}{\mathit{p}}_1\mathrm{,}{\mathit{a}}_1\mathrm{,}\dots$ ) 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 $\mathcal{I}=\mathrm{(}{\mathrm{\Delta }}^{\mathcal{I}}\mathrm{,}{·}^{\mathcal{I}}\mathrm{)}$ .

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.

Definition 2 (Alignment).

Let $\mathcal{O}=⟨\mathcal{S}\mathrm{,}\mathcal{D}⟩$ and ${\mathcal{O}}^{\prime }=⟨{\mathcal{S}}^{\prime }\mathrm{,}{\mathcal{D}}^{\prime }⟩$ be two ontologies. An alignment between $\mathcal{O}$ and ${\mathcal{O}}^{\prime }$ is a knowledge base ${\mathcal{A}}_{\mathcal{O}\mathrm{,}{\mathcal{O}}^{\prime }}=⟨{\mathcal{C}}_{\mathcal{O}\mathrm{,}{\mathcal{O}}^{\prime }}\mathrm{,}{\mathcal{L}}_{\mathcal{O}\mathrm{,}{\mathcal{O}}^{\prime }}⟩$ where ${\mathcal{C}}_{\mathcal{O}\mathrm{,}{\mathcal{O}}^{\prime }}$ is composed of class and property axioms $\mathit{C}\mathcal{R}\mathit{D}$ and $\mathit{p}\mathcal{R}\mathit{q}$ with $\mathcal{R}\in \{⊑\mathrm{,}⊒\mathrm{,}\equiv \mathrm{,}\perp \}$ , C and p are class and property expressions in $\mathcal{O}$ ’s vocabulary and D and q are class and property expressions in ${\mathcal{O}}^{\prime }$ ’s vocabulary, and ${\mathcal{L}}_{\mathcal{O}\mathrm{,}{\mathcal{O}}^{\prime }}$ is composed of equality statements $\mathit{a}\approx \mathit{b}$ where a is an individual name in $\mathcal{O}$ ’s vocabulary and b an individual name in ${\mathcal{O}}^{\prime }$ ’s vocabulary. The axioms in ${\mathcal{C}}_{\mathcal{O}\mathrm{,}{\mathcal{O}}^{\prime }}$ will be referred to as correspondences and the axioms in ${\mathcal{L}}_{\mathcal{O}\mathrm{,}{\mathcal{O}}^{\prime }}$ as links. If no confusion arises, ${\mathcal{A}}_{\mathcal{O}\mathrm{,}{\mathcal{O}}^{\prime }}$ , ${\mathcal{C}}_{\mathcal{O}\mathrm{,}{\mathcal{O}}^{\prime }}$ and ${\mathcal{L}}_{\mathcal{O}\mathrm{,}{\mathcal{O}}^{\prime }}$ will be replaced by $\mathcal{A}$ , $\mathcal{C}$ and $\mathcal{L}$ .

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 $\mathcal{O}$ and ${\mathcal{O}}^{\prime }$ are disjoint.

In what follows, given an ontology $\mathcal{O}$ , we will use the letters C and p (possibly with subscripts or superscripts) to denote class and property expressions of $\mathcal{O}$ , respectively, and, in case another ontology ${\mathcal{O}}^{\prime }$ is considered, we will use D and q for ${\mathcal{O}}^{\prime }$ . In this way, ${\mathit{C}}_1\mathcal{R}{\mathit{C}}_2$ and ${\mathit{p}}_1\mathcal{R}{\mathit{p}}_2$ will be used as general axioms in $\mathcal{O}$ , while $\mathit{C}\mathcal{R}\mathit{D}$ and $\mathit{p}\mathcal{R}\mathit{q}$ as general correspondences in an alignment $\mathcal{A}$ between $\mathcal{O}$ and ${\mathcal{O}}^{\prime }$ ( $\mathcal{R}\in \{⊑\mathrm{,}⊒\mathrm{,}\equiv \mathrm{,}\perp \}$ ).

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.

4.1. Semantics of keys

In what follows, given a DL interpretation $\mathcal{I}=\mathrm{(}{\mathrm{\Delta }}^{\mathcal{I}}\mathrm{,}{·}^{\mathcal{I}}\mathrm{)}$ , a property p, and a domain individual $\mathit{\delta }\in {\mathrm{\Delta }}^{\mathcal{I}}$ , ${\mathit{p}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}$ will denote the set of individuals related to δ through p, i.e. ${\mathit{p}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}=\{\mathit{\eta }\in {\mathrm{\Delta }}^{\mathcal{I}}:\mathrm{(}\mathit{\delta }\mathrm{,}\mathit{\eta }\mathrm{)}\in {\mathit{p}}^{\mathcal{I}}\}$ .

Definition 3 (in-key).

An in-key assertion, or simply an in-key, has the form $$\begin{array}{c}\mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{in}}\mathit{C}\mathrm{)}\end{array}$$ where ${\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}$ are properties and C is a class.

An interpretation $\mathcal{I}$ satisfies $\mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{in}}\mathit{C}\mathrm{)}$ if, for any $\mathit{\delta }\mathrm{,}{\mathit{\delta }}^{\prime }\in {\mathit{C}}^{\mathcal{I}}$ , $$\begin{array}{ll}\hfill & {\mathit{p}}_1^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}\cap {\mathit{p}}_1^{\mathcal{I}}\mathrm{\left(}{\mathit{\delta }}^{\prime }\mathrm{\right)}\ne \varnothing \mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}\cap {\mathit{p}}_{\mathit{k}}^{\mathcal{I}}\mathrm{\left(}{\mathit{\delta }}^{\prime }\mathrm{\right)}\ne \varnothing \\ \text{(1)}& \hfill & \text{implies}\mathit{\delta }={\mathit{\delta }}^{\prime }.\end{array}$$

Definition 4 (eq-key).

An eq-key assertion, or simply an eq-key, has the form $$\begin{array}{c}\mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{eq}}\mathit{C}\mathrm{)}\end{array}$$ where ${\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}$ are properties and C is a class.

An interpretation $\mathcal{I}$ satisfies $\mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{eq}}\mathit{C}\mathrm{)}$ if, for any $\mathit{\delta }\mathrm{,}{\mathit{\delta }}^{\prime }\in {\mathit{C}}^{\mathcal{I}}$ ,2

²

By ${\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}={\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{\delta }}^{\prime }\mathrm{)}\ne \varnothing$ we mean ${\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}={\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{\delta }}^{\prime }\mathrm{)}$ and ${\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{\delta }}^{\prime }\mathrm{)}\ne \varnothing$ , which implies ${\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}\ne \varnothing$ ( $\mathit{i}=1\mathrm{,}\dots \mathrm{,}\mathit{k}$ ).

$$\begin{array}{ll}\hfill & {\mathit{p}}_1^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}={\mathit{p}}_1^{\mathcal{I}}\mathrm{\left(}{\mathit{\delta }}^{\prime }\mathrm{\right)}\ne \varnothing \mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}={\mathit{p}}_{\mathit{k}}^{\mathcal{I}}\mathrm{\left(}{\mathit{\delta }}^{\prime }\mathrm{\right)}\ne \varnothing \\ \text{(2)}& \hfill & \text{implies}\mathit{\delta }={\mathit{\delta }}^{\prime }.\end{array}$$

According to Definition 3, if two instances of a class share at least one value for each of the properties of an in-key for the class, then we can infer that they are the same instance. This is formalised in Proposition 1.

Proposition 1.

The following holds: $$\begin{array}{}\text{(3)}& \begin{array}{cc}\hfill & \hfill \mathit{C}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{,}{\{{\mathit{p}}_{\mathit{i}}\mathrm{(}\mathit{a}\mathrm{,}{\mathit{c}}_{\mathit{i}}\mathrm{)}\}}_{\mathit{i}=1}^{\mathit{k}}\mathrm{,}\\ \hfill & \hfill \mathit{C}\mathrm{(}\mathit{b}\mathrm{)}\mathrm{,}{\{{\mathit{p}}_{\mathit{i}}\mathrm{(}\mathit{b}\mathrm{,}{\mathit{d}}_{\mathit{i}}\mathrm{)}\}}_{\mathit{i}=1}^{\mathit{k}}\mathrm{,}\\ \hfill & \hfill \mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{in}}\mathit{C}\mathrm{)}\mathrm{,}\\ \hfill & \hfill {\{{\mathit{c}}_{\mathit{i}}\approx {\mathit{d}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}\end{array}\vDash \mathit{a}\approx \mathit{b}\end{array}$$

Proof.

This is a direct consequence of Definition 3: for any interpretation $\mathcal{I}$ satisfying all the antecedent axioms of the entailment, ${\mathit{a}}^{\mathcal{I}}$ and ${\mathit{b}}^{\mathcal{I}}$ will belong to ${\mathit{C}}^{\mathcal{I}}$ and will share one value for each of the properties of the in-key, hence ${\mathit{a}}^{\mathcal{I}}$ will be equal to ${\mathit{b}}^{\mathcal{I}}$ .  □

Similarly, according to Definition 4, given an eq-key for a class and two instances of the class, we can infer that they are the same instance if they share all values (and at least one) for each of the properties of the key. However, we need to be sure that all known values indeed are all values that the instances may have. This is stated in Proposition 2.

Proposition 2.

The following holds: $$\begin{array}{}\text{(4)}& \begin{array}{cc}\hfill & \hfill \mathit{C}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{,}{\left\{{\mathit{p}}_{\mathit{i}}\mathrm{\right(}\mathit{a}\mathrm{,}{\mathit{c}}_{\mathit{i}}^1\mathrm{)}\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{i}}\mathrm{(}\mathit{a}\mathrm{,}{\mathit{c}}_{\mathit{i}}^{{\mathit{r}}_{\mathit{i}}}\mathrm{\left)}\right\}}_{\mathit{i}=1}^{\mathit{k}}\mathrm{,}\\ \hfill & \hfill {\{\{\mathit{a}\}⊑\forall {\mathit{p}}_{\mathit{i}}.\{{\mathit{c}}_{\mathit{i}}^1\mathrm{,}\dots \mathrm{,}{\mathit{c}}_{\mathit{i}}^{{\mathit{r}}_{\mathit{i}}}\left\}\right\}}_{\mathit{i}=1}^{\mathit{k}}\mathrm{,}\\ \hfill & \hfill \mathit{C}\mathrm{(}\mathit{b}\mathrm{)}\mathrm{,}{\left\{{\mathit{p}}_{\mathit{i}}\mathrm{\right(}\mathit{b}\mathrm{,}{\mathit{d}}_{\mathit{i}}^1\mathrm{)}\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{i}}\mathrm{(}\mathit{b}\mathrm{,}{\mathit{d}}_{\mathit{i}}^{{\mathit{r}}_{\mathit{i}}}\mathrm{\left)}\right\}}_{\mathit{i}=1}^{\mathit{k}}\mathrm{,}\\ \hfill & \hfill {\{\{\mathit{b}\}⊑\forall {\mathit{p}}_{\mathit{i}}.\{{\mathit{d}}_{\mathit{i}}^1\mathrm{,}\dots \mathrm{,}{\mathit{d}}_{\mathit{i}}^{{\mathit{r}}_{\mathit{i}}}\left\}\right\}}_{\mathit{i}=1}^{\mathit{k}}\mathrm{,}\\ \hfill & \hfill \mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{eq}}\mathit{C}\mathrm{)}\mathrm{,}\\ \hfill & \hfill {\{{\mathit{c}}_{\mathit{i}}^1\approx {\mathit{d}}_{\mathit{i}}^1\mathrm{,}\dots \mathrm{,}{\mathit{c}}_{\mathit{i}}^{{\mathit{r}}_{\mathit{i}}}\approx {\mathit{d}}_{\mathit{i}}^{{\mathit{r}}_{\mathit{i}}}\}}_{\mathit{i}=1}^{\mathit{k}}\end{array}\vDash \mathit{a}\approx \mathit{b}\end{array}$$

Proof.

Let $\mathcal{I}$ be an interpretation that satisfies all the antecedent axioms of the above entailment. Let us prove that $\mathcal{I}$ satisfies $\mathit{a}\approx \mathit{b}$ too. Since $\mathcal{I}\vDash {\mathit{p}}_{\mathit{i}}\mathrm{(}\mathit{a}\mathrm{,}{\mathit{c}}_{\mathit{i}}^{\mathit{l}}\mathrm{)}$ then ${\mathrm{(}{\mathit{c}}_{\mathit{i}}^{\mathit{l}}\mathrm{)}}^{\mathcal{I}}\in {\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{a}}^{\mathcal{I}}\mathrm{)}$ for $\mathit{i}=1\mathrm{,}\dots \mathrm{,}\mathit{k}$ and $\mathit{l}=1\mathrm{,}\dots \mathrm{,}{\mathit{r}}_{\mathit{i}}$ . Also, since $\mathcal{I}\vDash \{\mathit{a}\}⊑\forall {\mathit{p}}_{\mathit{i}}.\{{\mathit{c}}_{\mathit{i}}^1\mathrm{,}\dots \mathrm{,}{\mathit{c}}_{\mathit{i}}^{{\mathit{r}}_{\mathit{i}}}\}$ then ${\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{a}}^{\mathcal{I}}\mathrm{)}\subseteq {\{{\mathrm{(}{\mathit{c}}_{\mathit{i}}^{\mathit{l}}\mathrm{)}}^{\mathcal{I}}\}}_{\mathit{l}=1}^{{\mathit{r}}_{\mathit{i}}}$ . Therefore, ${\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{a}}^{\mathcal{I}}\mathrm{)}={\{{\mathrm{(}{\mathit{c}}_{\mathit{i}}^{\mathit{l}}\mathrm{)}}^{\mathcal{I}}\}}_{\mathit{l}=1}^{{\mathit{r}}_{\mathit{i}}}$ . Similarly, ${\mathit{q}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{b}}^{\mathcal{I}}\mathrm{)}={\{{\mathrm{(}{\mathit{d}}_{\mathit{i}}^{\mathit{l}}\mathrm{)}}^{\mathcal{I}}\}}_{\mathit{l}=1}^{{\mathit{r}}_{\mathit{i}}}$ . Now, since $\mathcal{I}\vDash {\mathit{c}}_{\mathit{i}}^{\mathit{l}}\approx {\mathit{d}}_{\mathit{i}}^{\mathit{l}}$ then ${\mathrm{(}{\mathit{c}}_{\mathit{i}}^{\mathit{l}}\mathrm{)}}^{\mathcal{I}}={\mathrm{(}{\mathit{d}}_{\mathit{i}}^{\mathit{l}}\mathrm{)}}^{\mathcal{I}}$ , which implies that ${\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{a}}^{\mathcal{I}}\mathrm{)}={\mathit{q}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{b}}^{\mathcal{I}}\mathrm{)}$ . Furthermore, ${\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{a}}^{\mathcal{I}}\mathrm{)}={\mathit{q}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{b}}^{\mathcal{I}}\mathrm{)}\ne \varnothing$ since ${\mathit{r}}_{\mathit{i}}⩾1$ . Additionally, since $\mathcal{I}\vDash \mathit{C}\mathrm{(}\mathit{a}\mathrm{)}$ and $\mathcal{I}\vDash \mathit{C}\mathrm{(}\mathit{b}\mathrm{)}$ then ${\mathit{a}}^{\mathcal{I}}\mathrm{,}{\mathit{b}}^{\mathcal{I}}\in {\mathit{C}}^{\mathcal{I}}$ . Finally, since $\mathcal{I}\vDash \mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{eq}}\mathit{C}\mathrm{)}$ , and we have ${\mathit{a}}^{\mathcal{I}}\mathrm{,}{\mathit{b}}^{\mathcal{I}}\in {\mathit{C}}^{\mathcal{I}}$ and ${\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{a}}^{\mathcal{I}}\mathrm{)}={\mathit{q}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{b}}^{\mathcal{I}}\mathrm{)}\ne \varnothing$ for $\mathit{i}=1\dots \mathrm{,}\mathit{k}$ , then we can infer that ${\mathit{a}}^{\mathcal{I}}={\mathit{b}}^{\mathcal{I}}$ , i.e. $\mathcal{I}\vDash \mathit{a}\approx \mathit{b}$ .  □

Thus, unlike in-keys, eq-keys require a local closed world assumption – represented in Proposition 2 by the axioms $\{\mathit{a}\}⊑\forall {\mathit{p}}_{\mathit{i}}.\{{\mathit{c}}_{\mathit{i}}^1\mathrm{,}\dots \mathrm{,}{\mathit{c}}_{\mathit{i}}^{{\mathit{r}}_{\mathit{i}}}\}$ and $\{\mathit{b}\}⊑\forall {\mathit{q}}_{\mathit{i}}.\{{\mathit{d}}_{\mathit{i}}^1\mathrm{,}\dots \mathrm{,}{\mathit{d}}_{\mathit{i}}^{{\mathit{r}}_{\mathit{i}}}\}$ ( $\mathit{i}=1\mathrm{,}\dots \mathrm{,}\mathit{k}$ ) – which, even though it is generally advised to avoid in the context of the semantic web and linked open data, it is also expected to be made in certain controlled scenarios.

Notice that Proposition 2 requires the logic to be able to express nominals and value restrictions. All our results are agnostic of the used logical language but those referring to the use of eq-keys and eq-link keys for data interlinking.

The semantics of owl:hasKey in OWL2 corresponds to the semantics of in-keys but restricted to being applied to named instances only (thus excluding blank nodes).

Although in-keys and eq-keys have been introduced separately, it is also possible to consider a hybrid notion of key.

Definition 5 (Hybrid key).

A key assertion, or simply a key, has the form $$\begin{array}{c}\mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}\{{\mathit{q}}_1\mathrm{,}\dots \mathrm{,}{\mathit{q}}_{\mathit{l}}\}\mathrm{key}\mathit{C}\mathrm{)}\end{array}$$ where ${\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}$ and ${\mathit{q}}_1\mathrm{,}\dots \mathrm{,}{\mathit{q}}_{\mathit{l}}$ are properties and C is a class.

An interpretation $\mathcal{I}$ satisfies the key $\mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}\{{\mathit{q}}_1\mathrm{,}\dots \mathrm{,}{\mathit{q}}_{\mathit{l}}\}\mathrm{key}\mathit{C}\mathrm{)}$ if, for any $\mathit{\delta }\mathrm{,}{\mathit{\delta }}^{\prime }\in {\mathit{C}}^{\mathcal{I}}$ , $$\begin{array}{ll}\hfill & {\mathit{p}}_1^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}\cap {\mathit{p}}_1^{\mathcal{I}}\mathrm{\left(}{\mathit{\delta }}^{\prime }\mathrm{\right)}\ne \varnothing \mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}\cap {\mathit{p}}_{\mathit{k}}^{\mathcal{I}}\mathrm{\left(}{\mathit{\delta }}^{\prime }\mathrm{\right)}\ne \varnothing \mathrm{,}\\ \hfill & {\mathit{q}}_1^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}={\mathit{q}}_1^{\mathcal{I}}\mathrm{\left(}{\mathit{\delta }}^{\prime }\mathrm{\right)}\ne \varnothing \mathrm{,}\dots \mathrm{,}{\mathit{q}}_{\mathit{l}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}={\mathit{q}}_{\mathit{l}}^{\mathcal{I}}\mathrm{\left(}{\mathit{\delta }}^{\prime }\mathrm{\right)}\ne \varnothing \\ \hfill & \text{implies}\mathit{\delta }={\mathit{\delta }}^{\prime }.\end{array}$$

From here on, an ontology $\mathcal{O}$ will be a triple $\mathcal{O}=⟨\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}⟩$ which, besides the schema $\mathcal{S}$ (TBox) and dataset $\mathcal{D}$ (ABox), has as a third component a set of keys $\mathcal{K}$ (KBox).

Example 1 below provides examples of in-keys and eq-keys in real RDF datasets.

Example 1 (Insee).

Insee is the French institution in charge of collecting and publishing information about French economy and society. Part of the Insee data is available in the form of RDF triples and can be downloaded as an RDF dump or queried through a SPARQL endpoint.3

³

http://rdf.insee.fr

Insee ontologies are available too. We only consider the Insee data related to administrative districts (COG dataset).

The Insee vocabulary comprises four class names for describing the main administrative divisions in France: Commune, Arrondissement, Département and Région. Among the properties of these classes, we find the datatype property nom (used to specify the name of an administrative division), the object property subdivisionDe (to specify that an administrative division is subdivision of another one, e.g. that the commune of Grenoble is a subdivision of the Isère department) and the datatype property codeINSEE (which is an identifier for territories, including administrative divisions, and can be thought of as the key in the Insee database). The property subdivisionDe is declared to be transitive in the Insee ontology. This fragment of the Insee ontology is depicted in Fig. 2.

No owl:hasKey axiom is declared in the Insee ontology. Nevertheless, we have checked the in-key and eq-key conditions for the properties and classes mentioned before. We have done so in the RDF graph of Insee extended with the transitivity of subdivisionDe. This generalises to the fully inferred graph as no other axiom of the Insee ontology may have an impact on the satisfiability of the examined key axioms.

As expected, the codeINSEE property is an in-key for Commune, Arrondissement, Département and Région. Formally: $$\begin{array}{ll}\hfill & {\mathcal{I}}_{\mathrm{Insee}}^{\ast }\vDash \mathrm{(}\{\mathsf{codeINSEE}\}{\mathrm{key}}_{\mathrm{in}}\mathsf{Commune}\mathrm{)}\\ \hfill & {\mathcal{I}}_{\mathrm{Insee}}^{\ast }\vDash \mathrm{(}\{\mathsf{codeINSEE}\}{\mathrm{key}}_{\mathrm{in}}\mathsf{Arrondissement}\mathrm{)}\\ \hfill & {\mathcal{I}}_{\mathrm{Insee}}^{\ast }\vDash \mathrm{(}\{\mathsf{codeINSEE}\}{\mathrm{key}}_{\mathrm{in}}\mathsf{Département}\mathrm{)}\\ \hfill & {\mathcal{I}}_{\mathrm{Insee}}^{\ast }\vDash \mathrm{(}\{\mathsf{codeINSEE}\}{\mathrm{key}}_{\mathrm{in}}\mathsf{Région}\mathrm{)}\end{array}$$ where ${\mathcal{I}}_{\mathrm{Insee}}^{\ast }$ is the natural DL interpretation of the inferred Insee graph.4

⁴

More specifically, this is the interpretation whose domain is made up of all IRIs and literals of the Insee graph (there are no blank nodes), it interprets domain individuals as themselves, and classes and properties as their extensions in the graph.

Concerning the property nom, it turns out to be an in-key for Département and Région, but neither for Commune nor Arrondissement. Indeed, there exist different communes (and arrondissements) sharing the same name. For instance, Bully may refer to three different communes: Bully in the department of Loire, Bully in Rhône and Bully in Seine-Maritime. However, there is no pair of communes of the same department sharing the same name. In fact, nom and subdivisionDe, when put together, form a key for the class Commune. The property subdivisionDe, though, must be treated in the sense of eq-keys. This is because, since subdivisionDe is a transitive property, all French communes share (at least) a value for subdivisionDe, namely, the Insee entity representing the country France. The same holds for the class Arrondissement. Formally (note that we use hybrid keys): $$\begin{array}{ll}\hfill {\mathcal{I}}_{\mathrm{Insee}}^{\ast }& \vDash \mathrm{(}\{\mathsf{nom}\}{\mathrm{key}}_{\mathrm{in}}\mathsf{Département}\mathrm{)}\\ \hfill {\mathcal{I}}_{\mathrm{Insee}}^{\ast }& \vDash \mathrm{(}\{\mathsf{nom}\}{\mathrm{key}}_{\mathrm{in}}\mathsf{Région}\mathrm{)}\\ \hfill {\mathcal{I}}_{\mathrm{Insee}}^{\ast }& \vDash \mathrm{(}\{\mathsf{nom}\}\{\mathsf{subdivisionDe}\}\mathrm{key}\mathsf{Arrondissement}\mathrm{)}\\ \hfill {\mathcal{I}}_{\mathrm{Insee}}^{\ast }& \vDash \mathrm{(}\{\mathsf{nom}\}\{\mathsf{subdivisionDe}\}\mathrm{key}\mathsf{Commune}\mathrm{)}\end{array}$$

From here on, we will use the shortcuts Reg, Dep, Arr and Com for the corresponding Insee classes.

4.2. Relations between the different types of keys

Compared to the semantics of S-keys and F-keys defined in [6], the semantics of in-keys corresponds directly to the semantics of S-keys. This is not the case for eq-keys and F-keys. Every eq-key is an F-key but not the other way around. The equivalence would hold if condition (2) in Definition 4 were replaced by $$\begin{array}{ll}\hfill & {\mathit{p}}_1^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}={\mathit{p}}_1^{\mathcal{I}}\mathrm{\left(}{\mathit{\delta }}^{\prime }\mathrm{\right)}\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}={\mathit{p}}_{\mathit{k}}^{\mathcal{I}}\mathrm{\left(}{\mathit{\delta }}^{\prime }\mathrm{\right)}\\ \hfill & \mathit{\text{implies}}\mathit{\delta }={\mathit{\delta }}^{\prime }.\end{array}$$

The prerequisite that the sets of property values must be non-empty enables to consider in-keys as a subset of eq-keys (which does not hold between S-keys and F-keys). This result is stated in Proposition 3.

Proposition 3.

The following holds: $$\begin{array}{c}\mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{in}}\mathit{C}\mathrm{)}\vDash \mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{eq}}\mathit{C}\mathrm{)}\end{array}$$

Proof.

Let $\mathcal{I}$ be an interpretation such that $\mathcal{I}\vDash \mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{in}}\mathit{C}\mathrm{)}$ . We have to prove that $\mathcal{I}\vDash \mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{eq}}\mathit{C}\mathrm{)}$ . Let $\mathit{\delta }\mathrm{,}{\mathit{\delta }}^{\prime }\in {\mathit{C}}^{\mathcal{I}}$ such that ${\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}={\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{\delta }}^{\prime }\mathrm{)}\ne \varnothing$ ( $\mathit{i}=1\mathrm{,}\dots \mathrm{,}\mathit{k}$ ). We have to prove that $\mathit{\delta }={\mathit{\delta }}^{\prime }$ . Since ${\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}$ and ${\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{\delta }}^{\prime }\mathrm{)}$ are equal and non-empty, then ${\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}\cap {\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{\delta }}^{\prime }\mathrm{)}\ne \varnothing$ ( $\mathit{i}=1\mathrm{,}\dots \mathrm{,}\mathit{k}$ ). So we have $\mathit{\delta }\mathrm{,}{\mathit{\delta }}^{\prime }\in {\mathit{C}}^{\mathcal{I}}$ and ${\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}\cap {\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{\delta }}^{\prime }\mathrm{)}\ne \varnothing$ ( $\mathit{i}=1\mathrm{,}\dots \mathrm{,}\mathit{k}$ ). Since $\mathcal{I}\vDash \mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{in}}\mathit{C}\mathrm{)}$ , then $\mathit{\delta }={\mathit{\delta }}^{\prime }$ .  □

The converse of Proposition 3 is not true, i.e. there are eq-keys that are not in-keys. Indeed, consider the interpretation defined by $\mathrm{(}{\mathit{a}}^{\mathcal{I}}\mathrm{,}{\mathit{c}}^{\mathcal{I}}\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{a}}^{\mathcal{I}}\mathrm{,}{\mathit{d}}^{\mathcal{I}}\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{b}}^{\mathcal{I}}\mathrm{,}{\mathit{c}}^{\mathcal{I}}\mathrm{)}\in {\mathit{p}}^{\mathcal{I}}$ and ${\mathit{a}}^{\mathcal{I}}\ne {\mathit{b}}^{\mathcal{I}}$ , ${\mathit{c}}^{\mathcal{I}}\ne {\mathit{d}}^{\mathcal{I}}$ . Then $\mathcal{I}\vDash \mathrm{(}\mathit{p}{\mathrm{key}}_{\mathrm{eq}}\top \mathrm{)}$ whereas $\mathcal{I}⊭\mathrm{(}\mathit{p}{\mathrm{key}}_{\mathrm{in}}\top \mathrm{)}$ . The converse is true if the key is made up of functional properties, as stated in Proposition 4. Notice that it is possible to define a functional property as a property p such that for any interpretation $\mathcal{I}=\mathrm{(}{\mathrm{\Delta }}^{\mathcal{I}}\mathrm{,}{·}^{\mathcal{I}}\mathrm{)}$ and for any $\mathit{\delta }\in {\mathrm{\Delta }}^{\mathcal{I}}$ then $|{\mathit{p}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}|⩽1$ . Indeed, p is functional if and only for any interpretation $\mathcal{I}=\mathrm{(}{\mathrm{\Delta }}^{\mathcal{I}}\mathrm{,}{·}^{\mathcal{I}}\mathrm{)}$ and for any $\mathit{\delta }\in {\mathrm{\Delta }}^{\mathcal{I}}$ , there exists one or no element related to δ via ${\mathit{p}}^{\mathcal{I}}$ , which is equivalent to say that $|{\mathit{p}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}|⩽1$ .

Proposition 4.

If ${\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}$ are functional, then $$\begin{array}{c}\mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{eq}}\mathit{C}\mathrm{)}\vDash \mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{in}}\mathit{C}\mathrm{)}\end{array}$$

Proof.

Let $\mathcal{I}$ be an interpretation such that $\mathcal{I}\vDash \mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{eq}}\mathit{C}\mathrm{)}$ . Let $\mathit{\delta }\mathrm{,}{\mathit{\delta }}^{\prime }\in {\mathit{C}}^{\mathcal{I}}$ such that ${\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}\cap {\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{\delta }}^{\prime }\mathrm{)}\ne \varnothing$ ( $\mathit{i}=1\mathrm{,}\dots \mathrm{,}\mathit{k}$ ). Since ${\mathit{p}}_{\mathit{i}}$ is functional, then $|{\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}|⩽1$ and $|{\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{\delta }}^{\prime }\mathrm{)}|⩽1$ , but, given that their intersection is not empty, then $|{\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}|=1$ and $|{\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{\delta }}^{\prime }\mathrm{)}|=1$ . Thus, they are equal and not empty, i.e. ${\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}={\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{\delta }}^{\prime }\mathrm{)}\ne \varnothing$ ( $\mathit{i}=1\mathrm{,}\dots \mathrm{,}\mathit{k}$ ). Since $\mathcal{I}\vDash \mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{eq}}\mathit{C}\mathrm{)}$ then we can infer that $\mathit{\delta }={\mathit{\delta }}^{\prime }$ . This proves that $\mathcal{I}\vDash \mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{in}}\mathit{C}\mathrm{)}$ .  □

Proposition 5 shows basic properties of in-keys and eq-keys that will be later used in the proofs of other theorems. In certain occasions, we will write $\mathrm{(}{\{{\mathit{p}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{key}}_{\mathit{x}}\mathit{C}\mathrm{)}$ instead of $\mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}{\mathrm{key}}_{\mathit{x}}\mathit{C}\mathrm{)}$ ( $\mathit{x}\in \{\mathrm{in}\mathrm{,}\mathrm{eq}\}$ ) to shorten too long expressions. Property (5) may be thought of as a version of Armstrong’s reflexivity axiom for functional dependencies in relational databases [5]. It is not surprising that it corresponds to one of these axioms as it deals with sets of properties. This is not the case of the other properties, as they deal with constructors not found in the relational model. Properties (6), (7) and (8) specify how keys behave with subsumption, intersection and union of classes, respectively. Properties (9) and (10) specify how keys behave with subsumption and equivalence of properties. Interestingly, (9) does not hold for eq-keys.

Proposition 5.

The following holds: $$\begin{array}{}\text{(5)}& \mathrm{\left(}{\{{\mathit{p}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{key}}_{\mathit{x}}\mathit{C}\mathrm{\right)}\vDash \mathrm{\left(}{\{{\mathit{p}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}+1}{\mathrm{key}}_{\mathit{x}}\mathit{C}\mathrm{\right)}\text{(6)}& \mathrm{\left(}{\{{\mathit{p}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{key}}_{\mathit{x}}\mathit{C}\mathrm{\right)}\mathrm{,}\mathit{C}⊒\mathit{D}\vDash \mathrm{\left(}{\{{\mathit{p}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{key}}_{\mathit{x}}\mathit{D}\mathrm{\right)}\text{(7)}& \mathrm{\left(}{\{{\mathit{p}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{key}}_{\mathit{x}}\mathit{C}\mathrm{\right)}\vDash \mathrm{(}{\{{\mathit{p}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{key}}_{\mathit{x}}\mathit{C}\sqcap \mathit{D}\mathrm{)}\text{(8)}& \mathrm{(}{\{{\mathit{p}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{key}}_{\mathit{x}}\mathit{C}\bigsqcup \mathit{D}\mathrm{)}\vDash \mathrm{\left(}{\{{\mathit{p}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{key}}_{\mathit{x}}\mathit{C}\mathrm{\right)}\text{(9)}& \mathrm{\left(}{\{{\mathit{p}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{key}}_{\mathrm{in}}\mathit{C}\mathrm{\right)}\mathrm{,}{\{{\mathit{p}}_{\mathit{i}}⊒{\mathit{q}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}\vDash \mathrm{\left(}{\{{\mathit{q}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{key}}_{\mathrm{in}}\mathit{C}\mathrm{\right)}\text{(10)}& \mathrm{\left(}{\{{\mathit{p}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{key}}_{\mathit{x}}\mathit{C}\mathrm{\right)}\mathrm{,}{\{{\mathit{p}}_{\mathit{i}}\equiv {\mathit{q}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}\vDash \mathrm{\left(}{\{{\mathit{q}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{key}}_{\mathit{x}}\mathit{C}\mathrm{\right)}\end{array}$$ with $\mathit{x}\in \{\mathrm{in}\mathrm{,}\mathrm{eq}\}$ .

Proof.

Properties (5) and (6) follow directly from Definitions 3 and 4, and Properties (7) and (8) are direct consequences of property (6).

Let us prove (9). Let $\mathcal{I}$ be an arbitrary DL interpretation such that $\mathcal{I}\vDash \mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{in}}\mathit{C}\mathrm{)}$ and $\mathcal{I}\vDash {\mathit{p}}_{\mathit{i}}⊒{\mathit{q}}_{\mathit{i}}$ ( $\mathit{i}=1\mathrm{,}\dots \mathrm{,}\mathit{k}$ ). We have to prove that $\mathcal{I}\vDash \mathrm{(}\{{\mathit{q}}_1\mathrm{,}\dots \mathrm{,}{\mathit{q}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{in}}\mathit{C}\mathrm{)}$ . Let $\mathit{\delta }\mathrm{,}{\mathit{\delta }}^{\prime }\in {\mathit{C}}^{\mathcal{I}}$ such that ${\mathit{q}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}\cap {\mathit{q}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{\delta }}^{\prime }\mathrm{)}\ne \varnothing$ ( $\mathit{i}=1\mathrm{,}\dots \mathrm{,}\mathit{k}$ ). Since $\mathcal{I}\vDash {\mathit{p}}_{\mathit{i}}⊒{\mathit{q}}_{\mathit{i}}$ then ${\mathit{q}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}\subseteq {\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}$ and ${\mathit{q}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{\delta }}^{\prime }\mathrm{)}\subseteq {\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{\delta }}^{\prime }\mathrm{)}$ , and, since ${\mathit{q}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}\cap {\mathit{q}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{\delta }}^{\prime }\mathrm{)}\ne \varnothing$ , then ${\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}\cap {\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{\delta }}^{\prime }\mathrm{)}\ne \varnothing$ ( $\mathit{i}=1\mathrm{,}\dots \mathrm{,}\mathit{k}$ ). This together with $\mathcal{I}\vDash \mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{in}}\mathit{C}\mathrm{)}$ implies $\mathit{\delta }={\mathit{\delta }}^{\prime }$ . Therefore, $\mathcal{I}\vDash \mathrm{(}\{{\mathit{q}}_1\mathrm{,}\dots \mathrm{,}{\mathit{q}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{in}}\mathit{C}\mathrm{)}$ .

Property (10) can be proven analogously.  □

In the following section, we establish when it is legitimate to combine in-keys and eq-keys with alignments for data interlinking.

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 $\mathcal{O}=⟨\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}⟩$ and ${\mathcal{O}}^{\prime }=⟨{\mathcal{S}}^{\prime }\mathrm{,}{\mathcal{D}}^{\prime }\mathrm{,}{\mathcal{K}}^{\prime }⟩$ equipped with keys and an alignment $\mathcal{A}=⟨\mathcal{C}\mathrm{,}\mathcal{L}⟩$ between $\mathcal{O}$ and ${\mathcal{O}}^{\prime }$ , the problem is to check, for any pair of individual names a and b of $\mathcal{O}$ and ${\mathcal{O}}^{\prime }$ , respectively, if the following entailment holds: $$\begin{array}{c}\mathcal{O}\mathrm{,}{\mathcal{O}}^{\prime }\mathrm{,}\mathcal{A}\vDash \mathit{a}\approx \mathit{b}\end{array}$$ This formulation also includes the particular case when $\mathcal{O}$ and ${\mathcal{O}}^{\prime }$ share the same schema, as in this case the set of correspondences is empty, i.e. $\mathcal{A}=⟨\varnothing \mathrm{,}\mathcal{L}⟩$ .

In the following, we give conditions on the schemas $\mathcal{S}$ and ${\mathcal{S}}^{\prime }$ , the datasets $\mathcal{D}$ and ${\mathcal{D}}^{\prime }$ , the set of class and property correspondences $\mathcal{C}$ , and the set of (known) links $\mathcal{L}$ , that, in the presence of a key $\mathit{\kappa }\in \mathcal{K}$ , are sufficient for inferring a (new) link $\mathit{a}\approx \mathit{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.

Let $\mathcal{O}=⟨\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}⟩$ and ${\mathcal{O}}^{\prime }=⟨{\mathcal{S}}^{\prime }\mathrm{,}{\mathcal{D}}^{\prime }\mathrm{,}{\mathcal{K}}^{\prime }⟩$ be two ontologies and $\mathcal{A}=⟨\mathcal{C}\mathrm{,}\mathcal{L}⟩$ and alignment between $\mathcal{O}$ and ${\mathcal{O}}^{\prime }$ such that

$\mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{in}}\mathit{C}\mathrm{)}\in \mathcal{K}$ , and

$\{\mathit{C}⊒\mathit{D}\}\cup {\{{\mathit{p}}_{\mathit{i}}⊒{\mathit{q}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}\subseteq \mathcal{C}$ .

Then, for any pair of individual names a and b of $\mathcal{O}$ and ${\mathcal{O}}^{\prime }$ , respectively, if

• $\{\mathit{C}\mathrm{(}\mathit{a}\mathrm{)}\}\cup {\{{\mathit{p}}_{\mathit{i}}\mathrm{(}\mathit{a}\mathrm{,}{\mathit{c}}_{\mathit{i}}\mathrm{)}\}}_{\mathit{i}=1}^{\mathit{k}}\subseteq \mathcal{D}$ ,

• $\{\mathit{D}\mathrm{(}\mathit{b}\mathrm{)}\}\cup {\{{\mathit{q}}_{\mathit{i}}\mathrm{(}\mathit{b}\mathrm{,}{\mathit{d}}_{\mathit{i}}\mathrm{)}\}}_{\mathit{i}=1}^{\mathit{k}}\subseteq {\mathcal{D}}^{\prime }$ , and

• ${\{{\mathit{c}}_{\mathit{i}}\approx {\mathit{d}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}\subseteq \mathcal{L}$ ,

then $\mathcal{O}$ , ${\mathcal{O}}^{\prime }$ , $\mathcal{A}\vDash \mathit{a}\approx \mathit{b}$ .

Proof.

Notice that $\mathit{C}⊒\mathit{D}$ and $\mathit{D}\mathrm{(}\mathit{b}\mathrm{)}$ entail $\mathit{C}\mathrm{(}\mathit{b}\mathrm{)}$ , and that ${\mathit{p}}_{\mathit{i}}⊒{\mathit{q}}_{\mathit{i}}$ and ${\mathit{q}}_{\mathit{i}}\mathrm{(}\mathit{b}\mathrm{,}{\mathit{d}}_{\mathit{i}}\mathrm{)}$ entail ${\mathit{p}}_{\mathit{i}}\mathrm{(}\mathit{b}\mathrm{,}{\mathit{d}}_{\mathit{i}}\mathrm{)}$ . Then, the statement follows from Proposition 1.  □

Theorem 1 logically grounds data interlinking with in-keys and ontology alignments: if we know that the properties ${\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}$ are an in-key for a class C in $\mathcal{O}$ , and that, according to an alignment $\mathcal{A}$ , C subsumes a class D of ${\mathcal{O}}^{\prime }$ and ${\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}$ pairwise subsume properties ${\mathit{q}}_1\mathrm{,}\dots \mathrm{,}{\mathit{q}}_{\mathit{k}}$ of ${\mathcal{O}}^{\prime }$ , 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 $\mathit{i}\in \{1\mathrm{,}\dots \mathrm{,}\mathit{k}\}$ , a has for ${\mathit{p}}_{\mathit{i}}$ a value ${\mathit{c}}_{\mathit{i}}$ which is equal to a value ${\mathit{d}}_{\mathit{i}}$ that b has for ${\mathit{q}}_{\mathit{i}}$ .

Theorem 2 provides the logical basis of data interlinking with eq-keys and alignments. Note that unlike Theorem 1, ${\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}$ are required to be pairwise equivalent to ${\mathit{q}}_1\mathrm{,}\dots \mathrm{,}{\mathit{q}}_{\mathit{k}}$ . 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 ${\mathit{p}}_{\mathit{i}}$ and ${\mathit{q}}_{\mathit{i}}$ , respectively, and that these values are the same. This local completeness is expressed as axioms in the ontology schemas $\mathcal{S}$ and ${\mathcal{S}}^{\prime }$ .

Theorem 2.

Let $\mathcal{O}=⟨\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}⟩$ and ${\mathcal{O}}^{\prime }=⟨{\mathcal{S}}^{\prime }\mathrm{,}{\mathcal{D}}^{\prime }\mathrm{,}{\mathcal{K}}^{\prime }⟩$ be two ontologies and $\mathcal{A}=⟨\mathcal{C}\mathrm{,}\mathcal{L}⟩$ an alignment between $\mathcal{O}$ and ${\mathcal{O}}^{\prime }$ such that

$\mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{eq}}\mathit{C}\mathrm{)}\in \mathcal{K}$ , and

$\{\mathit{C}⊒\mathit{D}\}\cup {\{{\mathit{p}}_{\mathit{i}}\equiv {\mathit{q}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}\subseteq \mathcal{C}$ .

Then, for any pair of individual names a and b of $\mathcal{O}$ and ${\mathcal{O}}^{\prime }$ , respectively, if

• $\{\mathit{C}\mathrm{(}\mathit{a}\mathrm{)}\}\cup {\bigcup }_{\mathit{i}=1}^{\mathit{k}}{\{{\mathit{p}}_{\mathit{i}}\mathrm{(}\mathit{a}\mathrm{,}{\mathit{c}}_{\mathit{i}}^{\mathit{j}}\mathrm{)}\}}_{\mathit{j}=1}^{{\mathit{r}}_{\mathit{i}}}\subseteq \mathcal{D}$ ,

• ${\{\{\mathit{a}\}⊑\forall {\mathit{p}}_{\mathit{i}}.\{{\mathit{c}}_{\mathit{i}}^1\mathrm{,}\dots \mathrm{,}{\mathit{c}}_{\mathit{i}}^{{\mathit{r}}_{\mathit{i}}}\}\}}_{\mathit{i}=1}^{\mathit{k}}\subseteq \mathcal{S}$ ,

• $\{\mathit{D}\mathrm{(}\mathit{b}\mathrm{)}\}\cup {\bigcup }_{\mathit{i}=1}^{\mathit{k}}{\{{\mathit{q}}_{\mathit{i}}\mathrm{(}\mathit{b}\mathrm{,}{\mathit{d}}_{\mathit{i}}^{\mathit{j}}\mathrm{)}\}}_{\mathit{j}=1}^{{\mathit{r}}_{\mathit{i}}}\subseteq {\mathcal{D}}^{\prime }$ ,

• ${\{\{\mathit{b}\}⊑\forall {\mathit{q}}_{\mathit{i}}.\{{\mathit{d}}_{\mathit{i}}^1\mathrm{,}\dots \mathrm{,}{\mathit{d}}_{\mathit{i}}^{{\mathit{r}}_{\mathit{i}}}\}\}}_{\mathit{i}=1}^{\mathit{k}}\subseteq {\mathcal{S}}^{\prime }$ , and

• ${\bigcup }_{\mathit{i}=1}^{\mathit{k}}{\{{\mathit{c}}_{\mathit{i}}^{\mathit{j}}\approx {\mathit{d}}_{\mathit{i}}^{\mathit{j}}\}}_{\mathit{j}=1}^{{\mathit{r}}_{\mathit{i}}}\subseteq \mathcal{L}$ ,

then $\mathcal{O}$ , ${\mathcal{O}}^{\prime }$ , $\mathcal{A}\vDash \mathit{a}\approx \mathit{b}$ .

Proof.

Notice that $\mathit{C}⊒\mathit{D}$ and $\mathit{D}\mathrm{(}\mathit{b}\mathrm{)}$ entail $\mathit{C}\mathrm{(}\mathit{b}\mathrm{)}$ , and that ${\mathit{p}}_{\mathit{i}}\equiv {\mathit{q}}_{\mathit{i}}$ entails ${\mathit{p}}_{\mathit{i}}⊒{\mathit{q}}_{\mathit{i}}$ which, together with ${\mathit{q}}_{\mathit{i}}\mathrm{(}\mathit{b}\mathrm{,}{\mathit{d}}_{\mathit{i}}^{\mathit{j}}\mathrm{)}$ , entails ${\mathit{p}}_{\mathit{i}}\mathrm{(}\mathit{b}\mathrm{,}{\mathit{d}}_{\mathit{i}}^{\mathit{j}}\mathrm{)}$ . Also, ${\mathit{p}}_{\mathit{i}}\equiv {\mathit{q}}_{\mathit{i}}$ entails ${\mathit{p}}_{\mathit{i}}⊑{\mathit{q}}_{\mathit{i}}$ which, along with $\{\mathit{b}\}⊑\forall {\mathit{q}}_{\mathit{i}}.\{{\mathit{d}}_{\mathit{i}}^1\mathrm{,}\dots \mathrm{,}{\mathit{d}}_{\mathit{i}}^{{\mathit{r}}_{\mathit{i}}}\}$ , entails $\{\mathit{b}\}⊑\forall {\mathit{p}}_{\mathit{i}}.\{{\mathit{d}}_{\mathit{i}}^1\mathrm{,}\dots \mathrm{,}{\mathit{d}}_{\mathit{i}}^{{\mathit{r}}_{\mathit{i}}}\}$ . Then, the statement follows from Proposition 2.  □

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 $\mathcal{L}$ ). Also, the case when instances are related to the same individual name – e.g. $\mathit{p}\mathrm{(}\mathit{a}\mathrm{,}\mathit{c}\mathrm{)}$ , $\mathit{q}\mathrm{(}\mathit{b}\mathrm{,}\mathit{c}\mathrm{)}$  – is covered by the theorem too, as it is enough to add links of type $\mathit{c}\approx \mathit{c}$ to $\mathcal{L}$ .

Another remark on Theorems 1 and 2 is that only one key of $\mathcal{O}$ and no key of ${\mathcal{O}}^{\prime }$ is needed to infer links. Actually, under the assumptions of the theorems, by Proposition 5, ${\{\mathit{q}\}}_{\mathit{i}=1}^{\mathit{k}}$ 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. $\mathcal{O}\mathrm{,}{\mathcal{O}}^{\prime }\mathrm{,}\mathcal{A}\vDash \mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{in}}\mathit{C}\mathrm{)}$ instead of $\mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{in}}\mathit{C}\mathrm{)}\in \mathcal{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.

Definition 6 (Link set generated by a key).

Let $\mathcal{O}$ and ${\mathcal{O}}^{\prime }$ be two ontologies. Let $\mathcal{A}$ be an alignment between $\mathcal{O}$ and ${\mathcal{O}}^{\prime }$ . Let κ be a key. The set of links between $\mathcal{O}$ and ${\mathcal{O}}^{\prime }$ generated by κ under $\mathcal{A}$ is defined as $$\begin{array}{ll}\hfill {\mathcal{L}}_{\mathit{\kappa }}^{\mathcal{O}\mathrm{,}{\mathcal{O}}^{\prime }\mathrm{,}\mathcal{A}}=& \{\mathit{a}\approx \mathit{b}:\mathit{a}\mathit{\text{is an individual in }}\mathcal{O}\\ \hfill & \wedge \mathit{b}\mathit{\text{is an individual in }}{\mathcal{O}}^{\prime }\\ \hfill & \wedge \mathcal{O}\mathrm{,}{\mathcal{O}}^{\prime }\mathrm{,}\mathcal{A}\mathrm{,}\mathit{\kappa }\vDash \mathit{a}\approx \mathit{b}\\ \hfill & \wedge \mathcal{O}\mathrm{,}{\mathcal{O}}^{\prime }\mathrm{,}\mathcal{A}⊭\mathit{a}\approx \mathit{b}\}\end{array}$$

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 (Weak in-link key).

A weak in-link key assertion, or simply a weak in-link key, has the form $$\begin{array}{c}\mathrm{\left(}\right\{⟨{\mathit{p}}_1\mathrm{,}{\mathit{q}}_1⟩\mathrm{,}\dots \mathrm{,}⟨{\mathit{p}}_{\mathit{k}}\mathrm{,}{\mathit{q}}_{\mathit{k}}⟩\}{\mathrm{linkkey}}_{\mathrm{in}}^{\mathrm{w}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}\end{array}$$ where ${\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}$ and ${\mathit{q}}_1\mathrm{,}\dots \mathrm{,}{\mathit{q}}_{\mathit{k}}$ are properties and C and D are classes.

An interpretation $\mathcal{I}$ satisfies $\mathrm{(}\{⟨{\mathit{p}}_1\mathrm{,}{\mathit{q}}_1⟩\mathrm{,}\dots \mathrm{,}⟨{\mathit{p}}_{\mathit{k}}\mathrm{,}{\mathit{q}}_{\mathit{k}}⟩\}{\mathrm{linkkey}}_{\mathrm{in}}^{\mathrm{w}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}$ if, for any $\mathit{\delta }\in {\mathit{C}}^{\mathcal{I}}$ and $\mathit{\eta }\in {\mathit{D}}^{\mathcal{I}}$ , $$\begin{array}{ll}\hfill & {\mathit{p}}_1^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}\cap {\mathit{q}}_1^{\mathcal{I}}\mathrm{(}\mathit{\eta }\mathrm{)}\ne \varnothing \mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}\cap {\mathit{q}}_{\mathit{k}}^{\mathcal{I}}\mathrm{(}\mathit{\eta }\mathrm{)}\ne \varnothing \\ \hfill & \text{implies}\mathit{\delta }=\mathit{\eta }.\end{array}$$

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 ${\{{\mathit{p}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}$ and ${\{{\mathit{q}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}$ 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 (Weak eq-link key).

A weak eq-link key assertion, or simply a weak eq-link key, has the form $$\begin{array}{c}\mathrm{\left(}\right\{⟨{\mathit{p}}_1\mathrm{,}{\mathit{q}}_1⟩\mathrm{,}\dots \mathrm{,}⟨{\mathit{p}}_{\mathit{k}}\mathrm{,}{\mathit{q}}_{\mathit{k}}⟩\}{\mathrm{linkkey}}_{\mathrm{eq}}^{\mathrm{w}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}\end{array}$$ where ${\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}$ and ${\mathit{q}}_1\mathrm{,}\dots \mathrm{,}{\mathit{q}}_{\mathit{k}}$ are properties and C and D are classes.

An interpretation $\mathcal{I}$ satisfies $\mathrm{(}\{⟨{\mathit{p}}_1\mathrm{,}{\mathit{q}}_1⟩\mathrm{,}\dots \mathrm{,}⟨{\mathit{p}}_{\mathit{k}}\mathrm{,}{\mathit{q}}_{\mathit{k}}⟩\}{\mathrm{linkkey}}_{\mathrm{in}}^{\mathrm{w}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}$ if, for any $\mathit{\delta }\in {\mathit{C}}^{\mathcal{I}}$ and $\mathit{\eta }\in {\mathit{D}}^{\mathcal{I}}$ , $$\begin{array}{ll}\hfill & {\mathit{p}}_1^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}={\mathit{q}}_1^{\mathcal{I}}\mathrm{(}\mathit{\eta }\mathrm{)}\ne \varnothing \mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}={\mathit{q}}_{\mathit{k}}^{\mathcal{I}}\mathrm{(}\mathit{\eta }\mathrm{)}\ne \varnothing \\ \hfill & \text{implies}\mathit{\delta }=\mathit{\eta }.\end{array}$$

It is worth noting that every key can be expressed as a link key. Indeed, $\mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}{\mathrm{key}}_{\mathit{x}}\mathit{C}\mathrm{)}$ is equivalent to $\mathrm{(}\{⟨{\mathit{p}}_1\mathrm{,}{\mathit{p}}_1⟩\mathrm{,}\dots \mathrm{,}⟨{\mathit{p}}_{\mathit{k}}\mathrm{,}{\mathit{p}}_{\mathit{k}}⟩\}{\mathrm{linkkey}}_{\mathit{x}}^{\mathrm{w}}⟨\mathit{C}\mathrm{,}\mathit{C}⟩\mathrm{)}$ , with $\mathit{x}\in \{\mathrm{in}\mathrm{,}\mathrm{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 (Strong in-link key).

A strong in-link key assertion, or simply a strong in-link key, has the form $$\begin{array}{c}\mathrm{\left(}\right\{⟨{\mathit{p}}_1\mathrm{,}{\mathit{q}}_1⟩\mathrm{,}\dots \mathrm{,}⟨{\mathit{p}}_{\mathit{k}}\mathrm{,}{\mathit{q}}_{\mathit{k}}⟩\}{\mathrm{linkkey}}_{\mathrm{in}}^{\mathrm{s}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}\end{array}$$ where ${\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}$ and ${\mathit{q}}_1\mathrm{,}\dots \mathrm{,}{\mathit{q}}_{\mathit{k}}$ are properties and C and D are classes.

An interpretation $\mathcal{I}$ satisfies $\mathrm{(}\{⟨{\mathit{p}}_1\mathrm{,}{\mathit{q}}_1⟩\mathrm{,}\dots \mathrm{,}⟨{\mathit{p}}_{\mathit{k}}\mathrm{,}{\mathit{q}}_{\mathit{k}}⟩\}{\mathrm{linkkey}}_{\mathrm{in}}^{\mathrm{s}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}$ if

$\mathcal{I}\vDash \mathrm{(}\{⟨{\mathit{p}}_1\mathrm{,}{\mathit{q}}_1⟩\mathrm{,}\dots \mathrm{,}⟨{\mathit{p}}_{\mathit{k}}\mathrm{,}{\mathit{q}}_{\mathit{k}}⟩\}{\mathrm{linkkey}}_{\mathrm{in}}^{\mathrm{w}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}$

$\mathcal{I}\vDash \mathrm{(}\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{in}}\mathit{C}\mathrm{)}$

$\mathcal{I}\vDash \mathrm{(}\{{\mathit{q}}_1\mathrm{,}\dots \mathrm{,}{\mathit{q}}_{\mathit{k}}\}{\mathrm{key}}_{\mathrm{in}}\mathit{D}\mathrm{)}$

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 (Plain in-link key).

A plain in-link key assertion, or simply a plain in-link key, has the form $$\begin{array}{c}\mathrm{\left(}\right\{⟨{\mathit{p}}_1\mathrm{,}{\mathit{q}}_1⟩\mathrm{,}\dots \mathrm{,}⟨{\mathit{p}}_{\mathit{k}}\mathrm{,}{\mathit{q}}_{\mathit{k}}⟩\}{\mathrm{linkkey}}_{\mathrm{in}}^{\mathrm{p}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}\end{array}$$ where ${\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}$ and ${\mathit{q}}_1\mathrm{,}\dots \mathrm{,}{\mathit{q}}_{\mathit{k}}$ are properties and C and D are classes.

An interpretation $\mathcal{I}$ satisfies $\mathrm{(}\{⟨{\mathit{p}}_1\mathrm{,}{\mathit{q}}_1⟩\mathrm{,}\dots \mathrm{,}⟨{\mathit{p}}_{\mathit{k}}\mathrm{,}{\mathit{q}}_{\mathit{k}}⟩\}{\mathrm{linkkey}}_{\mathrm{in}}^{\mathrm{p}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}$ if, for any $\mathit{\delta }\in {\mathit{C}}^{\mathcal{I}}$ and $\mathit{\eta }\in {\mathit{D}}^{\mathcal{I}}$ , $$\begin{array}{c}{\mathit{p}}_1^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}\cap {\mathit{q}}_1^{\mathcal{I}}\mathrm{(}\mathit{\eta }\mathrm{)}\ne \varnothing \mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}\cap {\mathit{q}}_{\mathit{k}}^{\mathcal{I}}\mathrm{(}\mathit{\eta }\mathrm{)}\ne \varnothing \end{array}$$ implies:

$\mathit{\delta }=\mathit{\eta }$ ,

for any ${\mathit{\delta }}^{\prime }\in {\mathit{C}}^{\mathit{I}}$ , ${\mathit{p}}_1^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}\cap {\mathit{p}}_1^{\mathcal{I}}\mathrm{(}{\mathit{\delta }}^{\prime }\mathrm{)}\ne \varnothing$ , $\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}\cap {\mathit{p}}_{\mathit{k}}^{\mathcal{I}}\mathrm{(}{\mathit{\delta }}^{\prime }\mathrm{)}\ne \varnothing$ implies $\mathit{\delta }={\mathit{\delta }}^{\prime }$ ,

for any ${\mathit{\eta }}^{\prime }\in {\mathit{D}}^{\mathit{I}}$ ,

${\mathit{q}}_1^{\mathcal{I}}\mathrm{(}\mathit{\eta }\mathrm{)}\cap {\mathit{q}}_1^{\mathcal{I}}\mathrm{(}{\mathit{\eta }}^{\prime }\mathrm{)}\ne \varnothing$ , $\dots \mathrm{,}{\mathit{q}}_{\mathit{k}}^{\mathcal{I}}\mathrm{(}\mathit{\eta }\mathrm{)}\cap {\mathit{q}}_{\mathit{k}}^{\mathcal{I}}\mathrm{(}{\mathit{\eta }}^{\prime }\mathrm{)}\ne \varnothing$ implies $\mathit{\eta }={\mathit{\eta }}^{\prime }$ .

Figure 1 shows the differences between weak, plain and strong link keys on two datasets $\mathcal{D}$ and ${\mathcal{D}}^{\prime }$ : $$\begin{array}{l}\begin{array}{cc}\hfill \mathcal{D}=& \{\mathit{p}\mathrm{(}{\mathit{a}}_1\mathrm{,}{\mathit{c}}_1\mathrm{)}\mathrm{,}\mathit{p}\mathrm{(}{\mathit{a}}_1\mathrm{,}{\mathit{c}}_2\mathrm{)}\mathrm{,}\mathit{C}\mathrm{(}{\mathit{a}}_1\mathrm{)}\mathrm{,}\mathit{p}\mathrm{(}{\mathit{a}}_2\mathrm{,}{\mathit{c}}_2\mathrm{)}\mathrm{,}\mathit{C}\mathrm{(}{\mathit{a}}_2\mathrm{)}\mathrm{,}\hfill \\ \hfill & \mathit{C}\mathrm{(}{\mathit{a}}_3\mathrm{)}\mathrm{,}\mathit{p}\mathrm{(}{\mathit{a}}_3\mathrm{,}{\mathit{c}}_3\mathrm{)}\mathrm{,}\mathit{C}\mathrm{(}{\mathit{a}}_4\mathrm{)}\mathrm{,}\mathit{p}\mathrm{(}{\mathit{a}}_4\mathrm{,}{\mathit{c}}_3\mathrm{)}\}\hfill \end{array}\\ \begin{array}{cc}\hfill {\mathcal{D}}^{\prime }=& \{\mathit{q}\mathrm{(}{\mathit{b}}_1\mathrm{,}{\mathit{d}}_1\mathrm{)}\mathrm{,}\mathit{q}\mathrm{(}{\mathit{b}}_1\mathrm{,}{\mathit{d}}_2\mathrm{)}\mathrm{,}\mathit{D}\mathrm{(}{\mathit{b}}_1\mathrm{)}\mathrm{,}\mathit{q}\mathrm{(}{\mathit{b}}_2\mathrm{,}{\mathit{d}}_2\mathrm{)}\mathrm{,}\mathit{D}\mathrm{(}{\mathit{b}}_2\mathrm{)}\mathrm{,}\hfill \\ \hfill & \mathit{D}\mathrm{(}{\mathit{b}}_3\mathrm{)}\mathrm{,}\mathit{q}\mathrm{(}{\mathit{b}}_3\mathrm{,}{\mathit{d}}_3\mathrm{)}\mathrm{,}\mathit{D}\mathrm{(}{\mathit{b}}_4\mathrm{)}\mathrm{,}\mathit{q}\mathrm{(}{\mathit{b}}_4\mathrm{,}{\mathit{d}}_3\mathrm{)}\}\hfill \end{array}\end{array}$$ with the initial set of links $\mathcal{L}=\{{\mathit{c}}_1\approx {\mathit{d}}_1\}$ . Consider the in-link key $\mathrm{(}\{⟨\mathit{p}\mathrm{,}\mathit{q}⟩\}{\mathrm{linkkey}}_{\mathrm{in}}^{\mathit{y}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}$ . Depending on the value of y, it will generate:

weak:

${\mathit{a}}_1\approx {\mathit{b}}_1$ (double-line arrow),

plain:

plus ${\mathit{a}}_1\approx {\mathit{a}}_2$ and ${\mathit{b}}_1\approx {\mathit{b}}_2$ (dashed arrows),

strong:

plus ${\mathit{a}}_3\approx {\mathit{a}}_4$ and ${\mathit{b}}_3\approx {\mathit{b}}_4$ (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: $$\begin{array}{c}\mathrm{(}{\{⟨{\mathit{p}}_{\mathit{i}}\mathrm{,}{\mathit{q}}_{\mathit{i}}⟩\}}_{\mathit{i}=1}^{\mathit{k}}{\{⟨{\mathit{r}}_{\mathit{j}}\mathrm{,}{\mathit{s}}_{\mathit{j}}⟩\}}_{\mathit{j}=1}^{\mathit{l}}{\mathrm{linkkey}}^{\mathit{y}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}\end{array}$$ with $\mathit{y}\in \{\mathrm{w}\mathrm{,}\mathrm{p}\mathrm{,}\mathrm{s}\}$ .

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

Below we give examples of link keys in real datasets.

Example 2 (Insee-IGN).

The Insee dataset includes links to the IGN dataset (French National Geographic Institute).5

⁵

http://data.ign.fr

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.6

⁶

ign is bound to the namespace http://data.ign.fr/def/geofla#.

The considered fragment of the IGN ontology is depicted in Fig. 2.

We have checked the different link key conditions for the property pair $⟨\mathsf{ins}:\mathsf{codeINSEE}\mathrm{,}\mathsf{ign}:\mathsf{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 $⟨\mathsf{ins}:\mathsf{Com}\mathrm{,}\mathsf{ign}:\mathsf{Com}⟩$ , $⟨\mathsf{ins}:\mathsf{Arr}\mathrm{,}\mathsf{ign}:\mathsf{Arr}⟩$ , $⟨\mathsf{ins}:\mathsf{Dép}\mathrm{,}\mathsf{ign}:\mathsf{Dép}⟩$ and $⟨\mathsf{ins}:\mathsf{Rég}\mathrm{,}\mathsf{ign}:\mathsf{Rég}⟩$ . Formally: $$\begin{array}{l}\begin{array}{cc}\hfill {\mathcal{I}}^{\ast }\vDash & \mathrm{\left(}\right\{⟨\mathsf{ins}:\mathsf{codeINSEE}\mathrm{,}\mathsf{ign}:\mathsf{numInsee}⟩\}{\mathrm{linkkey}}_{\mathrm{in}}^{\mathrm{s}}\hfill \\ \hfill & ⟨\mathsf{ins}:\mathsf{Com}\mathrm{,}\mathsf{ign}:\mathsf{Com}⟩\mathrm{)}\hfill \end{array}\\ \begin{array}{cc}\hfill {\mathcal{I}}^{\ast }\vDash & \mathrm{\left(}\right\{⟨\mathsf{ins}:\mathsf{codeINSEE}\mathrm{,}\mathsf{ign}:\mathsf{numInsee}⟩\}{\mathrm{linkkey}}_{\mathrm{in}}^{\mathrm{s}}\hfill \\ \hfill & ⟨\mathsf{ins}:\mathsf{Arr}\mathrm{,}\mathsf{ign}:\mathsf{Arr}⟩\mathrm{)}\hfill \end{array}\\ \begin{array}{cc}\hfill {\mathcal{I}}^{\ast }\vDash & \mathrm{\left(}\right\{⟨\mathsf{ins}:\mathsf{codeINSEE}\mathrm{,}\mathsf{ign}:\mathsf{numInsee}⟩\}{\mathrm{linkkey}}_{\mathrm{in}}^{\mathrm{s}}\hfill \\ \hfill & ⟨\mathsf{ins}:\mathsf{Dép}\mathrm{,}\mathsf{ign}:\mathsf{Dép}⟩\mathrm{)}\hfill \end{array}\\ \begin{array}{cc}\hfill {\mathcal{I}}^{\ast }\vDash & \mathrm{\left(}\right\{⟨\mathsf{ins}:\mathsf{codeINSEE}\mathrm{,}\mathsf{ign}:\mathsf{numInsee}⟩\}{\mathrm{linkkey}}_{\mathrm{in}}^{\mathrm{s}}\hfill \\ \hfill & ⟨\mathsf{ins}:\mathsf{Rég}\mathrm{,}\mathsf{ign}:\mathsf{Rég}⟩\mathrm{)}\hfill \end{array}\end{array}$$ where ${\mathcal{I}}^{\ast }$ 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 $⟨\mathsf{ins}:\mathsf{Com}\mathrm{,}\mathsf{ign}:\mathsf{Com}⟩$ , $⟨\mathsf{ins}:\mathsf{Arr}\mathrm{,}\mathsf{ign}:\mathsf{Arr}⟩$ , $⟨\mathsf{ins}:\mathsf{Dép}\mathrm{,}\mathsf{ign}:\mathsf{Dép}⟩$ and $⟨\mathsf{ins}:\mathsf{Rég}\mathrm{,}\mathsf{ign}:\mathsf{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 $⟨\mathsf{ins}:\mathsf{nom}\mathrm{,}\mathsf{rdfs}:\mathsf{label}⟩$ is a strong in-link key for $⟨\mathsf{ins}:\mathsf{Dép}\mathrm{,}\mathsf{ign}:\mathsf{Dép}⟩$ and $⟨\mathsf{ins}:\mathsf{Rég}\mathrm{,}\mathsf{ign}:\mathsf{Rég}⟩$ . The property pairs $⟨\mathsf{ins}:\mathsf{subdivisionDe}\mathrm{,}\mathsf{ign}:\mathsf{arr}⟩$ and $⟨\mathsf{ins}:\mathsf{subdivisionDe}\mathrm{,}\mathsf{ign}:\mathsf{dpt}⟩$ with $⟨\mathsf{ins}:\mathsf{nom}\mathrm{,}\mathsf{rdfs}:\mathsf{label}⟩$ constitute weak (and plain) in-link keys for the class pairs $⟨\mathsf{ins}:\mathsf{Com}\mathrm{,}\mathsf{ign}:\mathsf{Com}⟩$ and $⟨\mathsf{ins}:\mathsf{Arr}\mathrm{,}\mathsf{ign}:\mathsf{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: $$\begin{array}{l}\begin{array}{cc}\hfill {\mathcal{I}}^{\ast }\vDash & \mathrm{\left(}\right\{⟨\mathsf{ins}:\mathsf{nom}\mathrm{,}\mathsf{rdfs}:\mathsf{label}⟩\mathrm{,}⟨\mathsf{ins}:\mathsf{subdivisionDe}\mathrm{,}\hfill \\ \hfill & \mathsf{ign}:\mathsf{arr}⟩\}{\mathrm{linkkey}}_{\mathrm{in}}^{\mathrm{w}}⟨\mathsf{ins}:\mathsf{Com}\mathrm{,}\mathsf{ign}:\mathsf{Com}⟩\mathrm{)}\hfill \end{array}\\ \begin{array}{cc}\hfill {\mathcal{I}}^{\ast }\vDash & \mathrm{\left(}\right\{⟨\mathsf{ins}:\mathsf{nom}\mathrm{,}\mathsf{rdfs}:\mathsf{label}⟩\mathrm{,}⟨\mathsf{ins}:\mathsf{subdivisionDe}\mathrm{,}\hfill \\ \hfill & \mathsf{ign}:\mathsf{dpt}⟩\}{\mathrm{linkkey}}_{\mathrm{in}}^{\mathrm{w}}⟨\mathsf{ins}:\mathsf{Arr}\mathrm{,}\mathsf{ign}:\mathsf{Arr}⟩\mathrm{)}\hfill \end{array}\\ \begin{array}{cc}\hfill {\mathcal{I}}^{\ast }\vDash & \mathrm{\left(}\right\{⟨\mathsf{ins}:\mathsf{nom}\mathrm{,}\mathsf{rdfs}:\mathsf{label}⟩\}{\mathrm{linkkey}}_{\mathrm{in}}^{\mathrm{s}}\hfill \\ \hfill & ⟨\mathsf{ins}:\mathsf{Dép}\mathrm{,}\mathsf{ign}:\mathsf{Dép}⟩\mathrm{)}\hfill \end{array}\\ \begin{array}{cc}\hfill {\mathcal{I}}^{\ast }\vDash & \mathrm{\left(}\right\{⟨\mathsf{ins}:\mathsf{nom}\mathrm{,}\mathsf{rdfs}:\mathsf{label}⟩\}{\mathrm{linkkey}}_{\mathrm{in}}^{\mathrm{s}}\hfill \\ \hfill & ⟨\mathsf{ins}:\mathsf{Rég}\mathrm{,}\mathsf{ign}:\mathsf{Rég}⟩\mathrm{)}\hfill \end{array}\end{array}$$ where ${\mathcal{I}}^{\ast }$ 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].

6.2. Relations between different link keys

Below, we provide theoretical results stating the relations between the different kinds of link keys. Propositions 6 and 7 are the counterparts of Propositions 3 and 4 for link keys and can be proven similarly.

Proposition 6.

The following holds: $$\begin{array}{ll}\hfill & \mathrm{(}{\{⟨{\mathit{p}}_{\mathit{i}}\mathrm{,}{\mathit{q}}_{\mathit{i}}⟩\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{linkkey}}_{\mathrm{in}}^{\mathit{y}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}\\ \hfill & \vDash \mathrm{(}{\{⟨{\mathit{p}}_{\mathit{i}}\mathrm{,}{\mathit{q}}_{\mathit{i}}⟩\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{linkkey}}_{\mathrm{eq}}^{\mathit{y}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}\end{array}$$ with $\mathit{y}\in \{\mathrm{w}\mathrm{,}\mathrm{p}\mathrm{,}\mathrm{s}\}$ .

Proposition 7.

If ${\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{k}}$ and ${\mathit{q}}_1\mathrm{,}\dots \mathrm{,}{\mathit{q}}_{\mathit{k}}$ are functional then $$\begin{array}{ll}\hfill & \mathrm{(}{\{⟨{\mathit{p}}_{\mathit{i}}\mathrm{,}{\mathit{q}}_{\mathit{i}}⟩\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{linkkey}}_{\mathrm{eq}}^{\mathit{y}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}\\ \hfill & \vDash \mathrm{(}{\{⟨{\mathit{p}}_{\mathit{i}}\mathrm{,}{\mathit{q}}_{\mathit{i}}⟩\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{linkkey}}_{\mathrm{in}}^{\mathit{y}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}\end{array}$$ with $\mathit{y}\in \{\mathrm{w}\mathrm{,}\mathrm{p}\mathrm{,}\mathrm{s}\}$ .

Proposition 8 shows the relations between weak link keys, plain link keys and strong link keys: a strong link key is always a plain link key, which is always a weak link key. Interestingly, there is no distinction between weak eq-link keys and plain eq-link keys. This is due to the transitivity of equality.

Proposition 8.

The following holds: $$\begin{array}{l}\begin{array}{cc}\hfill & \mathrm{(}{\{⟨{\mathit{p}}_{\mathit{i}}\mathrm{,}{\mathit{q}}_{\mathit{i}}⟩\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{linkkey}}_{\mathit{x}}^{\mathrm{s}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}\hfill \\ \hfill & \vDash \mathrm{(}{\{⟨{\mathit{p}}_{\mathit{i}}\mathrm{,}{\mathit{q}}_{\mathit{i}}⟩\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{linkkey}}_{\mathit{x}}^{\mathrm{p}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}\hfill \end{array}\\ \begin{array}{cc}\hfill & \mathrm{(}{\{⟨{\mathit{p}}_{\mathit{i}}\mathrm{,}{\mathit{q}}_{\mathit{i}}⟩\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{linkkey}}_{\mathit{x}}^{\mathrm{p}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}\hfill \\ \hfill & \vDash \mathrm{(}{\{⟨{\mathit{p}}_{\mathit{i}}\mathrm{,}{\mathit{q}}_{\mathit{i}}⟩\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{linkkey}}_{\mathit{x}}^{\mathrm{w}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}\hfill \end{array}\\ \begin{array}{cc}\hfill & \mathrm{(}{\{⟨{\mathit{p}}_{\mathit{i}}\mathrm{,}{\mathit{q}}_{\mathit{i}}⟩\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{linkkey}}_{\mathrm{eq}}^{\mathrm{w}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}\hfill \\ \hfill & \vDash \mathrm{(}{\{⟨{\mathit{p}}_{\mathit{i}}\mathrm{,}{\mathit{q}}_{\mathit{i}}⟩\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{linkkey}}_{\mathrm{eq}}^{\mathrm{p}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}\hfill \end{array}\end{array}$$ with $\mathit{x}\in \{\mathrm{in}\mathrm{,}\mathrm{eq}\}$ .

Proof.

The first two propositions follow directly from the definitions of link keys. We prove the validity of the third one. Let $\mathcal{I}$ be a DL interpretation such that $\mathcal{I}\vDash \mathrm{(}{\{⟨{\mathit{p}}_{\mathit{i}}\mathrm{,}{\mathit{q}}_{\mathit{i}}⟩\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{linkkey}}_{\mathrm{eq}}^{\mathrm{w}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}$ , and let us prove that $\mathcal{I}\vDash \mathrm{(}{\{⟨{\mathit{p}}_{\mathit{i}}\mathrm{,}{\mathit{q}}_{\mathit{i}}⟩\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{linkkey}}_{\mathrm{eq}}^{\mathrm{p}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}$ . Let $\mathit{\delta }\in {\mathit{C}}^{\mathcal{I}}$ and $\mathit{\eta }\in {\mathit{D}}^{\mathcal{I}}$ be such that ${\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}={\mathit{q}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}\mathit{\eta }\mathrm{)}\ne \varnothing$ ( $\mathit{i}=1\mathrm{,}\dots \mathrm{,}\mathit{k}$ ). Since $\mathcal{I}\vDash \mathrm{(}{\{⟨{\mathit{p}}_{\mathit{i}}\mathrm{,}{\mathit{q}}_{\mathit{i}}⟩\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{linkkey}}_{\mathrm{eq}}^{\mathrm{w}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}$ , then $\mathit{\delta }=\mathit{\eta }$ . Now, let ${\mathit{\delta }}^{\prime }\in {\mathit{C}}^{\mathcal{I}}$ with ${\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}={\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{\delta }}^{\prime }\mathrm{)}\ne \varnothing$ ( $\mathit{i}=1\mathrm{,}\dots \mathrm{,}\mathit{k}$ ). From ${\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}={\mathit{q}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}\mathit{\eta }\mathrm{)}\ne \varnothing$ and ${\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}\mathit{\delta }\mathrm{)}={\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{\delta }}^{\prime }\mathrm{)}\ne \varnothing$ , we can infer that ${\mathit{p}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}{\mathit{\delta }}^{\prime }\mathrm{)}={\mathit{q}}_{\mathit{i}}^{\mathcal{I}}\mathrm{(}\mathit{\eta }\mathrm{)}\ne \varnothing$ ( $\mathit{i}=1\mathrm{,}\dots \mathrm{,}\mathit{k}$ ). This together with ${\mathit{\delta }}^{\prime }\in {\mathit{C}}^{\mathcal{I}}$ , $\mathit{\eta }\in {\mathit{D}}^{\mathcal{I}}$ and $\mathcal{I}\vDash \mathrm{(}{\{⟨{\mathit{p}}_{\mathit{i}}\mathrm{,}{\mathit{q}}_{\mathit{i}}⟩\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{linkkey}}_{\mathrm{eq}}^{\mathrm{w}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}$ implies ${\mathit{\delta }}^{\prime }=\mathit{\eta }$ , and, since $\mathit{\delta }=\mathit{\eta }$ , then $\mathit{\delta }={\mathit{\delta }}^{\prime }$ . The last condition of plain eq-link keys can be proven analogously.  □

In the following section, we establish when it is legitimate to use link keys for data interlinking.

7. Data interlinking with link keys

Theorems 3 and 4 give the logical foundations of data interlinking with weak in-link keys and eq-link keys, respectively. Their proofs follow the same ideas as the proofs of Theorems 1 and 2 and are omitted.

Theorem 3.

Let $\mathcal{O}=⟨\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}⟩$ and ${\mathcal{O}}^{\prime }=⟨{\mathcal{S}}^{\prime }\mathrm{,}{\mathcal{D}}^{\prime }\mathrm{,}{\mathcal{K}}^{\prime }⟩$ be two ontologies. Let $\mathcal{A}=⟨\mathcal{C}\mathrm{,}\mathcal{L}\mathrm{,}\mathcal{LK}⟩$ be an alignment between $\mathcal{O}$ and ${\mathcal{O}}^{\prime }$ such that

$\mathrm{(}\{⟨{\mathit{p}}_1\mathrm{,}{\mathit{q}}_1⟩\mathrm{,}\dots \mathrm{,}⟨{\mathit{p}}_{\mathit{k}}\mathrm{,}{\mathit{q}}_{\mathit{k}}⟩\}{\mathrm{linkkey}}_{\mathrm{in}}^{\mathrm{w}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}\in \mathcal{LK}$ .

Then, for any pair of individual names a and b of $\mathcal{O}$ and ${\mathcal{O}}^{\prime }$ , respectively, if

• $\{\mathit{C}\mathrm{(}\mathit{a}\mathrm{)}\}\cup {\{{\mathit{p}}_{\mathit{i}}\mathrm{(}\mathit{a}\mathrm{,}{\mathit{c}}_{\mathit{i}}\mathrm{)}\}}_{\mathit{i}=1}^{\mathit{k}}\subseteq \mathcal{D}$ ,

• $\{\mathit{D}\mathrm{(}\mathit{b}\mathrm{)}\}\cup {\{{\mathit{q}}_{\mathit{i}}\mathrm{(}\mathit{b}\mathrm{,}{\mathit{d}}_{\mathit{i}}\mathrm{)}\}}_{\mathit{i}=1}^{\mathit{k}}\subseteq {\mathcal{D}}^{\prime }$ , and

• ${\{{\mathit{c}}_{\mathit{i}}\approx {\mathit{d}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}\subseteq \mathcal{L}$

then $\mathcal{O}$ , ${\mathcal{O}}^{\prime }$ , $\mathcal{A}\vDash \mathit{a}\approx \mathit{b}$ .

Theorem 3 provides the logical basis of data interlinking with weak in-link keys: if we know that the property pairs $⟨{\mathit{p}}_1\mathrm{,}{\mathit{q}}_1⟩$ , …, $⟨{\mathit{p}}_{\mathit{k}}\mathrm{,}{\mathit{q}}_{\mathit{k}}⟩$ are a weak in-link key for the class pair $⟨\mathit{C}\mathrm{,}\mathit{D}⟩$ , then, for every pair of instances a of C and b of D, the link key will generate a same-as link between a and b if, for every $\mathit{i}\in \{1\mathrm{,}\dots \mathrm{,}\mathit{k}\}$ , a has for ${\mathit{p}}_{\mathit{i}}$ a value ${\mathit{c}}_{\mathit{i}}$ which is equal to a value ${\mathit{d}}_{\mathit{i}}$ that b has for ${\mathit{q}}_{\mathit{i}}$ .

The counterpart of Theorem 3 for weak eq-link keys is Theorem 4. In this case, to generate a same-as link between a and b, we need to know all the values that a and b have for ${\mathit{p}}_{\mathit{i}}$ and ${\mathit{q}}_{\mathit{i}}$ , respectively, and that these values are the same. This local completeness is expressed as axioms in the ontology schemas $\mathcal{S}$ and ${\mathcal{S}}^{\prime }$ .

Theorem 4.

Let $\mathcal{O}=⟨\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}⟩$ and ${\mathcal{O}}^{\prime }=⟨{\mathcal{S}}^{\prime }\mathrm{,}{\mathcal{D}}^{\prime }\mathrm{,}{\mathcal{K}}^{\prime }⟩$ be two ontologies. Let $\mathcal{A}=⟨\mathcal{C}\mathrm{,}\mathcal{L}\mathrm{,}\mathcal{LK}⟩$ be an alignment between $\mathcal{O}$ and ${\mathcal{O}}^{\prime }$ such that

$\mathrm{(}\{⟨{\mathit{p}}_1\mathrm{,}{\mathit{q}}_1⟩\mathrm{,}\dots \mathrm{,}⟨{\mathit{p}}_{\mathit{k}}\mathrm{,}{\mathit{q}}_{\mathit{k}}⟩\}{\mathrm{linkkey}}_{\mathrm{eq}}^{\mathrm{w}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}\in \mathcal{LK}$ .

Then, for any pair of individual names a and b of $\mathcal{O}$ and ${\mathcal{O}}^{\prime }$ , respectively, if

• $\{\mathit{C}\mathrm{(}\mathit{a}\mathrm{)}\}\cup {\bigcup }_{\mathit{i}=1}^{\mathit{k}}{\{{\mathit{p}}_{\mathit{i}}\mathrm{(}\mathit{a}\mathrm{,}{\mathit{c}}_{\mathit{i}}^{\mathit{j}}\mathrm{)}\}}_{\mathit{j}=1}^{{\mathit{r}}_{\mathit{i}}}\subseteq \mathcal{D}$ ,

• ${\{\{\mathit{a}\}⊑\forall {\mathit{p}}_{\mathit{i}}.\{{\mathit{c}}_{\mathit{i}}^1\mathrm{,}\dots \mathrm{,}{\mathit{c}}_{\mathit{i}}^{{\mathit{r}}_{\mathit{i}}}\}\}}_{\mathit{i}=1}^{\mathit{k}}\subseteq \mathcal{S}$ ,

• $\{\mathit{D}\mathrm{(}\mathit{b}\mathrm{)}\}\cup {\bigcup }_{\mathit{i}=1}^{\mathit{k}}{\{{\mathit{q}}_{\mathit{i}}\mathrm{(}\mathit{b}\mathrm{,}{\mathit{d}}_{\mathit{i}}^{\mathit{j}}\mathrm{)}\}}_{\mathit{j}=1}^{{\mathit{r}}_{\mathit{i}}}\subseteq {\mathcal{D}}^{\prime }$ ,

• ${\{\{\mathit{b}\}⊑\forall {\mathit{q}}_{\mathit{i}}.\{{\mathit{d}}_{\mathit{i}}^1\mathrm{,}\dots \mathrm{,}{\mathit{d}}_{\mathit{i}}^{{\mathit{r}}_{\mathit{i}}}\}\}}_{\mathit{i}=1}^{\mathit{k}}\subseteq {\mathcal{S}}^{\prime }$ , and

• ${\bigcup }_{\mathit{i}=1}^{\mathit{k}}{\{{\mathit{c}}_{\mathit{i}}^{\mathit{j}}\approx {\mathit{d}}_{\mathit{i}}^{\mathit{j}}\}}_{\mathit{j}=1}^{{\mathit{r}}_{\mathit{i}}}\subseteq \mathcal{L}$

then $\mathcal{O}$ , ${\mathcal{O}}^{\prime }$ , $\mathcal{A}\vDash \mathit{a}\approx \mathit{b}$ .

Theorems 3 and 4 show that, unlike keys, weak link keys do not need mappings between classes and properties to perform data interlinking. In addition, since, by Proposition 8, any plain or strong link key is a weak link key, Theorems 3 and 4 hold for strong and plain link keys too.

Below we give the definition of the link set generated by a link key. It applies to all types of link keys.

Definition 11 (Link set generated by a link key).

Let $\mathcal{O}$ and ${\mathcal{O}}^{\prime }$ be two ontologies. Let $\mathcal{A}$ be an alignment between $\mathcal{O}$ and ${\mathcal{O}}^{\prime }$ . Let λ be a link key. The set of links between $\mathcal{O}$ and ${\mathcal{O}}^{\prime }$ generated by λ under $\mathcal{A}$ is $$\begin{array}{ll}\hfill {\mathcal{L}}_{\mathit{\lambda }}^{\mathcal{O}\mathrm{,}{\mathcal{O}}^{\prime }\mathrm{,}\mathcal{A}}=& \{\mathit{a}\approx \mathit{b}:\mathit{a}\mathit{\text{is an individual in }}\mathcal{O}\\ \hfill & \wedge \mathit{b}\mathit{\text{is an individual in }}{\mathcal{O}}^{\prime }\\ \hfill & \wedge \mathcal{O}\mathrm{,}{\mathcal{O}}^{\prime }\mathrm{,}\mathcal{A}\mathrm{,}\mathit{\lambda }\vDash \mathit{a}\approx \mathit{b}\\ \hfill & \wedge \mathcal{O}\mathrm{,}{\mathcal{O}}^{\prime }\mathrm{,}\mathcal{A}⊭\mathit{a}\approx \mathit{b}\}\end{array}$$

Strong link keys generate more equality statements than plain link keys, which generate more than weak link keys. Logically speaking, it is justified by the fact that the more constraining a link key is, the less models it has, and, thus, the more logical consequences follow from it. Dually, when searching for link keys, it will be easier to search for weak link keys than plain link keys, which will be easier than searching for strong link keys. This is because, in each case, more constraints need to be satisfied.

Therefore, the manipulation of link keys is delicate: the stronger a link key is, the more difficult to extract it, but the more equality statements it will generate. Furthermore, weak link keys may exist when plain and strong link keys do not. In such cases, data interlinking will only be possible with weak link keys. In contrast, duplicate detection inside datasets is only possible with plain or strong link keys.

The generation of links from a link key based on Theorems 3 and 4 is reasonably easy. It may be achieved by using specific tools such as Linkex [1], by transforming link keys into SPARQL queries (available from the Alignment API [15]) or by expressing them as (boolean) linkage rules to be executed in specific platforms such as SILK [22,33] or LIMES [26].

However, these latter platforms do not seem to support the comparison of sets of property values, thus the direct translation of eq-link keys is not possible. The natural extension of this approach, taking into account full reasoning, will require developing specific provers.

Now that we have formally defined how to interlink data with keys and link keys independently of each other, we are in position to compare them.

8. Relation between keys and link keys

Keys and link keys are data interlinking devices that we have developed so far in a parallel manner. One then may expect that their application always results in the generation of the same links. We are now able to formally establish the relation between keys and link keys, and to show that, although there may be data interlinking scenarios in which they will return the same links, this will not always be the case.

This section starts by studying the relation between keys and link keys as description logic axioms (Section 8.1). Theorem 5 states the correspondence between strong link keys and keys and alignments. This correspondence no longer holds for weak link keys (Theorem 6). We also study the impact of these results on the generation of links (Section 8.2): Theorems 7 and 8 show that the links generated by a strong link key are the same as the links generated by its corresponding keys and proper alignments. There are cases, though, in which it is possible to generate links with weak link keys while it is not possible with keys and alignments.

8.1. Logical relations between keys and link keys

The theorems presented here are consequences of stronger results included in the Appendix. We have decided to not include the latter in this section because the former are more directly related to data interlinking with keys and link keys.

Theorem 5 states the correspondence between strong link keys and keys and alignments: (11) says that strong link keys entail keys; (12) and (13) express conditions under which the converse of (11) holds.

Theorem 5.

The following holds: $$\begin{array}{}\text{(11)}& \begin{array}{cc}\hfill & \mathrm{(}{\{⟨{\mathit{p}}_{\mathit{i}}\mathrm{,}{\mathit{q}}_{\mathit{i}}⟩\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{linkkey}}_{\mathit{x}}^{\mathrm{s}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}\hfill \\ \hfill & \vDash \mathrm{\left(}{\{{\mathit{p}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{key}}_{\mathit{x}}\mathit{C}\mathrm{\right)}\hfill \end{array}\text{(12)}& \begin{array}{cc}\hfill & \mathrm{\left(}{\{{\mathit{p}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{key}}_{\mathrm{in}}\mathit{C}\mathrm{\right)}\mathrm{,}\mathit{C}⊒\mathit{D}\mathrm{,}{\{{\mathit{p}}_{\mathit{i}}⊒{\mathit{q}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}\hfill \\ \hfill & \vDash \mathrm{(}{\{⟨{\mathit{p}}_{\mathit{i}}\mathrm{,}{\mathit{q}}_{\mathit{i}}⟩\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{linkkey}}_{\mathrm{in}}^{\mathrm{s}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}\hfill \end{array}\text{(13)}& \begin{array}{cc}\hfill & \mathrm{\left(}{\{{\mathit{p}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{key}}_{\mathrm{eq}}\mathit{C}\mathrm{\right)}\mathrm{,}\mathit{C}⊒\mathit{D}\mathrm{,}{\{{\mathit{p}}_{\mathit{i}}\equiv {\mathit{q}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}\hfill \\ \hfill & \vDash \mathrm{(}{\{⟨{\mathit{p}}_{\mathit{i}}\mathrm{,}{\mathit{q}}_{\mathit{i}}⟩\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{linkkey}}_{\mathrm{eq}}^{\mathrm{s}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}\hfill \end{array}\end{array}$$ with $\mathit{x}\in \{\mathrm{in}\mathrm{,}\mathrm{eq}\}$ .

Proof.

(11) is a direct consequence of the definition of strong link keys (Definition 9). (12) and (13) are consequences of Proposition 12 in the Appendix.  □

Given the symmetry of the link key definitions, (11), (12) and (13) hold for the right-hand side of the link key too (with reversed subsumption relations).

Theorem 5 states that it is possible to infer keys from strong link keys. This is not surprising because strong link keys are composed of keys by definition. We call these keys the side keys associated with a strong link key. More interestingly, Theorem 5 also states that strong link keys can be inferred from keys and proper alignments. Note that one key is enough to entail the strong link key as long as the alignment holds (these alignments are different depending on whether in-link keys or eq-link keys are considered).

The converses of (12) and (13) are only partly true: strong link keys entail keys, but strong link keys (nor plain or weak link keys) do not necessarily entail an alignment between their properties and classes. This rejects the idea that link keys embed alignments. Link keys do not assert alignments, but express conditions for identifying individuals. A link key between two classes C and D does not assert that C and D are equivalent, nor that one of the classes subsumes the other, it just specifies how to link individuals that are described as instances of C and D, but there may be individuals in both classes that do not belong to the other class. For example, there may exist a link key between the classes AdministrativeCentre and Town, although no equivalence, nor subsumption holds between them (some administrative centres are towns, others are cities; some towns are administrative centres, others not).

Is Theorem 5 still valid for weak and plain link keys? (12) and (13) do hold, but (11) does not. In other words: keys and proper alignments entail weak and plain link keys (Corollary 5.1); however, none of the side components of weak or plain link keys are necessarily keys (Theorem 6).

Fig. 3.

Two ontologies ${\mathcal{O}}_1$ and ${\mathcal{O}}_2$ such that ${\mathcal{O}}_1\cup {\mathcal{O}}_2\cup \{\mathrm{(}\{⟨\mathit{p}\mathrm{,}\mathit{q}⟩\mathrm{,}⟨{\mathit{p}}^{\prime }\mathrm{,}{\mathit{q}}^{\prime }⟩\}{\mathrm{linkkey}}_{\mathrm{in}}^{\mathrm{w}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}\}$ is consistent, whereas ${\mathcal{O}}_1\cup \{\mathrm{(}\{\mathit{p}\mathrm{,}{\mathit{p}}^{\prime }\}{\mathrm{key}}_{\mathrm{in}}\mathit{C}\mathrm{)}\}$ and ${\mathcal{O}}_2\cup \{\mathrm{(}\{\mathit{q}\mathrm{,}{\mathit{q}}^{\prime }\}{\mathrm{key}}_{\mathrm{in}}\mathit{D}\mathrm{)}\}$ are inconsistent.

Corollary 5.1.

The following holds: $$\begin{array}{}\text{(14)}& \begin{array}{cc}\hfill & \mathrm{\left(}{\{{\mathit{p}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{key}}_{\mathrm{in}}\mathit{C}\mathrm{\right)}\mathrm{,}\mathit{C}⊒\mathit{D}\mathrm{,}{\{{\mathit{p}}_{\mathit{i}}⊒{\mathit{q}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}\hfill \\ \hfill & \vDash \mathrm{(}{\{⟨{\mathit{p}}_{\mathit{i}}\mathrm{,}{\mathit{q}}_{\mathit{i}}⟩\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{linkkey}}_{\mathrm{in}}^{\mathit{y}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}\hfill \end{array}\text{(15)}& \begin{array}{cc}\hfill & \mathrm{\left(}{\{{\mathit{p}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{key}}_{\mathrm{eq}}\mathit{C}\mathrm{\right)}\mathrm{,}\mathit{C}⊒\mathit{D}\mathrm{,}{\{{\mathit{p}}_{\mathit{i}}\equiv {\mathit{q}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}\hfill \\ \hfill & \vDash \mathrm{(}{\{⟨{\mathit{p}}_{\mathit{i}}\mathrm{,}{\mathit{q}}_{\mathit{i}}⟩\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{linkkey}}_{\mathrm{eq}}^{\mathit{y}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}\hfill \end{array}\end{array}$$ with $\mathit{y}\in \{\mathrm{w}\mathrm{,}\mathrm{p}\}$ .

Proof.

This is a direct consequence of Theorem 5 since, by Proposition 8, any strong link key is also a plain and a weak link key.  □

Unlike strong link keys, none of the side components of weak or plain link keys are necessarily keys. The proof of Theorem 6 provides two ontologies that are consistent with a weak link key but are inconsistent with any of its side components.

Theorem 6.

There exist ontologies that are consistent with a weak link key but inconsistent with each of its side components.

Proof.

Consider the two ontologies ${\mathcal{O}}_1$ and ${\mathcal{O}}_2$ depicted in Fig. 3. It can be checked that $$\begin{array}{c}\mathit{\lambda }=\mathrm{\left(}\right\{⟨\mathit{p}\mathrm{,}\mathit{q}⟩\mathrm{,}⟨{\mathit{p}}^{\prime }\mathrm{,}{\mathit{q}}^{\prime }⟩\}{\mathrm{linkkey}}_{\mathrm{in}}^{\mathrm{w}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}\end{array}$$ is consistent with ${\mathcal{O}}_1\cup {\mathcal{O}}_2$ . Notice that λ together with ${\mathcal{O}}_1$ and ${\mathcal{O}}_2$ entails the link ${\mathit{a}}_1\approx {\mathit{b}}_1$ .

On the contrary, the side components of λ, i.e. $$\begin{array}{c}{\mathit{\kappa }}_1=\mathrm{\left(}\right\{\mathit{p}\mathrm{,}{\mathit{p}}^{\prime }\left\}{\mathrm{key}}_{\mathrm{in}}\mathit{C}\mathrm{\right)}{\mathit{\kappa }}_2=\mathrm{\left(}\right\{\mathit{q}\mathrm{,}{\mathit{q}}^{\prime }\left\}{\mathrm{key}}_{\mathrm{in}}\mathit{D}\mathrm{\right)}\end{array}$$ are inconsistent with ${\mathcal{O}}_1$ and ${\mathcal{O}}_2$ , respectively. Indeed, ${\mathcal{O}}_1\cup \{{\mathit{\kappa }}_1\}\vDash {\mathit{a}}_2\approx {\mathit{a}}_4$ because ${\mathit{a}}_2$ and ${\mathit{a}}_4$ share the value ${\mathit{v}}_2$ for p and the value ${\mathit{w}}_1$ for ${\mathit{p}}^{\prime }$ . However, ${\mathcal{O}}_1\cup \{{\mathit{\kappa }}_1\}\vDash {\mathit{a}}_2\not\approx {\mathit{a}}_4$ because ${\mathit{a}}_2\not\approx {\mathit{a}}_4$ belongs to ${\mathcal{O}}_1$ . This means that ${\mathcal{O}}_1\cup \{{\mathit{\kappa }}_1\}$ is inconsistent. Similarly, it can be shown that ${\mathcal{O}}_2\cup \{{\mathit{\kappa }}_2\}$ is inconsistent.  □

It is noteworthy that not a single useful key (i.e. a key that can be used to generate links) can be found in the ontologies of the proof of Theorem 6: $\mathrm{(}\{\mathit{p}\}{\mathrm{key}}_{\mathrm{in}}\mathit{C}\mathrm{)}$ and $\mathrm{(}\{{\mathit{p}}^{\prime }\}{\mathrm{key}}_{\mathrm{in}}\mathit{C}\mathrm{)}$ are both inconsistent with ${\mathcal{O}}_1$ , and $\mathrm{(}\{\mathit{q}\}{\mathrm{key}}_{\mathrm{in}}\mathit{D}\mathrm{)}$ and $\mathrm{(}\{{\mathit{q}}^{\prime }\}{\mathrm{key}}_{\mathrm{in}}\mathit{D}\mathrm{)}$ with ${\mathcal{O}}_2$ . As a consequence, in this example, data interlinking is possible with link keys (λ allows to find ${\mathit{a}}_1\approx {\mathit{b}}_1$ ) but not with keys. Moreover, data interlinking is possible with weak link keys but not with strong link keys.

Example 3 makes it clear in the context of a real data interlinking scenario that (11) in Theorem 5 does not hold for weak link keys.

Example 3 (Insee-IGN (cont.)).

The following statement of Example 2: $$\begin{array}{ll}\hfill {\mathcal{I}}^{\ast }\vDash & \mathrm{\left(}\right\{⟨\mathsf{ins}:\mathsf{nom}\mathrm{,}\mathsf{rdfs}:\mathsf{label}⟩\mathrm{,}⟨\mathsf{ins}:\mathsf{subdivisionDe}\mathrm{,}\\ \hfill & \mathsf{ign}:\mathsf{arr}⟩\}{\mathrm{linkkey}}_{\mathrm{in}}^{\mathrm{w}}⟨\mathsf{ins}:\mathsf{Com}\mathrm{,}\mathsf{ign}:\mathsf{Com}⟩\mathrm{)}\end{array}$$ expresses a weak in-link key satisfied by ${\mathcal{I}}^{\ast }$ , the canonical interpretation of the RDF graphs of Example 2 whose linked individuals are merged.

Let us consider the side components of the above weak link key: If (11) of Theorem 5 were true for weak link keys, then the following two keys would be satisfied by ${\mathcal{I}}^{\ast }$ : $$\begin{array}{ll}\hfill & \mathrm{(}\{\mathsf{ins}:\mathsf{nom}\mathrm{,}\mathsf{ins}:\mathsf{subdivisionDe}\}{\mathrm{key}}_{\mathrm{in}}\mathsf{ins}:\mathsf{Com}\mathrm{)}\\ \hfill & \mathrm{(}\{\mathsf{rdfs}:\mathsf{label}\mathrm{,}\mathsf{ign}:\mathsf{arr}\}{\mathrm{key}}_{\mathrm{in}}\mathsf{ign}:\mathsf{Com}\mathrm{)}\end{array}$$ However, as explained in Example 2, the key axiom $\mathrm{(}\{\mathsf{ins}:\mathsf{nom}\mathrm{,}\mathsf{ins}:\mathsf{subdivisionDe}\}{\mathrm{key}}_{\mathrm{in}}\mathsf{ins}:\mathsf{Com}\mathrm{)}$ is not satisfied by ${\mathcal{I}}^{\ast }$ due to the transitivity of the property ins:subdivisionDe.

One may think that data interlinking is still possible with $\mathrm{(}\{\mathsf{rdfs}:\mathsf{label}\mathrm{,}\mathsf{ign}:\mathsf{arr}\}{\mathrm{key}}_{\mathrm{in}}\mathsf{ign}:\mathsf{Com}\mathrm{)}$ , which is indeed satisfied by ${\mathcal{I}}^{\ast }$ . This would require the following property correspondences to hold $$\begin{array}{ll}\hfill \mathsf{ins}:\mathsf{nom}& ⊒\mathsf{rdfs}:\mathsf{label}\\ \hfill \mathsf{ins}:\mathsf{subdivisionDe}& ⊒\mathsf{ign}:\mathsf{arr}\end{array}$$ However, ${\mathcal{I}}^{\ast }$ does not satisfy $\mathsf{ins}:\mathsf{nom}⊒\mathsf{rdfs}:\mathsf{label}$ but the reversed subsumption $\mathsf{ins}:\mathsf{nom}⊑\mathsf{rdfs}:\mathsf{label}$ (see Fig. 2).

Even though the side components of a weak link key are not necessarily keys for the ontologies separately, every weak link key entails one key in the vocabulary of the ontologies together, as stated by Proposition 9 below. Unfortunately, this link key is of very limited use in practice because the inferred key holds for the intersection of the classes that we actually want to interlink (it is not known before linking which individuals belong to both classes).

Proposition 9.

The following holds: $$\begin{array}{ll}\hfill & \mathrm{(}{\{⟨{\mathit{p}}_{\mathit{i}}\mathrm{,}{\mathit{q}}_{\mathit{i}}⟩\}}_{\mathit{i}=1}^{\mathit{k}}\mathrm{link}{\mathrm{key}}_{\mathit{x}}^{\mathrm{w}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}\\ \hfill & \vDash \mathrm{(}{\{{\mathit{p}}_{\mathit{i}}\sqcap {\mathit{q}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{key}}_{\mathit{x}}^{\mathrm{w}}\mathit{C}\sqcap \mathit{D}\mathrm{)}\end{array}$$ with $\mathit{x}\in \{\mathrm{in}\mathrm{,}\mathrm{eq}\}$ .

Proof.

This is a consequence of Proposition 10 in the Appendix.  □

8.2. Relations between generated link sets

The difference between using link keys for data interlinking instead of keys and ontology alignments becomes evident when comparing Theorem 1 with Theorem 3 and Theorem 2 with Theorem 4. In both cases, knowledge about keys and alignments is replaced by knowledge about link keys. Theorem 7 shows that the generated link sets are exactly the same.

Theorem 7.

Let $\mathcal{O}$ and ${\mathcal{O}}^{\prime }$ be ontologies. Let $\mathcal{A}=⟨\mathcal{C}\mathrm{,}\mathcal{L}\mathrm{,}\mathcal{LK}⟩$ be an alignment between $\mathcal{O}$ and ${\mathcal{O}}^{\prime }$ with $\{\mathit{C}⊒\mathit{D}\}\mathrm{,}{\{{\mathit{p}}_{\mathit{i}}⊑{\mathit{q}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}\subseteq \mathcal{C}$ . Let $\mathit{\kappa }=\mathrm{(}{\{{\mathit{p}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{key}}_{\mathrm{in}}\mathit{C}\mathrm{)}$ and $\mathit{\lambda }=\mathrm{(}{\{⟨{\mathit{p}}_{\mathit{i}}\mathrm{,}{\mathit{q}}_{\mathit{i}}⟩\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{linkkey}}_{\mathrm{in}}^{\mathrm{s}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}$ . Then, it holds that ${\mathcal{L}}_{\mathit{\kappa }}^{\mathcal{O}\mathrm{,}{\mathcal{O}}^{\prime }\mathrm{,}\mathcal{A}}={\mathcal{L}}_{\mathit{\lambda }}^{\mathcal{O}\mathrm{,}{\mathcal{O}}^{\prime }\mathrm{,}\mathcal{A}}$ .

Proof.

The result follows from Definitions 6 and 11 and the fact that, since $\{\mathit{C}⊒\mathit{D}\}\cup {\{{\mathit{p}}_{\mathit{i}}⊑{\mathit{q}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}\subseteq \mathcal{C}$ , by clause (12) of Theorem 5, we have $\mathcal{O}$ , ${\mathcal{O}}^{\prime }$ , $\mathcal{A}$ , $\mathit{\kappa }\vDash \mathit{\lambda }$ and also $\mathcal{O}$ , ${\mathcal{O}}^{\prime }$ , $\mathcal{A}$ , $\mathit{\lambda }\vDash \mathit{\kappa }$ .  □

The same holds for eq-keys and eq-link keys.

Theorem 8.

Let $\mathcal{O}$ and ${\mathcal{O}}^{\prime }$ be ontologies. Let $\mathcal{A}=⟨\mathcal{C}\mathrm{,}\mathcal{L}\mathrm{,}\mathcal{LK}⟩$ be an alignment between $\mathcal{O}$ and ${\mathcal{O}}^{\prime }$ with $\{\mathit{C}⊒\mathit{D}\}\mathrm{,}{\{{\mathit{p}}_{\mathit{i}}\equiv {\mathit{q}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}\subseteq \mathcal{C}$ . Let $\mathit{\kappa }=\mathrm{(}{\{{\mathit{p}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{key}}_{\mathrm{eq}}\mathit{C}\mathrm{)}$ and $\mathit{\lambda }=\mathrm{(}{\{⟨{\mathit{p}}_{\mathit{i}}\mathrm{,}{\mathit{q}}_{\mathit{i}}⟩\}}_{\mathit{i}=1}^{\mathit{k}}{\mathrm{linkkey}}_{\mathrm{eq}}^{\mathrm{s}}⟨\mathit{C}\mathrm{,}\mathit{D}⟩\mathrm{)}$ . Then, it holds that ${\mathcal{L}}_{\mathit{\kappa }}^{\mathcal{O}\mathrm{,}{\mathcal{O}}^{\prime }\mathrm{,}\mathcal{A}}={\mathcal{L}}_{\mathit{\lambda }}^{\mathcal{O}\mathrm{,}{\mathcal{O}}^{\prime }\mathrm{,}\mathcal{A}}$ .

Proof.

The result follows from Definitions 6 and 11 and the fact that, since $\{\mathit{C}⊒\mathit{D}\}\cup {\{{\mathit{p}}_{\mathit{i}}\equiv {\mathit{q}}_{\mathit{i}}\}}_{\mathit{i}=1}^{\mathit{k}}\subseteq \mathcal{C}$ , by clause (13) of Theorem 5, we have $\mathcal{O}$ , ${\mathcal{O}}^{\prime }$ , $\mathcal{A}$ , $\mathit{\kappa }\vDash \mathit{\lambda }$ and also $\mathcal{O}$ , ${\mathcal{O}}^{\prime }$ , $\mathcal{A}$ , $\mathit{\lambda }\vDash \mathit{\kappa }$ .  □

The lesson from Theorems 7 and 8 is that, for interlinking two datasets, if there is a key for one dataset and a proper alignment from the key to the vocabulary of the other dataset, then using the key or the strong link key entailed by the key and the alignment is strictly equivalent.

However, as explained in the previous section, weak link keys may exist even when keys and proper alignments do not. As a conclusion, in general, link keys are more suitable than keys for data interlinking. Thus, data interlinking algorithms are justified in discovering link keys rather than keys and alignments. Below we provide a real data-interlinking scenario in which keys and alignments are not useful, but link keys are. Example 4 (Insee-GeoNames).

GeoNames is a world-wide geographical database publicly available in RDF.7

⁷

https://download.geonames.org/export/dump/allCountries.zip

Imagine that we are given the task of finding links between the URIs of Insee and GeoNames that represent French communes. Below we show that, for this particular task, keys and alignments are useless as they will generate no link, while link keys will generate almost all of them.

Insee’s ontology is very different from GeoNames’ ontology.8

⁸

http://www.geonames.org/ontology/ontology_v3.2.rdf

It is not surprising as Insee’s scope is France and GeoNames’ is world-wide. GeoNames’ ontology basically contains only one class, gn:Feature, of which all geographical features (countries, cities, mountains, lakes, etc.) are direct instances. There is no named class equivalent to ins:Com, ins:Arr, ins:Dép or ins:Rég, but the following complex alignment holds: $$\begin{array}{l}\begin{array}{cc}\hfill \mathsf{ins}:\mathsf{Com}\equiv & \mathsf{gn}:\mathsf{Feature}\hfill \\ \hfill & \sqcap \exists \mathsf{gn}:\mathsf{countryCode}.\{\mathsf{FR}\}\hfill \\ \hfill & \sqcap \exists \mathsf{gn}:\mathsf{featureCode}.\{\mathsf{A}.\mathsf{ADM}\mathsf{4}\}\hfill \end{array}\\ \begin{array}{cc}\hfill \mathsf{ins}:\mathsf{Arr}\equiv & \mathsf{gn}:\mathsf{Feature}\hfill \\ \hfill & \sqcap \exists \mathsf{gn}:\mathsf{countryCode}.\{\mathsf{FR}\}\hfill \\ \hfill & \sqcap \exists \mathsf{gn}:\mathsf{featureCode}.\{\mathsf{A}.\mathsf{ADM}\mathsf{3}\}\hfill \end{array}\\ \begin{array}{cc}\hfill \mathsf{ins}:\mathsf{Dép}\equiv & \mathsf{gn}:\mathsf{Feature}\hfill \\ \hfill & \sqcap \exists \mathsf{gn}:\mathsf{countryCode}.\{\mathsf{FR}\}\hfill \\ \hfill & \sqcap \exists \mathsf{gn}:\mathsf{featureCode}.\{\mathsf{A}.\mathsf{ADM}\mathsf{2}\}\hfill \end{array}\\ \begin{array}{cc}\hfill \mathsf{ins}:\mathsf{Rég}\equiv & \mathsf{gn}:\mathsf{Feature}\hfill \\ \hfill & \sqcap \exists \mathsf{gn}:\mathsf{countryCode}.\{\mathsf{FR}\}\hfill \\ \hfill & \sqcap \exists \mathsf{gn}:\mathsf{featureCode}.\{\mathsf{A}.\mathsf{ADM}\mathsf{1}\}\hfill \end{array}\end{array}$$

From here on, the complex classes of the right-hand sides of the above equivalences will be denoted by gn:Com, gn:Arr, gn:Dep and gn:Reg.

Fig. 4.

Fragments of the Insee and GeoNames ontologies and their alignment.

In Insee, apart from rdf:type and owl:sameAs, communes only have the following properties: ins:nom, ins:subdivisionDe, ins:codeCommune and ins:codeInsee. Neither ins:codeCommune nor ins:codeInsee has any counterpart in GeoNames’ ontology, but ins:nom and ins:subdivisionDe are aligned in the following way: $$\begin{array}{}\text{(16)}& \hfill \mathsf{ins}:\mathsf{nom}& \equiv \mathsf{gn}:\mathsf{name}\text{(17)}& \hfill \mathsf{ins}:\mathsf{subdivisionDe}& ⊑\mathsf{gn}:\mathsf{parentFeature}\end{array}$$ Certainly, gn:parentFeature is a multivalued property that relates features with their parents, in either administrative or physical subdivision. Therefore, ins:subdivisionDe, which only relates administrative divisions, is subsumed by gn:parentFeature but not equivalent to it.

Besides ins:subdivisionDe, one could also consider the GeoNames properties gn:parentCountry and gn:parentADMN – where gn:parentADMN refers to a level N administrative parent, $\mathit{N}=1\mathrm{,}2\mathrm{,}3\mathrm{,}4$  – and the alignment $$\begin{array}{}\text{(18)}& \hfill & \mathsf{ins}:\mathsf{subdivisionDe}⊒\mathsf{gn}:\mathsf{parentCountry}\text{(19)}& \hfill & \mathsf{ins}:\mathsf{subdivisionDe}⊒\mathsf{gn}:\mathsf{parentADM}\mathit{N}\end{array}$$ However, (18) and (19) are not true because the properties gn:parentCountry and gn:parentADMN may be applied to non-administrative features (e.g. a lake), which is not the case of ins:subdivisionDe. The considered fragments of the Insee and GeoNames ontologies and their alignment are depicted in Fig. 4.

The following are the minimal keys that can be formed with the properties of the alignment made up of (16) and (17): $$\begin{array}{}\text{(20)}& \hfill \mathrm{(}\{\mathsf{ins}:\mathsf{nom}\}\{\mathsf{ins}:\mathsf{subdivisionDe}\}\mathrm{key}\mathsf{ins}:\mathsf{Com}\mathrm{)}& \text{(21)}& \hfill \mathrm{(}\{\mathsf{gn}:\mathsf{name}\}\{\mathsf{gn}:\mathsf{parentFeature}\}\mathrm{key}\mathsf{gn}:\mathsf{Com}\mathrm{)}& \end{array}$$ (20) cannot be used for interlinking because this requires ins:subdivisionDe and ins:parentFeature to be equivalent (Theorem 2), which is not true. This becomes apparent when we compare the values of French communes for both properties, as there are values that the communes have for ins:parentFeature but not for ins:subdivisionDe (e.g. the URI representing the European Union). Likewise, (21) is not useful.

From the above paragraph, we can conclude that keys and alignments are not useful for interlinking communes of Insee and GeoNames. Nevertheless, link keys are. More specifically, the following link keys can be used: $$\begin{array}{}\text{(22)}& \begin{array}{cc}\hfill & \mathrm{\left(}\right\{⟨\mathsf{ins}:\mathsf{nom}\mathrm{,}\mathsf{gn}:\mathsf{name}⟩\left\}\right\{⟨\mathsf{ins}:\mathsf{subdivisionDe}\mathrm{,}\hfill \\ \hfill & \mathsf{gn}:\mathsf{parentADM}\mathsf{3}⟩\}\mathrm{linkke}{y}^s⟨\mathsf{ins}:\mathsf{Com}\mathrm{,}\mathsf{gn}:\mathsf{Com}⟩\mathrm{)}\hfill \end{array}\text{(23)}& \begin{array}{cc}\hfill & \mathrm{\left(}\right\{⟨\mathsf{ins}:\mathsf{nom}\mathrm{,}\mathsf{gn}:\mathsf{name}⟩\left\}\right\{⟨\mathsf{ins}:\mathsf{subdivisionDe}\mathrm{,}\hfill \\ \hfill & \mathsf{gn}:\mathsf{parentADM}\mathsf{2}⟩\}\mathrm{linkke}{y}^s⟨\mathsf{ins}:\mathsf{Arr}\mathrm{,}\mathsf{gn}:\mathsf{Arr}⟩\mathrm{)}\hfill \end{array}\text{(24)}& \begin{array}{cc}\hfill & \mathrm{\left(}\right\{⟨\mathsf{ins}:\mathsf{nom}\mathrm{,}\mathsf{gn}:\mathsf{name}⟩\}\hfill \\ \hfill & \mathrm{linkke}{y}_{in}^s⟨\mathsf{ins}:\mathsf{Dép}\mathrm{,}\mathsf{gn}:\mathsf{Dep}⟩\mathrm{)}\hfill \end{array}\end{array}$$ Indeed, the links between departments can be found using (24) by comparing their names, and, once these links are found, they can be used to find links between arrondissements using (23) by comparing their names and the departments they belong to. Finally, the found links between arrondissements can be used to find links between communes using (22) by comparing their names and the arrondissements they belong to. We did so and compared the results with a reference link set. We obtained 100% precision and 97% recall. The latter was due to the similarity function used to compare name strings.

To conclude, let us stress that, even though (19) is not true, (22) and (23) hold and are useful for interlinking. This confirms once again that the properties of a link key are not necessarily semantically related via subsumption or equivalence.

9. Conclusions and further work

The relation between keys and link keys is much more subtle than may be thought of at first sight, and one may not be replaced by the other without care. In particular, we have shown that data interlinking with keys requires (a) a proper alignment (Theorems 1 and 2), and (b) completion in the case of eq-keys (Theorem 2). Data interlinking with link keys, in turn, does not need alignments (Theorems 3 and 4) but still needs completion in the case of eq-link keys (Theorem 4).

Strong link keys entail keys by definition, and keys with proper alignments entail strong link keys (Theorem 5). In this case, the links generated by a strong link key are the same as those generated by their associated side keys and alignments (Theorems 7 and 8).

Nonetheless, in addition to not needing an alignment, weak link keys may exist independently from the existence of any key of the individual ontologies (Theorem 6; if they are, then they are strong link keys), and yet they may be useful for interlinking datasets.

These results provide a clear picture of the relationships between key-inspired devices available for data interlinking. They can be easily transferred to the hybrid keys and link keys.

The work presented in this paper contributes grounding data interlinking methods based on keys and link keys. In particular, it justifies the work for directly extracting weak link keys [7] instead of searching for keys with matching alignments. Link key extraction directly focuses on what may be used for data interlinking instead of generating keys and alignments that may not be possible to exploit. Also, when no strong link key exists, link key extraction may find a suitable weak link key, though key extraction will not return any useful key.

The clarification of the semantics of link keys tackled in this paper should lead to complement data interlinking methods with inference methods. One approach consists in designing rules, inspired by the statements found in propositions of this paper, to infer (link) keys from (link) keys in the same way as Armstrong’s axioms [5] allow to derive functional dependencies. However, this approach is highly dependent on the actual schema language used. Another approach extends description logic reasoners to include keys [23] and link keys as axioms. In both cases, entailed link keys could be exploited by extended versions of reasoning-based data interlinking tools. This should also enable breaking the extraction + interlinking process by reasoning on link keys before interlinking in order to provide more accurate links, eventually more efficiently.