dataesr/scientific-paragraphs-categorization huggingface dataset:
Additionally, data may be incomplete and depending on how the absence of some property values is interpreted, it has led to consider different key semantics. [17, 23, 24, 4]  consider the OWL2 semantics  [26] : in order to infer an identity link between two instances, it suffices that these instances share at least one value for each property involved in the key (e. g. , if the property email is considered as a key for the class person, a shared email address is sufficient to decide that two people are the same). Thus, a set of properties is considered to be a key under this semantic, if there exist no instances in the dataset sharing at least one value per property in the key. Keys discovered under this semantic are called S-keys. Unlike  [17, 23, 24, 4] , in  [5, 22]  two instances have to share all the values for each property involved in the key to be considered identical (e.
g. , if the property email is considered as a key, the sets of emails must be equal to decide that two people are the same). Thus, a set of properties is considered to be a key under this semantic, if there exist no instances in the dataset sharing the same set of values for all properties in the key. While  [17, 23, 24, 4, 5]  consider that two instances can be compared using only the values appearing in the data,  [22]  introduces a new interpretation for the absence of values. More precisely, considering a set of properties as a key, two instances are identical for  [22]  if for every property in the key they either have the exact same set of values or they both have no value provided in the data. Keys under the semantic proposed in  [22]  are called F-keys while under the semantic proposed in  [5]  are called SF-keys.
A theoretical study of S-keys and F-keys along with a preliminary experimental comparison of S-keys, F-keys and SF-keys has been proposed in  [3]. This first comparative study has shown that when the discovered keys are used to link RDF datasets, the results can vary depending on the dataset and the studied class. However, the evaluation of the approaches has been conducted on a very limited number of classes and has not provided insights on when each semantic is more appropriate to use. Key discovery strategies in RDF data. The number of candidate keys for a given class is exponential w. r. t. the number of properties used to describe the data of that class. Therefore, different strategies and heuristics have been proposed to optimize both the time and the space complexity of key discovery.
Approaches can be roughly classified in two categories, the ones discovering keys directly and the ones discovering first non keys (i. e. , sets of properties that are not keys) and then using them to derive keys. In the first category, all approaches exploit the monotonic characteristic of keys to prune the search space. In  [21] , discriminating data type properties (i. e. , approximate keys) are discovered from a dataset to develop a data linking blocking method. Keys of a specific size are explored only if there is no smaller key with a high discriminative power. These approximate keys are then exploited to construct blocks of instances. In this work, the aim is not to learn the complete set of minimal keys, but to discover a set of properties that can be used to partition the data efficiently.
Therefore, no additional optimisation strategies are addressed. In  [5] , the authors introduce a bottomup approach based on TANE  [13] , to discover pseudokeys (keys with exceptions). In order to improve the scalability of the approach, the authors discover explore combinations of properties that are highly instantiated. In ROCKER  [22] , the authors propose a more sophisticated bottom-up approach based on a refinement oper- ator allowing to efficiently discover pseudo-keys. As  [5] ,  [22]  also filter the search space using highly instantiated sets of properties. However, the key discovery tool provided in this work, used in the experimental evaluation, in some cases fails to compute the complete set of minimal keys as expected (i. e. , some of the discovered keys are not minimal and some valid keys are not discovered) (see https://github.
com/danaiS/ BECKEY/tree/master/Annexe/OtherTools for an example). To avoid scanning all the data, some approaches  [17, 23]  extend  [20]  proposed in the context of relation databases. This approach discovers the complete set of maximal non keys first and uses them to derive minimal keys. Such approaches exploit the antimonotonic characteristic of non keys to prune the search space. KD2R  [17]  is based on a prefix tree structure to store the data but can be overwhelmed by large datasets. Indeed, deriving keys from non keys is a time consuming step for such approaches. Furthermore, this approach requires datasets that fulfill the Unique Name Assumption to discover keys that are valid in all the dataset (i. e. , no exceptions allowed). SAKey  [23]  discovers almost keys in large datasets that may contain errors or duplicates.
Keys for data linking The goal of this section is to present and illustrate the different semantics of keys existing in the Semantic Web. To do so, we introduce the notations that will assist with the formalisation of a uniform framework for key discovery in RDF datasets. We first present the data model. Then we provide three definitions of keys that have been envisaged for data linking before introducing the inclusion relationships between these definitions. At the end of this section, we introduce the common struc-tures and definitions that will be re-used for discovering these keys.
Data Model In this work we consider a knowledge base as a set of instances I (e. g. , a specific person referred as i1), a set of literals L, a set of properties P (e. g. , FirstName), and a set of classes C (e. g. , University). Statements of instances in a knowledge base are usually represented as triples < s, p, o > where subject s ∈ C ∪ I, property p ∈ P, and object o ∈ C ∪ I ∪ L, which we write as p(s, o). Every instance is typically associated to one or more classes by the type property, and these classes can be arranged in a hierarchy by the subclassOf property. A set of such statements constitutes a knowledge base (KB) 1. Given a KB K, an RDF dataset D for a class c of K is the set of all statements that have as subject an instance of c or of a subclass of c. Table  1  shows an example dataset about people i1,.
Understanding and comparing key semantics General concept of a key. A key represents a set of properties that uniquely identifies resources stored in a dataset. The three semantics of keys proposed in the context of Semantic Web i. e. , S-key  [23] , F-key  [22]  and SF-key  [5]  also converge to define a key as a set of properties that uniquely identifies an instance. However, these semantics diverge on when to consider that the set of values, associated to an instance and a given set of properties, is unique. The S-key semantic assumes data incompleteness and only considers a set of properties as a key if there exist no instances sharing a value for the given set of properties. The SF-key semantic assumes data completeness and considers a set of properties as a key if there exist no instances having the exact same set of values for the given set of properties.
More precisely, owl:hasKey(c(ope 1 ,. , ope m ) (d pe 1 ,. , d pe n )) states that each instance of the class c is uniquely identified by the object property expressions ope i and the data property expressions d pe j. An object property expression is either an object property or an inverse object property. The semantic of the construct owl:hasKey is defined in  [26]   3. F-key and SF-key have different semantics. Both definitions consider that property values are completely known for all instances of a given dataset. Indeed, it can be also meaningful to consider that the instances should coincide for all property values (e. g. , a list of authors of a given paper, or the list of universities a person has studied in). Keys following this semantic are referred as F-keys or SF-keys depending on how empty values are considered.
Moreover, this definition allows two instances to refer to the same real world object even the set of values associated to some or all of the properties expressed in F-key is empty. Implicitly in this definition the absence of values for a property is treated as an "known no value" rather than "possibly missing values" for a property. This hypothesis may appear to be too permissive to identify identical instances of real world datasets. The next definition of SF-key overcomes this issue. An SF-key can be viewed as a specific type of F-key that requires two instances to be considered as identical when they share similar non empty set values for each properties declared in the SF-key. Keys under the SFkey semantic are discovered in  [5]. More formally we have: Definition 3 (SF-key). Let P = {p 1 ,.
Key discovery under different semantics Data on the Web are describing instances of different classes using numerous properties. In this context, keys that can be exploited for data linking are hidden and cannot easily be specified even by a human expert. Therefore, automatic methods are needed to discover them from the data. When the Unique Name Assumption (UNA) is fulfilled, a set of properties can be considered as a valid key in a dataset if every instance can be uniquely identified using the values of this set of properties. Thus, keys can first be discovered in each data source and then merged according to a merging method that computes keys that are valid in all the datasets  [17]  or that rank and select keys based on quality measures  [8]. In this paper, we focus on the key discovery processes that can be defined for one dataset.
Keys with exceptions. RDF datasets may contain erroneous data and duplicates. Thus, discovering keys in RDF datasets without taking into account these data characteristics may lead to lose keys. Furthermore, there exist sets of properties that even if they are not keys, due to a small number of shared values, they can Relations S-Links = F-Links = SF-Links F-Links = SF-Links SF-Links ⊆ S-Links F-Links ⊆ S-Links SF-Links = S-Links SF-Links ⊆ F-Links S-Links ⊆ F-Links SF-Links ⊆ S-Links SF-Links ⊆ F-Links In this work we will refer to keys with exceptions as n-almost keys, first used in  [23]. A set of properties is a n-almost key if there exist at most n instances that share values for this set of properties. However, the different key semantics lead to different definitions of the notion of exception.
P is a n-almost Skey(resp. F-key, SF-key ) if |E S ,P | (resp. |E F,P |, |E S F,P |) ≤ n. This means that a set of properties is considered as a nalmost key, if there exist from 1 to n exceptions in the dataset for this set of properties. For example, in D1, for the class Person, {LastName, S tudiedIn} is a 3-almost S-key {i1, i2, i7}, a 4-almost F-key {i1, i7, i3, i8}, and a 2-almost SF-key {i1, i7}. By definition, if a set of properties P is a n-almost key, every superset of P is also a n-almost key. We are interested in discovering only minimal n-almost keys, i. e. , n-almost keys that do not contain subsets of properties that are n-almost keys for a fixed n. Support. The discovered keys can be valid for a number of class instances that can be few, compared to the total number of class instances described in the dataset.
Inclusion relations for key discovery Relations between S-key and F-key sets discovered in a given dataset have been initially presented in  [3]. These relations vary depending on the characteristics of the dataset used to discover keys. Table  3  summarises these relations and extends them with the case of SF-keys. Note that, Table  3  uses S-keys (resp. SF-keys, F-keys) to refer to the complete set of keys discovered in a dataset under the S-key (resp. SF-key, F-key) semantic. Considering a dataset where no multivaluation and no empty values occur, the sets of keys discovered under the three semantics are the same. When this is not the case, different relations of inclusion appear. In the case where the multivaluation is present and all the properties are instantiated for all instances in the data, the sets of SF-keys and F-keys are identical while all the S-keys are also keys under both F-key and SF-key semantics.
Discovery of n-almost keys from n-non keys In order to check if a set of properties is a n-almost key for a class c in a dataset D, a naive approach would scan all the instances of a class c to verify if at most n instances share values for these properties. Even when a class is described by few properties, the number of candidate n-almost keys can be huge. For example, if we consider a class c that is described by 60 properties and we aim to discover all the n-almost keys that are composed of at most 5 properties, the number of candidate n-almost keys that should be checked will be more than 6 million. An efficient way to obtain n-almost keys, as already proposed in  [20, 17] , is to discover first all the sets of properties that are not n-almost keys and use them to derive the n-almost keys.
Indeed, to show that a set of properties is not a n-almost key, it is sufficient to find only (n+1) instances that share values for this set. We call the sets that are not n-almost keys, n-non keys. Definition 12. (n-non key). Let P be a set of properties (P ⊆ P) and n an integer. P is a n-non key if |E P | ≥ n. Note that, every subset of P is also a n-non key since the dataset also contains n exceptions for this subset. We are interested in discovering only maximal n-non keys, i. e. , n-non keys that are not subsets of other n-non keys for a fixed n.
We illustrate in Tables 4, 5 and 6 the propertyexception maps corresponding to the dataset D1 (see Table  1 ). These property-exception maps are going to be used for discovering respectively S, SF, and F n-non keys. Similarly, p1, p6 and p7 have all studied in Stanford, thus they represent another property-exception set w. r. t. the S-key semantic. Note that the people p2 and p5 have both studied in UCD. However, they do not appear as a property-exception set for the property Stud-iedIn. This property-exception set is subsumed by the set {p1, p2, p5, p7} containing people that have studied in UCC. Indeed, all non keys that can be discovered using the property-exception set {p2, p5} will be discovered by the property-exception set {p1, p2, p5, p7}.
FirstName Table  5  shows the property-exception map computed from the dataset D1 that is used for discovering SFkeys when n=2. In this map, the individuals p1 and p7 have both studied in the exact same universities, i. e. , UCC and Stanford. These two individuals represent a property-exception set that prevents StudiedIn to be considered as an SF-key. Note that the property HasSibling does not appear in the map since it corresponds to a minimal 1-almost SF-key. Table  6  shows the property-exception map computed from the dataset D1 that is used for discovering Fkeys when n=2. For all properties, each propertyexception set w. r. t. SF-key semantic also appears as a property-exception set w. r. t. F-key semantic. In addition, a property-exception map w. r. t. F-key semantic contains property-exception sets for which instances map to missing values.
Construction of shared exception graph The goal of n-non key search is to extend propertyexception sets valid for one property to a set of properties in order to discover maximal n-non keys. In some datasets the properties are numerous, and the number of candidate n-non keys, which is exponential in the number of properties, may be intractable. This is why we need a n-non key search mechanism that will avoid exploring irrelevant combinations of properties. For example, in the DBpedia dataset, the properties depth and mountainRange are never used to describe the same instances of the class NaturalPlace. Indeed, depth is used to describe natural places that are lakes while moun-tainRange natural places that are mountains. Therefore, depth and mountainRange cannot participate together in a n-non key.
In addition, to efficiently lead the search for n-non keys, the relation < establishes a total order and prioritises the properties that will be explored first. Figure  1  shows the shared exception graph corresponding to the dataset D1 w. r. t. S-key semantic when the number of exceptions is set to 2, i. e. , n=2. Within the graph, the set of properties {FirstName, LastName, SSN} forms a clique. Therefore, the search space is pruned since no n-non keys including the set {First-Name, LastName, SSN} should be explored. Figures  2  and 3  show the shared exception graph for the SF-key and F-key semantics when n=2. Note that in this approach, unlike SAKey  [23] , it is not necessary to pre- compute the set of all cliques associated to a propertyexception map since it can be very time consuming on datasets with numerous properties.
The algorithm stops when the exploration reaches a maximal clique in G or when the next non key to be composed is already included in one of discovered non keys (lines 1-3). If the algorithm is launched with n=2 (i. e. , at least 2 exceptions authorised) in the dataset D1 presented in the Table  1 , then: 2-S non keys = {{FirstName, LastName, DateOfBirth, StudiedIn, HasSibling}, {FirstName, LastName, SSN}} under the S-key semantic, 2-SF non keys ={{FirstName, LastName, StudiedIn}, {FirstName, LastName, SSN}} under the SF-key semantic and 2-F non keys ={{FirstName, LastName, SSN, DateOf-Birth, StudiedIn, HasSibling}} under the F-key semantic.
13 J o u n a l r e -r o f of the same knowledge base that evolves over time. In the first set of experiments two different versions of DBpedia are compared. This scenario uses BECKEY as a solution for tackling the temporal evolution of a given dataset. In the second real-world scenario, we evaluate the capability of the three semantics to discover the correct owl:SameAs links among the instances of two different knowledge bases built separately, conforming to different ontologies. In the second set of experiments, one version of DBpedia is linked to one version of YAGO  5. This scenario uses BECKEY as a solution for tackling the heterogeneity of knowledge bases. For both scenarios the objective of the experiments is twofold: compare the different key semantics through the quality of the links inferred and understand in which case a key semantic may be more suitable for data linking than another.
To this aim, for all semantics of keys, the data linking step is computed as follows. Given two datasets containing instances of the same class, the keys discovered by each semantic are applied to provide owl:sameAs links among the instances of the two datasets. No similarity measures are applied even if  [23]  has shown that similarity measure may positively impact the computed scores. This simple data linking step allow us to have a fair comparison of the different key semantics and have a clearer understanding of the cases where a specific key semantic may be more suitable. Setting. In all experiments, the data are stored in a dictionary-encoded map, where each distinct string appearing in a triple is represented by an integer. The experiments have been executed on a single machine with 16GB RAM, processor 2.
Linking data of evolving Knowledge Bases In this first set of experiments, we compare the quality of the three different key semantics for linking two versions of a same knowledge base that evolved over time (see Section 5. 1. 1). In Section 5. 1. 2, we demonstrate the impact of exceptions in the data linking process for all three semantics. Datasets. The experiment is executed on 2 different versions of DBpedia, the latest version published in October 2016  6  (DBpedia 2016) and a previous version published in 2013  7  (DBpedia 2013). The selected datasets are highly heterogeneous as shown in this section, and allow a comparison of the three key semantics when data evolve through time (i. e. , instances, properties and property values are added or suppressed). 266 DBpedia classes are randomly chosen for the experimental evaluation.
Since the three key semantics differ on the hypothesis on data completeness, such an evolutive dataset is used to compare the three approaches. To compare the results of different semantics of keys on significant classes, we select the classes for which at least one set of keys discovered for a given semantic and a given number of exceptions (among 0, 10, 20, 30) returns an FMeasure equal or higher than 60. 155 classes correspond to this criteria. Therefore, our experiments focus on these 155 classes. These classes contain from 100 to more than 200. 000 instances (see Figure  4 ), from 419 to 1. 611. 241 triples (see Figure  5 ) and finally from 7 to 462 properties (see Figure  6 ). The classes in all three figures are sorted according to their number of instances, triples and properties respectively.
Data linking challenge. The objective of this experiment is to compare the linking performance of key based approaches on the problem of data linking. To this aim, we compare the links found among instances of a given class described by two datasets, i. e. , db2013 and db2016. Table  7  shows the evolution of the data with respect to the two versions of DBpedia. More precisely, as shown in this   In this first set of experiments we focus on keys with 0 exceptions. More precisely, we provide the linking results of all three key semantics in the selected classes and an analysis on which semantic is more appropriate to use depending on the nature of the data. For each class, and each key semantic, the keys discovered in the most recent version of DBpedia (db2016) are used to identify the common instances between the two datasets (db2013 and db2016).
We consider the newest dataset as a knowledge base that is more complete and contains less errors than the previous versions. Figure  7  shows the Recall obtained by each semantic, for each class. In the x-axis, classes are ordered by the overall Recall, i. e. , the sum of Recall scores returned for  the three semantics of keys. S-keys and SF-keys lead to relatively similar Recall scores. As it can be easily observed, Recall scores are uniformly distributed among the classes. S-keys and SF-keys lead to Recall scores from 0 up to 99% depending on the tested class. In the case of low Recall, this is usually due to the data incompleteness on the properties participating in the keys. For example, in the case of the class HollywoodCartoon we obtain a very low Recall using S-keys or SFkeys (lower than 1%).
The S-key (resp. SF-key) with the highest support is the IMDB-ID of the Hollywood cartoon. However, only 139 instances out of 1258 participating in the goldstandard are containing information about their imdb-id in the version db2016 while none of the instances of the version db2013 contains this property. This means that this key leads to zero links. All the other keys discovered of this class have a very low support. For example the key {Homepage}, a key that seems to be relevant for the data linking task, is filled for only one Hollywood cartoon in the db2016 version. Nevertheless, Figure  7  shows that both S-keys and SFkeys bring very good Recall scores for numerous classes (more than 50 classes obtain a Recall higher than 70%). The Recall obtained for F-keys is equal to 0 for 117 of the 155 classes since no F-keys are discovered for these classes (see Table  8 ).