Nacira Abbas

Alexandre Bazin

Jérôme David

Amedeo Napoli

Discovery of Link Keys in Resource Description Framework Datasets Based on Pattern Structures

Keywords: Data Interlinking, Link Key Discovery, Link Key Candidate, Formal Concept Analysis, Pattern Structures, Redundancy of Link Sets

In this paper, we present a detailed and complete study on data interlinking and the discovery of identity links between two RDF -Resource Description Framework-datasets over the web of data. Data interlinking is the task of discovering identity links between individuals across datasets. Link keys are constructions based on pairs of properties and classes that can be considered as rules allowing to infer identity links between subjects in two RDF datasets. Here we investigate how FCA -Formal Concept Analysis-and its extensions are well adapted to investigate and to support the discovery of link keys. Indeed plain FCA allows to discover the so-called link key candidates, while a specific pattern structure allows to associate a pair of classes with every candidate. Different link key candidates can generate sets of identity links between individuals that can be considered as equal when they are regarded as partitions of the identity relation and thus involving a kind of redundancy. In this paper, such a redundancy is deeply studied thanks to partition pattern structures. In particular, experiments are proposed where it is shown that redundancy of link key candidates while not significant when based on identity of partitions appears to be much more significant when based on similarity.

Introduction

In this paper, we are interested in data interlinking through the discovery of identity links between two RDF (Resource Description Framework) datasets over the web of data [START_REF] Nentwig | A survey of current Link Discovery frameworks[END_REF]. RDF triples such as (subject,property,object) are the basic bricks of the web of data [START_REF] Hogan | The Web of Data[END_REF]. Elements in such triples may be described thanks to an RDF Schema and/or OWL -Web Ontology Language-ontologies. Moreover, a given subject can be represented in two different datasets by different individuals. Then data interlinking is the task of discovering identity links between individuals across different datasets. In particular, data interlinking is meaningful in data preparation, data cleaning, and noise reduction.

There are several approaches for discovering identity links between two RDF datasets. Some approaches, as in the systems LIMES [START_REF] Ngomo | LIMES -A Time-Efficient Approach for Large-Scale Link Discovery on the Web of Data[END_REF] and SILK [START_REF] Volz | Silk -A Link Discovery Framework for the Web of Data[END_REF], are based on link specifications which are rules declaring whether two elements should be linked. In addition, link specifications may also be specified by users or learned from data [START_REF] Isele | Active learning of expressive linkage rules using genetic programming[END_REF][START_REF] Ngomo | EAGLE: Efficient Active Learning of Link Specifications Using Genetic Programming[END_REF][START_REF] Ngomo | Unsupervised learning of link specifications: deterministic vs. non-deterministic[END_REF]. Other approaches are based on the discovery of sufficient conditions for declaring that two subjects are identical [START_REF] Saïs | L2R: A Logical Method for Reference Reconciliation[END_REF][START_REF] Al-Bakri | Inferring same-as facts from Linked Data: an iterative import-by-query approach[END_REF][START_REF] Al-Bakri | Uncertaintysensitive reasoning for inferring sameAs facts in linked data[END_REF]. Following this way, link keys extend the notion of keys in databases and can be viewed as rules allowing to infer identity links between subjects in two RDF datasets [START_REF] Atencia | Data interlinking through robust linkkey extraction[END_REF]. A link key is based on two sets of property pairs associated with a pair of classes. The property pairs correspond to sufficient conditions for declaring that two subjects are identical w.r.t. the associated pair of classes.

For example, the link key ({(designation,title)},{(creator,author)},(Book,Novel)) states that whenever an instance a of the class Book has the same values for the property designation as an instance b of the class Novel for the property title, and that a and b share at least one value for the properties creator and author, then a and b denote the same entity.

More formally, the link keys which are under investigation in this paper are composed of two sets of property pairs ({(p i , q i )} i∈I , {(p ′ j , q ′ j )} j∈J ) associated with a pair of classes (c 1 , c 2 ). Then, whenever an instance a of class c 1 has the same non empty set of values as an instance b of class c 2 , i.e. p i (a) = q i (b) for all property pairs in {(p i , q i )} i∈I , and shares at least one value for all property pairs in {(p ′ j , q ′ j )} j∈J , i.e. p ′ j (a) ∩ q ′ j (b) ̸ = ∅, then a and b denote the same entity. The first property set {(p i , q i )} i∈I corresponds to a "universal quantification" while the second property set {(p ′ j , q ′ j )} j∈J corresponds to an "existential quantification". An identity link is then materialized by the a owl:sameAs b link, where the OWL construction owl:sameAs represents an equivalence relation.

Link keys are not provided with RDF datasets and some algorithms were designed for automatically discovering such link keys [START_REF] Atencia | Data interlinking through robust linkkey extraction[END_REF][START_REF] Atencia | Link key candidate extraction with relational concept analysis[END_REF][START_REF] Abbas | Discovery of Link Keys in RDF Data Based on Pattern Structures: Preliminary Steps[END_REF]. These algorithms try to reduce the search space instead of checking every combination of property pairs and class pairs. They focus on the discovery of "link key candidates" which are made precise below and which involve maximality and closure. Accordingly, straightforward connections were established in [START_REF] Atencia | What can FCA do for database linkkey extraction?[END_REF][START_REF] Atencia | Link key candidate extraction with relational concept analysis[END_REF] between link key discovery and Formal Concept Analysis (FCA [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF]). Following the lines proposed in [START_REF] Atencia | What can FCA do for database linkkey extraction?[END_REF], FCA is applied in [START_REF] Atencia | Link key candidate extraction with relational concept analysis[END_REF] to a binary table where rows correspond to individual pairs and columns to property pairs. The intent of a resulting concept corresponds to a link key candidate while the extent includes potential identity links between individuals.

Afterwards, these identity links should be validated thanks to appropriate quality measures such as "coverage" and "discriminability" [START_REF] Atencia | Data interlinking through robust linkkey extraction[END_REF]. Coverage depends on linkage between entities, i.e., the more subjects are linked by a candidate the better is the coverage of the candidate. By contrast, discriminability assumes that subjects have to be distinct in each dataset and then measures the capability of a link key candidate to discriminate between subjects.

A generalization of the FCA-based approach was proposed in [START_REF] Abbas | Discovery of Link Keys in RDF Data Based on Pattern Structures: Preliminary Steps[END_REF], which relies on pattern structures [START_REF] Ganter | Pattern Structures and Their Projections[END_REF][START_REF] Kaytoue | Mining Gene Expression Data with Pattern Structures in Formal Concept Analysis[END_REF] and which takes into account different pairs of classes at the same time in the discovery of link keys. Link key candidates are searched in one pass and the class pairs associated with each discovered link key candidate are specified. There is no need to iterate over every pair of classes and the discovery process does not require any prior alignment. Moreover pairs of class expressions such as conjunctions or disjunctions of named classes may be returned with link key candidates rather than pairs of named classes.

Actually, link key candidates allow to generate different and maximal link sets, i.e., the mapping between individuals is close to a "bijection". However, some candidates are generating the same link set when the latter is considered as a partition w.r.t. the equivalence relation owl:sameAs. This leads to a form of "redundancy" as two different candidates that are inducing the same partition can be considered as equivalent w.r.t. the generated link sets. This redundancy can be detected thanks to the equivalence classes generated by the owl:sameAs relation. Then two candidates relying on the same partition can be considered as redundant and "merged". It should be noticed that no link key is removed in this case, and that merging records redundancy. In this way, the objective of the research work presented in [START_REF] Abbas | A Study of the Discovery and Redundancy of Link Keys Between Two RDF Datasets Based on Partition Pattern Structures[END_REF] was to check the existence and to evaluate the significance of such redundancy.

Based on "partition pattern structures" (pps) introduced in [START_REF] Baixeries | Characterizing functional dependencies in formal concept analysis with pattern structures[END_REF] for discovering functional dependencies in datasets, we were able to formalize link key discovery in taking into account sets of equivalent individuals w.r.t. owl:sameAs partitions. Then, a pattern concept represents a link key candidate and the related partition induced by the candidate. Experiments provided three main results: (i) the redundancy of link keys in real-world datasets is not so significant, (ii) the discovery of link key candidates based on pps is efficient and returns whenever possible a reduced number of non redundant candidates, (iii) the quality of the returned link keys is quite high when compared to competitors.

This paper is based on two previous publications at the "International Conference on Concept Lattices and Applications" (CLA 2020 and 2022) [START_REF] Abbas | Discovery of Link Keys in RDF Data Based on Pattern Structures: Preliminary Steps[END_REF][START_REF] Abbas | A Study of the Discovery and Redundancy of Link Keys Between Two RDF Datasets Based on Partition Pattern Structures[END_REF]. It proposes a complete and revised synthesis of both papers including an alternative formalization, additional explanations, and extended experiments. The application of partition pattern structure for detecting redundancy in link key discovery and an alternative way of dealing with redundancy are made precise. For completing and generalizing the research work initiated in [START_REF] Abbas | A Study of the Discovery and Redundancy of Link Keys Between Two RDF Datasets Based on Partition Pattern Structures[END_REF], we have carried out experiments where the equality operation corresponding to the owl:sameAs relation is weakened and replaced with a similarity operation. These experiments tell us that redundancy based on equality is in general small and not so important. By contrast, redundancy based on similarity appears to be much more significant with a similarity above rather high thresholds. In particular, this shows that this research line brings some benefits and contributes in a substantial way to general research about link keys.

The summary of the paper is as follows. Section 2 introduces RDF datasets and the basics about link key expressions/candidates, and link key discovery. Then in Section 3 the formalism of pattern structures, which extends plain Formal Concept Analysis, is made precise and supports the discovery of link key candidates with pairs of classes. Examples of a pattern structure, a pattern concept lattice, and a set of link key candidates are given in Section 3. In Section 5 redundancy of link key candidates is discussed, and as well the way how partition pattern structures allow to detect such redundancy. Section 6 provides details about experiments, describes the datasets which are reused, and shows how the use of a similarity brings another point of view on redundancy of link key candidates. Finally, before Conclusion, Section 7 presents the state of the art and especially the approaches which are close to the present research work.

Basics About Link Keys

The process of discovering link keys takes as input two RDF datasets, computes a set of potential link keys, called link key candidates, and evaluates them thanks to quality measures. This section introduces different definitions about RDF datasets that are used in the following.

RDF Dataset

An RDF dataset represents data as a collection of graphs associating entities to values or to other entities through properties. For the sake of simplicity and without loss of generality, we do not make the distinction between "RDF graph" and an "RDF dataset" in this paper.

Definition 1 (RDF Dataset). Let U denote a set of IRIs, i.e., "Internationalized Resource Identifiers", B a set of blank nodes, i.e., "anonymous resources" or "variables", and L a set of literals, i.e., "string values".

An RDF dataset is a set of triples (s, p, o)

∈ (U ∪ B) × U × (U ∪ B ∪ L).
Here There are also different sets of instances namely: Furthermore, the "value" of b17 for property auth is auth(b17) = {Stephen King, Peter Straub}.

I NC (Character) = {a1,
It is possible to lift the above restriction to named classes and to consider conjunctions of named classes such as c 1 ⊓ class c 2 , or disjunctions of named classes such as c 1 ⊔ class c 2 . The intuition justifying such an extension relies on the fact that ontologies related to RDF datasets are usually based on different levels of abstraction. For example, the set of female scientists may be represented by the conjunction of the classes "Woman" and "Scientist" in one dataset, and by the named class "FemScientist" in another dataset. In such a case, it is interesting to be able to take into account conjunctions and also disjunctions of classes. Then in agreement with the corresponding constructions in Description Logics [START_REF] Baader | The Description Logic Handbook: Theory, Implementation and Applications[END_REF], the set of class expressions over the RDF dataset D denoted by C(D), including named classes, plus conjunctions (c 1 ⊓ class c 2 ∈ C(D)) and disjunctions of named classes (c 1 ⊔ class c 2 ∈ C(D)), can be recursively defined as follows:

-If c ∈ N C(D) then c ∈ C(D), -if c 1 , c 2 ∈ C(D) then c 1 ⊓ class c 2 ∈ C(D), -if c 1 , c 2 ∈ C(D) then c 1 ⊔ class c 2 ∈ C(D).
Accordingly, the set of instances of a class c ∈ C(D), denoted by I(c), is recursively defined as follows:

-If c ∈ N C(D) then I(c) = I N C (c), -if c 1 , c 2 , c 3 ∈ C(D) such as c 1 = c 2 ⊓ class c 3 , then I(c 1 ) = I(c 2 ) ∩ I(c 3 ), -if c 1 , c 2 , c 3 ∈ C(D) such as c 1 = c 2 ⊔ class c 3 , then I(c 1 ) = I(c 2 ) ∪ I(c 3 ).

Link key expressions, generated links and candidate link keys

Link keys are based on a syntax and a semantics, and they are used to generate identity links between individuals. The discovery of link keys relies on the definitions of "link key expression", "identity link", and "link key candidate", as made precise here below.

Definition 2 (Link key expression and generated identity link set). A link key expression over two RDF datasets D 1 and D 2 is a tuple k = (Eq, In, (c 1 , c 2 )) such that In ⊆ P (D 1 ) × P (D 2 ), Eq ⊆ In, c 1 ∈ C(D 1 ), and c 2 ∈ C(D 2 ).

The set of identity links generated by k is denoted by L(k) and includes the set of pairs of instances (a, b) ∈ I(c 1 ) × I(c 2 ) satisfying:

(i) for all (p, q) ∈ Eq, p(a) = q(b) and p(a) ̸ = ∅, (ii) for all (p, q) ∈ In \ Eq, p(a) ∩ q(b) ̸ = ∅.

Intuitively, a link key expression k = (Eq, In, (c 1 , c 2 )) generates the identity link (a, b) between individuals a instance of class c 1 and b instance of class c 2 , when (i) for all (p, q) ∈ Eq, a has the same values for p as b has for q, and (ii) for all (p ′ , q ′ ) ∈ In, a and b share at least one value for p ′ and q ′ . The number of link key expressions may be exponential w.r.t. the number of properties. In addition, it is possible that several link key expressions generate the same set of identity links. Then, to reduce the number of potential link keys, link key discovery algorithms only consider the so-called link key candidates. The latter correspond to link key expressions that generate at least one link and that are "maximal" among all link key expressions generating the same links.

Definition 3 (Link key candidate). A link key candidate is a link key expression

k 1 = (Eq 1 , In 1 , (c 1 , c 2 )) such that: (i) L(k 1 ) ̸ = ∅, (ii)
there does not exist another link key expression

k 2 = (Eq 2 , In 2 , (c 1 , c 2 )) over D 1 and D 2 such that Eq 1 ⊂ Eq 2 , In 1 ⊂ In 2 , and L(k 1 ) = L(k 2 ).
For example, consider the expressions k1 and k2: k1 = ({(date, year),(desig, title)},{(date, year),(desig, title)}, (Book, Dictionary)), k2 = ({(date, year)},{(date, year)},(Book, Dictionary)).

The link key expressions k1 and k2 both generate the same set of links, namely L(k1) = L(k2) = {(a13,b13), (a14,b14)}. As k1 is larger than k2, i.e. {(date,year)} ⊂ {(date,year),(desig,title)}, and as there is no other link key expression generating the same set of links as k1, then k1 is considered as a link key candidate.

Quality measures

A link key candidate can be promoted as a "valid link key" as soon as it generates only valid identity links. As it is not feasible to check one by one every identity link, adapted measures have been introduced for evaluating the quality of a link key candidate. In this way, "discriminability" and "coverage" are two quality measures that work in an unsupervised scenario, i.e., when reference links are not available, as this is the case most of the time [START_REF] Atencia | Data interlinking through robust linkkey extraction[END_REF].

Intuitively, coverage (resp. discriminability) evaluates how close is a set of links to a surjective (resp. injective) map. Hence, coverage is maximum when all instances of the considered classes are linked to "at least" another instance. Discriminability is maximum when instances are linked to "at most" one instance. The coverage of L over c 1 and c 2 is defined as:

co(L, c 1 , c 2 ) = |π 1 (L) ∪ π 2 (L)| |I(c 1 ) ∪ I(c 2 )|
The discriminability of L is defined as:

di(L) = min(|π 1 (L)|, |π 2 (L)|) |L|
Similarly to the F-measure, discriminability and coverage can be combined into a harmonic mean denoted by hm (hmean).

A Semantics for Link Keys

Link keys are not only syntactic constructions and a semantics may be defined for such expressions. Usually, the semantics of link keys reuses the Description Logics (DL) for interpretation I = (∆ I , • I ) [START_REF] Baader | The Description Logic Handbook: Theory, Implementation and Applications[END_REF]. The set ∆ I is called the interpretation domain and is composed of individuals, while the interpretation function • I maps conceptual expressions into subsets of the interpretation domain, i.e., subsets of individuals. Such a semantics allows to check the consistency of knowledge bases related by link keys, to infer subsumption relations between link keys, and to define the validity of a link key w.r.t. an interpretation.

Definition 5 (Link key). A link key is an expression of the form (Eq, In, (c 1 , c 2 )) where Eq and In are sets of pairs of properties with Eq ⊆ In, and c 1 and c 2 are classes.

An interpretation I satisfies a link key (Eq, In, 1) and ( 2) below it can be inferred that α = β. (1) p I i (α) = q I i (β) with p I i (α) ̸ = ∅ for all (p i , q i ) ∈ Eq, (2) p I j (α) ∩ q I j (β) ̸ = ∅ for all (p j , q j ) ∈ In, The link keys which are considered here are a merge of "weak eq-link keys" and "weak in-link keys" as this is introduced and made precise in [START_REF] Atencia | On the relation between keys and link keys for data interlinking[END_REF]. However, the present work is not directly related to semantics of link keys and we will no more elaborate in this direction.

(c 1 , c 2 )) if, for any α ∈ c I 1 and β ∈ c I 2 verifying (

Basics About Pattern Structures

Pattern structures [START_REF] Ganter | Pattern Structures and Their Projections[END_REF][START_REF] Kaytoue | Mining Gene Expression Data with Pattern Structures in Formal Concept Analysis[END_REF] are an extension of Formal Concept Analysis [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF] aimed at adapting the FCA formalism to objects whose descriptions is too complex to be expressed as a set of binary attributes. This is the case when objects have attributes whose values can be numbers, intervals, sequences, trees, graphs. . . It should be noticed that "object" here denotes an element or an individual which has a description and not as a component of an RDF triple.

Definition 6 (Pattern structure). A pattern structure is a triple (G, (D, ⊓), δ), where G is a set of objects, D is a set of descriptions, and δ : G → D maps an object to its description.

Moreover, the operator ⊓ is a similarity operator that defines the similarity between two descriptions. In addition, given two descriptions d 1 and d 2 , ⊓ is associated with a partial ordering denoted by ⊑ as follows:

d 1 ⊓ d 2 = d 1 iff d 1 ⊑ d 2 .
In particular, the set of potential descriptions (D, ⊑) forms a meet-semilattice. The semi-lattice (D, ⊑) can be interpreted as the set of descriptions ordered by the ⊑ relation (subsumption). Actually ⊓ maps pairs of descriptions to their least common subsumer as explained in [START_REF] Ganter | Pattern Structures and Their Projections[END_REF]. For example, Figure 2 depicts a simple pattern structure in which objects are described by intervals. Details and examples about "interval pattern structures" can be found in [START_REF] Kaytoue | Mining Gene Expression Data with Pattern Structures in Formal Concept Analysis[END_REF].

Objects Descriptions g 1 [1, 2] g 2 [2, 3] g 3 [3, 4]
Figure 2: A pattern structure with three objects g 1 , g 2 and g 3 whose description is an interval. The similarity ⊓ between two intervals is defined by their convex hull, i.e.

[a, b] ⊓ [c, d] = [min(a, c), max(b, d)]. Then δ(g 1 ) ⊓ δ(g 2 ) = [1, 2] ⊓ [2, 3] = [1, 3].
As in plain FCA, given a pattern structure (G, (D, ⊓), δ), two derivation operators denoted by • ⋄ can be defined as follows:

• ⋄ : 2 G → D, G ⋄ = g∈G δ(g) • ⋄ : D → 2 G , d ⋄ = {g ∈ G | d ⊓ δ(g) = d}
It should be noticed that, alternatively, d ⊓ δ(g) = d can be rewritten as d ⊑ δ(g). Given a set of objects G, G ⋄ returns the most specific description common to all the objects in G. Dually, given a description d, d ⋄ returns all the objects whose description is more specific than d. Based on these two derivation operators we can define a pattern concept as:

Definition 7 (Pattern concept). A pattern concept in (G, (D, ⊓), δ) is a pair (A, d) with A ⊆ G and d ∈ D such that A = d ⋄ and d = A ⋄ .
For example, in Figure 3

, ({g 1 , g 2 }, [1, 3]) is a concept as {g 1 , g 2 } ⋄ = δ(g 1 ) ⊓ δ(g 2 ) = [1, 3] and dually [1, 3] ⋄ = {g 1 , g 2 }.
Then, as this is the case in plain FCA, the set of all concepts of a pattern structure can be partially ordered by inclusion of extents to form a complete lattice called the "pattern concept lattice" of the pattern structure.

In the pattern concept lattice, it can be checked that every object is attached to a unique concept, i.e., the corresponding "object pattern concept" (the "object concept" in plain FCA) [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF]. Dually, for every description there is an "description pattern concept", also called an "attribute pattern concept" (the "attribute concept" in plain FCA). Intuitively, considering the order from top to bottom in the lattice, as soon as a description is attached to a given pattern concept, it is attached to all the pattern concepts which are below. For example, the description pattern concept of interval [START_REF] Hogan | The Web of Data[END_REF][START_REF] Volz | Silk -A Link Discovery Framework for the Web of Data[END_REF] is the pattern concept ({g 2 , g 3 }, [START_REF] Hogan | The Web of Data[END_REF][START_REF] Volz | Silk -A Link Discovery Framework for the Web of Data[END_REF]) and interval [START_REF] Hogan | The Web of Data[END_REF][START_REF] Volz | Silk -A Link Discovery Framework for the Web of Data[END_REF] is subsumed by the intents [START_REF] Hogan | The Web of Data[END_REF][START_REF] Ngomo | LIMES -A Time-Efficient Approach for Large-Scale Link Discovery on the Web of Data[END_REF] and [START_REF] Ngomo | LIMES -A Time-Efficient Approach for Large-Scale Link Discovery on the Web of Data[END_REF][START_REF] Volz | Silk -A Link Discovery Framework for the Web of Data[END_REF] lying in the pattern concepts below. Recall that for descriptions d 1 and d 2 ,

d 1 ⊓ d 2 = d 1 iff d 1 ⊑ d 2 .
(∅, ⊤)

({g 1 }, [1, 2]) ({g 2 }, [2, 3]) ({g 3 }, [3, 4]) ({g 1 , g 2 }, [1, 3]) ({g 2 , g 3 }, [2, 4]) ({g 1 , g 2 , g 3 }, [1, 4])
Figure 3: The pattern concept lattice related to the pattern structure given in Figure 2. The ⊤ symbol is arbitrarily added to the meet-semilattice of intervals in order to make it a lattice.

This can be read for intervals as follows:

[2, 3] ⊓ [2, 4] = [2, 4] iff [2, 4] ⊆ [2, 3] [17]
. Dually, considering the order from bottom to top in the lattice, as soon as an object is attached to a given pattern concept, it is attached to all the pattern concepts which are above. For example, the object pattern concept of

{g 1 } is the pattern concept ({g 1 }, [1, 2]
), and {g 1 } is lying in all extents above this pattern concept. More formally, the object pattern concept is defined as γ(g) = (g ⋄⋄ , g ⋄ ), while the description pattern concept is defined as µ(d) = (d ⋄ , d ⋄⋄ ). Moreover, the set of object pattern concepts ordered by the inclusion relation on the extents is called the OC-poset of the pattern structure [START_REF] Berry | Hermes: a simple and efficient algorithm for building the AOC-poset of a binary relation[END_REF]. Actually, this is a partially ordered set and not necessarily a lattice. More details and an example involving the OC-poset is proposed in Section 5.

Discovering Link Keys Within Pattern Structures

In this section, we present the use of pattern structures to discover link key candidates in RDF datasets. The pairs of classes considered in the link key expressions are restricted to class expressions composed of named classes, or conjunctions of named classes such as c 1 ⊓ class c 2 , or disjunctions of named classes such as c 1 ⊔ class c 2 . Recall that conjunctions and disjunctions of named classes correspond to respectively conjunction and disjunction of concepts in Description Logics [START_REF] Baader | The Description Logic Handbook: Theory, Implementation and Applications[END_REF]. Table 1: The LK-pattern structure corresponding to the datasets D1 and D2 given in Figure 1.

(Eq 1 , In 1 , (c D1 1 , c D2 1 )) ⊓ (Eq 2 , In 2 , (c D1 2 , c D2 2 )) = (Eq 1 ∩ Eq 2 , In 1 ∩ In 2 , (c D1 1 ⊔ class c D1 2 , c D2 1 ⊔ class c D2 2 )). ( iii) Mapping δ: δ : S(D 1 ) × S(D 2 ) -→ E associates a pair (s 1 , s 2 ) ∈ S(D 1 ) × S(D 2 )
to its description δ((s 1 , s 2 )) = (Eq, In, (c 1 , c 2 )) where: For example, the LK-pattern structure corresponding to the datasets given in Figure 1 is detailed in Table 1. The pattern concept lattice corresponding to this LK-pattern structure is displayed in Figure 4.

Eq = {(p 1 , p 2 ) | p 1 (s 1 ) = p 2 (s 2 ) ̸ = ∅}, In = {(p 1 , p 2 ) | p 1 (s 1 ) ∩ p 2 (s 2 ) ̸ = ∅}, c
In the pattern concept lattice, every pattern concept is based on a pair of closed sets, namely an intent representing a link key candidate and an extent representing the related link set, plus a pair of classes related to the type of the subjects under study. For example, the link key candidate k9 is associated with the pair of classes (Woman ⊓ class Scientist, FemScientist), i.e., k9 relates an instance of the class conjunction Woman ⊓ class Scientist with an instance of the class FemScientist. Moreover, different link key candidates may have the same sets of pairs of properties Eq and In, but they are associated with different pairs of class expressions, as this is the case for k1a and k 1b . Indeed, k1a and k 1b have the same sets of properties pairs, namely {(desig,title)}, {(desig,title)}, while they are associated respectively with (Book,Dictionary ⊔ class Novel) and (Book,Novel).

The properties appearing in such link key candidates describe subjects belonging to different classes. For example, the property title in k1a and k 1b describes instances of the classes Dictionary or Novel. Furthermore, it should be noticed that one pair of classes can be associated with more than one link key candidate. For example, the pair of classes (Book,Novel) (in orange in Figure 4) is associated with the four link key candidates k3, k4, k5, and k6. In particular, this means that there are four possible choices to select a link key candidate for the pair of classes (Book,Novel). Now let us have a more precise look at the link sets generated by link key candidates. For example, the link set L(k11) = {(a1,b1),(a2,b2),(a2,b1)} is generated by k11 and L(k12) = {(a1,b1),(a2,b2),(a1,b2)} is generated by k12. An identity link states that two subjects represent the same entity and materialized by the owl:sameAs relation. The latter is an equivalence relation, i.e., reflexive, symmetric, and transitive. Relying on the transitivity of owl:sameAs and considering link sets as partitions, it comes that k11 and k12 are generating the same equivalence class of links [START_REF] Abbas | A Study of the Discovery and Redundancy of Link Keys Between Two RDF Datasets Based on Partition Pattern Structures[END_REF]. Then it can be concluded that the four subjects a1, a2, b1, and b2, represent the same entity.

Therefore, when link sets are considered as partitions induced by owl:sameAs, the two link key candidates k11 and k12 are carrying the same information about identity links. In other words, this involves a kind of "redundancy", i.e., it is 1.

no longer true that every link key candidate provides information that cannot be retrieved from the rest of the link key candidates. Accordingly, the topic of the next Section is to present how to define, to detect, and to deal with such redundancy.

Detecting Redundant Link Keys with Partition Pattern Structures

Detecting the Redundancy of Link Keys based on Partition Pattern Structures

In [START_REF] Baixeries | Characterizing functional dependencies in formal concept analysis with pattern structures[END_REF], authors are using "partition pattern structures" for discovering functional dependencies (FDs), which correspond to attribute implications or to pairs of attributes having the same behavior w.r.t. an object partition. Here we are facing the same kind of problem and thus we reuse the same approach, replacing "implication" by "link key candidate", knowing that an implication within a concept lattice is related with a closed set as link key candidates are.

Below, we show how the detection of redundancy among link key candidates is based on the use of partition pattern structures, where partitions of subjects are composed of equivalent subsets of subjects in generated link sets. Firstly, we present a motivating example explaining the process of redundancy detection. In Figure 4, the link key candidate k 1b generates the following link set: L(k 1b ) = {(a13,b13),(a14,b14),(a13,b14),(a14,b13)}.

Based on the symmetry and transitivity of the owl:sameAs relation, it is possible to compute the equivalence class of subjects lying in the L(k 1b ) link set. Then, the link (a13,a14) can be inferred from the pairs (a13,b13) and (b13,a14) (using symmetry for the latter). In particular, these two pairs can be rewritten as the RDF triples (a13,owl:sameAs,b13) and (b13,owl:sameAs,a14). Computing the transitive closure of the owl:sameAs relation in L(k 1b ) yields the partition {a13,a14,b13,b14}. This partition can be regarded as an equivalence class or as a "complete graph" -all vertices are connected to each others. Based on that, we have the following definition: Definition 9 (Partition of subjects induced by a link key). Let D 1 and D 2 be two RDF datasets and k a link key candidate. The partition of subjects induced by k is defined as the quotient set: P art(k) = L(k)/owl:sameAs.

Before making precise the "partition pattern structure" supporting the discovery of such quotient sets, we recall that the meet of two partitions ⊓ part is defined as the coarsest common refinement of the two partitions [START_REF] Baixeries | Characterizing functional dependencies in formal concept analysis with pattern structures[END_REF]. For example:

{{a15,a16,b15,b16}} ⊓part {{a15,b15},{a16,b16},{a17,b17}} = {{a15,b15},{a16,b16}}.

Given two RDF datasets D 1 and D 1 , the set of instances I(D 1 ) ∪ I(D 1 ), the related set of partitions equipped with the similarity operator ⊓ part , we can build the following "partition pattern structure": For example, the LK-partition pattern structure corresponding to the RDF datasets displayed in Figure 1 is given in Table 2. The objects are the link key candidates k1a, k 1b , k2, . . . , k9, k11, k12, k13, which are taken from the LK-pattern structure given in Table 1, while the descriptions are the related partitions of subjects.

PPS objects (k

i ) Descriptions (δ(k i ) = P art(k i )) k 1a {{a 13 ,
k 11 {{a 1 , a 2 , b 1 , b 2 }} k 12 {{a 1 , a 2 , b 1 , b 2 }} k 13 {{a 1 , b 1 }, {a 2 , b 2 }} Table 2:
The "partition pattern structure" corresponding to the pattern structure given in Table 1.

Pattern concepts from this LK-partition pattern structure are composed of a set of link keys (the extent) and a partition of the set of instances (the intent) that is the coarsest refinement of the partitions induced by the link keys in the extent. In order to detect redundant link keys, we want to find sets of link keys that induce the same partition of instances, i.e. link keys k i , k j such that P art(k i ) = P art(k j ). As such, we do not need all the concepts of this LK-partition pattern structure but only the concepts in which the intent is a partition of subjects induced by a single link key, i.e. concepts of the form

(k ⋄⋄ i , k ⋄ i ).
Those concepts are, by definition, the object concepts introducers (about the OC-poset, see Section 3 and [START_REF] Berry | Hermes: a simple and efficient algorithm for building the AOC-poset of a binary relation[END_REF]). If the extent of these concepts contains more than one element, it contains redundant link keys.

Figure 5 shows the OC-poset of the running example completed into a lattice (for the sake of readability). We can observe that the link key candidates k11 and k12 are merged into the same concept, at the bottom left. This concept can be interpreted in the following way: k11 and k12 are inducing the same partition and they should be considered as equivalent. By contrast, the extents of the other concepts contain only a single element as these link key candidates are not redundant.

From Partition Equality to Partition Similarity

Partitions of subjects induced by link keys can be different but still close. Then, instead of comparing partitions thanks to equality, one can use an adapted similarity measure. Given two partitions, such a similarity measure can be defined as the ratio of the common equivalence classes among all equivalence classes composing both partitions.

Definition 11 (Similarity between partitions). Given two partitions P 1 and P 2 , the similarity measure between P 1 and P 2 can be defined as: Figure 5: The OC-poset of the LK-partition pattern structure given in Table 2.

σ(P 1 , P 2 ) = |P 1 ∩ P 2 | |P 1 ∪ P 2 | {k1a,
For example, in Table 2, the similarity between Part(k3) and Part(k4) is 1/4 because Part(k3) and Part(k4) only share one equivalence class, namely {a17,b17}. By contrast, the similarity between partitions Part(k5) and Part(k6) is 0 because no equivalence class is shared, even if there exists a subsumption relation between k5 and k6 (see Figure 5).

In data clustering, the Rand index is usually used for comparing partitions [START_REF] Rand | Objective criteria for the evaluation of clustering methods[END_REF]. Since this index is defined over pairs of elements, it may return a more precise estimation of similarity. However, it requires that the two compared partitions are defined over the same set of objects, which is not the case here.

Here after, in Section 6, we present experiments about the redundancy of link keys in real-world datasets. Moreover, we also discuss the contrast existing between the use of equality and the use of similarity for comparing partitions. Actually, redundancy which is not really significant when based on equality becomes much more significant when based on similarity.

Experiments

There are two main objectives in these experiments. The first one is to show how the discovery of link keys based on pattern structure extends the related process based on FCA as proposed in [START_REF] Atencia | Link key candidate extraction with relational concept analysis[END_REF]. The second one is to investigate in real-world datasets how significant is redundancy among link keys, when partition pattern structures are used to detect such redundancy. Table 3: The description of the datasets used in the experiments. The columns #inst., #prop., and #triples, respectively denote the number of instances, of properties, and of triples in each dataset. The number of link key candidates generated in the pattern structure is given in the column |LK-PS|.

The Datasets and Their Contents

In these experiments, the so-called "tasks" described in Table 3 are taken from OAEI1 2010. A task consists in discovering links between instances of the two corresponding datasets given in the column "Dataset". For every task, a set of reference owl:sameAs links is provided (gold standard). Accordingly, reference links between classes r1:Restaurant and r2:Restaurant are provided in the task Restaurants, and between classes p11:Person and p12:Person as well. By contrast, as they were not provided, we built the reference links between r1:Address and r2:Address, and between classes p11:Address and p12:Address The task Pr, built on purpose, is based on a combination of Restaurant1 and Person11 from one side, and a combination of Restaurant2 and Person12 from the other side. Moreover, we considered the task Actor introduced in [START_REF] Symeonidou | VICKEY: Mining Conditional Keys on Knowledge Bases[END_REF] which consists in linking the class db:Actor from DBpedia and the class yago:Actor from Yago. A set of reference links between these two classes is provided.

Regarding the provenance of these datasets, Restaurant1 and Person1 are taken from the well-known "Ontology Alignment Evaluation Initiative (OAEI)" which includes a collection of benchmarks designed to assess and to compare the performance of ontology alignment systems, including data interlinking systems. Experiments were conducted on additional datasets taken from OAEI, namely Doremus (OAEI 2016) and SPIMBench (OAEI 2018), and similar results were observed.

Finally, experiments were also conducted on the Actor dataset, which was extracted from DBpedia and Yago. This dataset was selected because of its particular use in experiments about data interlinking based on keys and conditional keys [START_REF] Symeonidou | VICKEY: Mining Conditional Keys on Knowledge Bases[END_REF]. Additional results about these last experiments can be found in [START_REF] Abbas | A Study of the Discovery and Redundancy of Link Keys Between Two RDF Datasets Based on Partition Pattern Structures[END_REF].

A Pattern Structure for Link Key Discovery

As pointed out above, one objective in these experiments is to understand to which extent link key discovery based on pattern structure extends the FCAbased approach proposed in [START_REF] Atencia | Link key candidate extraction with relational concept analysis[END_REF]. Thus link key candidates were generated using both methods and then ranked thanks to hm, i.e., the harmonic mean of coverage and discriminability. The results returned by the FCA-based process can be interpreted as follows:

-The top link key candidate for task Restaurants, say k 1st R , generates links between classes r1:Restaurant and r2:Restaurant, while k 1st R does not generate any link between classes r1:Address and r2:Address. The link key generating links between r1:Address and r2:Address is ranked second.

-The top link key candidate for task Person1, say k 1st P1 , generates links between classes p11:Person and p12:Person, while k 1st P1 does not generate any link between classes p11:Address and p12:Address. Moreover, the link key candidates ranked from 1 to 8 do not generate any link between classes p11:Address and p12:Address.

-The top link key candidate for task Pr, k 1st

Pr , generates links between classes p11:Person and p12:Person only. The first link key candidate generating links between classes p11:Address and p12:Address is ranked 8 th .

The first link key candidate generating links between classes r1:Restaurant and r2:Restaurant is ranked at position 1976. Moreover, the first link key candidate generating links between classes r1:Address and r2:Address is ranked at position 2049.

-Finally, the top link key candidate for task Actor generates links between db:Actor and yago:Actor, which are the most general classes in this task.

Then the interest of such link key candidates is rather low.

The FCA-based method for discovering link key candidates returns candidates without specifying the pairs of classes, such as ({}, {(r1:name,r2:name)}, ()), which is the top link key candidate in the task Restaurants. This link key candidate can be interpreted as follows: if an instance of Restaurant1 and an instance of Restaurant2 share at least a value for the property name, then these two instances denote the same entity. Even a non expert person may conclude that the validity of such a link key is not very high, since holding the same name does not mean at all lying at the same place.

By contrast, the use of an adapted pattern structure as discussed in this paper allows one to discover link key candidates with related pairs of classes. Then it is straightforward to select link key candidates w.r.t. a target pair of classes. For example, in the task Restaurants, it is possible to select if required the top link key candidate defined over classes r1:Restaurant and r2:Restaurant, namely ({},{(r1:name,r2:name)},(r1:Restaurant,r2:Restaurant)). Then, the first link key candidate defined over classes r1:Address and r2:Address can be selected in In this experiment, we do not count pairs of the same partition (P, P ) (reflexivity) and we count pairs (P 1 , P 2 ) and (P 2 , P 1 ) as only one pair (symmetry).

continuation, namely ({},{(r1:street,r2:street)},(r1:Address,r2:Address)). This process ensures a progressive selection process of link key candidates, where any class pair can be considered, excluding inconsistent or not relevant pairs. Let us consider now the link key candidate ({},{(r1:name,p12:given_name)}, (r1:Restaurant,p12:Person)) that is returned in task Pr. Actually, this link key candidate instantiates an inconsistent pair of classes, since a restaurant and a person cannot materialize the same entity. As such this candidate should be excluded by a domain expert. Accordingly, the paper [START_REF] Abbas | LKSA : un algorithme de sélection de clés de liage dans des données RDF guidée par des paires de classes[END_REF] follows this idea and proposes the LKSA algorithm aimed at the selection of link key candidate guided by the associated pairs of classes. This enforces the fact that link key candidates with associated pairs of classes are significant and bring an added value in link key management.

The Redundancy of Link key candidates

The next experiments are aimed at determining how important is redundancy of link key candidates in real-world datasets. Firstly, the set of link key candidates, named "LK-PS", is generated thanks to the LK-pattern structure. Then the redundancy of candidates is based on the equality of partitions in the LK-partition pattern structure, i.e., two link key candidates are declared as redundant when they induce the same link partition. Then, the set of link key candidates lying in the OC-poset, related to the LK-partition pattern structure and named "LK-PPS", can be generated. The results can be read as follows. In the tasks Restaurants, Person1, and Pr, it comes that |LK-PS| = |LK-PPS|. Thus no redundancy among link keys can be observed in these real-world datasets. Besides that, in task Actor, there are 29 pairs of partitions which are equal, showing that some redundant candidates are existing in these datasets. More precisely, |LK-PPS| is lower than |K-PS| by 1%.

Hence, it can be concluded that redundancy of link key candidates based on equality is not really significant in the real-world datasets considered in these experiments. This also shows that equality of partitions is probably a too strong constraint and should be relaxed. Following this line, the next experiments are no longer based on equality of partitions but instead on similarity of partitions as introduced in Definition 11. The similarity measure is evaluated for all pairs of candidates contained in LK-PS. Figure 6 shows the cumulative distributions for each task.

The results can be read as follows. The link key candidates generate similar partitions when the similarity threshold is equal or below 0.8 in task Restaurants, and when the similarity threshold is equal or below 0.9 in tasks Person 1 and Pr.

In the task Actor, it can be observed that 29 pairs of link key candidates are generating the same partitions when the similarity threshold is 1, 0. By contrast, this number exponentially increases when the threshold is set to 0.9, as the number of similar pairs of partitions jumps from 29 to 1067! More generally, such a break can be verified in all the datasets with threshold values varying from 0.5 to 0.9, except in Restaurants where the number of pairs is smaller than in the other datasets.

Contrasting the results of the experiments based on equality of partitions, the experiments based on similarity show that a "redundancy" effectively exists in real-world datasets, even if it is rather weak. Then redundancy based on similarity of partitions can be considered as a valuable criterion for merging link key candidates, especially in large datasets. Indeed, the number of link key candidates can increase very quickly, and then the resulting pattern concept lattices become much harder to visualize, to handle, and to interpret. Merging redundant link keys based on similarity of partitions is a way to minimize the total number of link keys and to build kinds of "classes" of link keys. Then such classes of link keys can be proposed to domain experts for evaluation and interpretation. More should be done in this way and this opens new lines of research for future work.

Related Work

Data interlinking is a difficult task is studied since a long time. Systems such as "SILK" [START_REF] Volz | Silk -A Link Discovery Framework for the Web of Data[END_REF] and "LIMES" [START_REF] Ngomo | LIMES -A Time-Efficient Approach for Large-Scale Link Discovery on the Web of Data[END_REF] rely on link specifications to discover links, and in particular identity links, between two RDF datasets. Link specifications define conditions that subjects should meet in order to be linked. These specifications are complex, as they are composed of many elements, (i) properties to be compared, (ii) transformations to be applied, (iii) similarity measures to be used for comparing pairs, (iv) aggregation functions for combining several similarity values, and finally (v) similarity thresholds. To optimize link generation in terms of runtime efficiency and scaling, SILK relies on blocking strategies. By contrast, LIMES takes advantage of the triangular inequality in the Euclidean space for reducing the number of comparisons.

Moreover, in SILK and LIMES, while users may manually define link specifications, algorithms such as "RAVEN" [START_REF] Ngomo | RAVEN -Active Learning of Link Specifications[END_REF], "EAGLE" [START_REF] Ngomo | EAGLE: Efficient Active Learning of Link Specifications Using Genetic Programming[END_REF], and "LIGON" [START_REF] Sherif | LIGON -link discovery with noisy oracles[END_REF], are used to automatically discover links between datasets. One main common characteristic shared by these algorithms is that they are based on machine learning techniques, and thus they require a set of reference links. Furthermore, they do not take into account the semantics of ontologies possibly attached to the considered datasets, which describe elements in the RDF triples and provide classes.

As underlined above, link specifications require the definition of properties and classes to be compared, as well as determining the adapted similarity measures and associated thresholds. To a certain extent, link keys can be considered as a particular kind of link specifications. In this way, link key discovery techniques can be valuable assets and complements for supporting approaches based on link specifications, as they automatically provide properties and classes to be compared without requiring reference links. Such properties and classes provide a support for link specification along with similarity measures and thresholds.

There are some other approaches in link discovery relying on logical axioms from which are deriving the researched links. As they are based on a logical interpretation, logical reasoners or rule interpreters can take advantage of logical axioms to infer such new facts. These approaches are more efficient when the descriptions of the same entity are likely to be identical. In particular, keybased approaches are falling in this category. A key is a set of properties whose values unequivocally define instances of the associated class within a dataset. Although keys are not directly intended to be used in data interlinking, they can easily be used for solving this task, as shown in the following example. Let us consider two datasets, say D1 and D2, and the following key related to D1 and D2, namely "{firstName,lastName}, (Person)". Here firstName and lastName are properties, and Person is a class of individuals related to D1 and D2. The key can be interpreted as follows: when an instance say p1 of Person in D1 and an instance say p2 of the same class Person in D2 have the same firstName and the same lastName, then p1 and p2 represent the same entity, and an identity link can be created for relating p1 and p2. As one can see, based on the above description, keys are very close to link keys.

Keys, as this is also the case for link keys, are not necessarily provided in datasets, and various approaches have been proposed to automatically discovering such keys. For example, the "KD2R" algorithm [START_REF] Pernelle | An automatic key discovery approach for data linking[END_REF] discovers keys that are valid in multiple RDF datasets. However, when the datasets contain duplicates or erroneous data, no keys can be discovered using this approach. Furthermore, the KD2R algorithm is hardly scalable when dealing with large datasets. Thus a new algorithm called "SAKey" was introduced in [START_REF] Symeonidou | SAKey: Scalable Almost Key Discovery in RDF Data[END_REF] to improve applicability and scalability of the precedent key-based approach. SAKey discovers keys with exceptions called n-almost keys. A set of properties is an n-almost key if at most n instances share the same values for this set of properties. A later improvement was brought in the "VICKEY" algorithm [START_REF] Symeonidou | VICKEY: Mining Conditional Keys on Knowledge Bases[END_REF] for dealing with the absence of keys in some datasets. VICKEY is able to discover the so-called "conditional keys" that are valid only in a part of the whole dataset where specific conditions made precise within the conditional key are met. When they are running, KD2R, SAKey, and VICKEY, are following the same main steps. Firstly, they compute a set of maximal non-keys, which are based on combinations of properties sharing the same values for at least two instances. Then the keys are computed from the set of non-keys. Moreover, these algorithms make use of various efficient techniques to reduce the search space of potential keys.

A closer look on the way keys are used in data interlinking shows that the two datasets considered for interlinking should rely on the same ontology or an ontology alignment has to be provided. This can be seen as a limitation that can be overcome by using link keys. Then, as this is the case for keys, link keys can be declared as logical axioms. By contrast, unlike keys, link keys can be used in data interlinking in scenarios when different ontologies are involved or when no ontology alignment is provided. Finally, an experimental comparison between the present approach based on link keys, and approaches based on keys and conditional keys, in terms of recall, precision, and F-measure, is detailed in [START_REF] Abbas | A Study of the Discovery and Redundancy of Link Keys Between Two RDF Datasets Based on Partition Pattern Structures[END_REF].

In the FCA community, a recent work dealing with data interlinking was proposed in [START_REF] Ferré | Exploring the Application of Graph-FCA to the Problem of Knowledge Graph Alignment[END_REF]. More precisely, the Graph-FCA system [START_REF] Ferré | Graph-FCA: An extension of Formal Concept Analysis to knowledge graphs[END_REF] is aimed at extending the FCA setting to deal with multi-relational or graph data. Graph-FCA can be used to discover identity links between instances as well as alignments between properties and classes. Graph-FCA and the approach presented in this paper share some commonalities, such as discovering identity links between instances in different datasets. However, the objectives of the two systems are quite different, dealing with graph data for the former and dealing with link key discovery for the latter. Nevertheless, a careful comparison of both approaches remains to be carried out.

Conclusion

In this paper, we have made precise an original research work about data interlinking based on FCA and Pattern Structures. The main objective is to discover the so-called link key candidates and the related identity link sets across two RDF datasets in the web of data. Actually, link keys are syntactic constructions based on pairs of properties and of classes that can be considered as rules allowing to infer identity links between two subjects in RDF datasets. FCA and pattern structures are well adapted to support this discovery process. FCA is used to discover link key candidates while pattern structures allow one to associate pair of classes with a link key candidate. Moreover, when the owl:sameAs relation is regarded as an equivalence relation, two link key candidates can be considered as redundant when they generate the same link sets. Then partition pattern structures allow one to study the potential redundancy of link key candidates. It appears that FCA and pattern structures are really valuable formalisms in link key discovery, and this paper demonstrates it.

Future work can be carried out in several directions. Firstly, there is a need for improving the formalization of link key discovery within the FCA and the pattern structure formalisms. In particular, more complete investigations about the relations between equality-based and similarity-based partitions, and as well the significance of redundancy remain to be done. In parallel, more experiments should be performed to support and demonstrate these theoretical aspects. Finally, another direction is to study the relations existing with link discovery in Knowledge Graphs and more generally in the web of data [START_REF] Haller | What Are Links in Linked Open Data? A Characterization and Evaluation of Links between Knowledge Graphs on the Web[END_REF][START_REF] Haller | An Analysis of Links in Wikidata[END_REF], especially link prediction [START_REF] Portisch | Knowledge graph embedding for data mining vs. knowledge graph embedding for link prediction -two sides of the same coin?[END_REF] and entity summarization [START_REF] Yang | Incremental Entity Summarization With Formal Concept Analysis[END_REF].

Example 1 .

 1 after, D denotes an RDF dataset, and (s, p, o) a triple with a subject s ∈ (U ∪ B), a predicate p ∈ U , and an object o ∈ (U ∪ B ∪ L). Then S(D) = {s | ∃ p, o (s, p, o) ∈ D} denotes the set of subject identifiers, while P (D) = {p | ∃ s, o (s, p, o) ∈ D} and the set of property identifiers. In addition, p(s) = {o | (s, p, o) ∈ D} denotes the set of objects -or values-associated with s through property p. Furthermore, N C(D) = {c ∈ U | ∃ s (s, rdf:type, c) ∈ D} denotes the set of named classes, where rdf:type stands for the instantiation link in RDF, and I N C (c) = {s | ∃ s (s, rdf:type, c) ∈ D} denotes the set of instances of a named classes c ∈ N C(D).Finally, an identity link is an RDF triple such as (a, owl:sameAs, b), stating that the IRIs a and b are referring to the same entity, or a and b are denoting the same individual. In Figure1, P(D1) and P(D2) are sets of property identifiers: P(D1) = {cAge, cFN, cLN, given, famN, date, desig, creat}, P(D2) = {pAge, pLN, pFN, first, name, year, title, auth}. NC(D1) and NC(D2) are sets of named classes over D1 and D2: NC(D1) = {Character, Woman, Scientist, Book}, NC(D2) = {Persona, FemScientist, Dictionary, Novel}.

2 Figure 1 :

 21 Figure 1: An example of two RDF datasets, with D1 on the left-hand side and D2 on the right-hand.

  a2}, I NC (Woman) = {a3, . . . , a10}, I NC (Book) = {a13, . . . , a17}, I NC (Scientist) = {a5, . . . , a12}, I NC (Persona) = {b1, b2}, I NC (Dictionary) = {b13, b14}, I NC (FemScientist) = {b5, . . . , b10}, and I NC (Novel) = {b15, b16, b17}.

Definition 4 .

 4 Let L ⊆ I(c 1 ) × I(c 2 ) be a set of links between classes c 1 and c 2 . Let us denote π 1 (L) = {a|(a, b) ∈ L} and π 2 (L) = {b|(a, b) ∈ L}.

Definition 8 (

 8 LK-pattern structure). Let D 1 and D 2 be two RDF datasets. The LK-pattern structure supporting link key candidate discovery over D 1 and D 2 is defined as the triple (S(D 1 ) × S(D 2 ), (E, ⊓), δ) where: ( i) Objects: S(D 1 ) × S(D 2 ) denotes the set of subjects pairs over D 1 and D 2 . ( ii) Descriptions and similarity operator (⊓): E denotes the set of link key expressions k = (Eq, In, (c 1 , c 2 )) over D 1 and D 2 , where c 1 ∈ C(D 1 ) and c 2 ∈ C(D 2 ).The similarity operator (⊓) is such that:

Figure 4 :

 4 Figure4: The pattern concept lattice induced from the LK-pattern structure in Table1.

Definition 10 (

 10 LK-partition pattern structure). Let D 1 and D 2 be two RDF datasets. The LK-partition pattern structure over D 1 and D 2 is defined as the triple (LKC, (P art(S(D 1 ) ∪ S(D 2 )), ⊓ part ), δ) such that: -LKC is the set of link key candidates over D 1 and D 2 computed thanks to the LK-pattern structure introduced in Section 4, -P art(S(D 1 ) ∪ S(D 2 )) is the set of partitions of the set of all subjects in D 1 and D 2 , while ⊓ part is the "meet" of two partitions, δ maps a link key candidate k to the partition P art(k) = L(k)/owl:sameAs, where L(k) is the link set generated by k.

Figure 6 :

 6 Figure 6: Variation of the number of similar pairs of partitions w.r.t. the similarity threshold.In this experiment, we do not count pairs of the same partition (P, P ) (reflexivity) and we count pairs (P 1 , P 2 ) and (P 2 , P 1 ) as only one pair (symmetry).

  [START_REF] Nentwig | A survey of current Link Discovery frameworks[END_REF] is the conjunction of the named classes to which s 1 belongs, i.e., c 1 = i∈[1,ℓ1] cl i where cl i verifies (s 1 ,rdf:type,cl i ) for i ∈ [1, ℓ 1 ],similarly, c 2 is the conjunction of the named classes to which s 2 belongs, i.e., c 2 = j∈[1,ℓ2] cl j where (s 2 ,rdf:type,cl j ) for j ∈ [1, ℓ 2 ].

  a 14 , b 13 , b 14 }, {a 15 , b 15 }, {a 16 , b 16 }, {a 17 , b 17 }} k 1b {{a 13 , a 14 , b 13 , b 14 }} k 2 {{a 13 , b 13 }, {a 14 , b 14 }} k 3 {{a 15 , a 16 , b 15 , b 16 }, {a 17 , b 17 }} k 4 {{a 15 , b 15 }, {a 16 , b 16 }, {a 17 , b 17 }} k 5 {{a 15 , a 16 , b 15 , b 16 }} k 6 {{a 15 , b 15 }, {a 16 , b 16 }} k 7 {{a 5 , b 5 }, {a 6 , b 6 }, {a 7 , b 7 }, {a 8 , b 8 }, {a 9 , b 9 }, {a 10 , a 11 , b 10 }} k 8 {{a 4 , a 5 , b 5 }, {a 6 , b 6 }, {a 7 , b 7 }, {a 8 , b 8 }, {a 9 , b 9 }, {a 10 , b 10 }} k 9 {{a 5 , b 5 }, {a 6 , b 6 }, {a 7 , b 7 }, {a 8 , b 8 }, {a 9 , b 9 }, {a 10 , b 10 }}

http://oaei.ontologymatching.org/2010/im/index.html

Acknowledgments

This work has been partially supported by the ANR project Elker (ANR-17-CE23-0007-01).