The Web of Data contains a large number of openly-available datasets covering a wide variety of topics. In order to bene t from this massive amount of open data, e.g., to add value to an organization's internal data, such external datasets must be analyzed and understood already at the basic level of data types, uniqueness, constraints, value patterns, etc. For Linked Datasets and other Web data such meta information is currently quite limited or not available at all. Data pro ling techniques are needed to compute respective statistics and meta information. Analyzing datasets along the vocabulary-de ned taxonomic hierarchies yields further insights, such as the data distribution at di erent hierarchy levels, or possible mappings betweens vocabularies or datasets. In particular, key candidates for entities are di cult to nd in light of the sparsity of property values on the Web of Data. To this end we introduce the concept of keyness and perform a comprehensive analysis of its expressiveness on multiple datasets.
and their properties. Furthermore, Linked Datasets are often inconsistent and
lack even basic metadata. One of the main reasons for this problem is that
many of the data sources, such as DBpedia or YAGO, have been extracted from
unstructured datasets and their schemata usually evolve over time. Hence it is
vital to thoroughly examine and understand each dataset, its structure, and its
properties before usage. Algorithms and tools are needed that pro le the dataset
to retrieve relevant and interesting metadata analyzing the entire dataset [
We focus on a speci c metadata aspect, namely the identi cation of objects with keys. Keys are important in many aspects of data management, such as guiding query formulation, query optimization, indexing, etc. Furthermore, for Linked Datasets key properties allow, e.g., for de ning interlinking speci cation rules to establish the underlying links as owl:sameAs that make the Web of Data a linked one.
In OWL 2 a collection of properties can be assigned as a key to a class using
the owl:hasKey statement [
Specifying or nding keys in RDF data has another dimension that distinguishes it from relational data: Ontology classes usually are arranged in a taxonomic (subclass/superclass) hierarchy. The class owl:Thing is a superclass of all OWL classes and thus, classes without an explicit superclass are direct subclasses of it. While the Web of Data spans a global distributed data graph, its ontology classes build a tree with owl:Thing as its root. Analyzing datasets along the vocabulary-de ned taxonomic hierarchies yields further insights, such as the data distribution at di erent hierarchy levels, or possible mappings between vocabularies or datasets.
Given a Linked Dataset with a set of properties, a unique property combination is a set of one or more properties whose projection has only unique entities. Our initial approach to e ciently detect keys in a given dataset regards all property combinations to nd those that together uniquely (and reliably) identify an object. Unfortunately, due to poor speci cation and data sparsity, such unique property combinations are rare. This insight leads us to the de nition of three relaxed dimensions of an RDF property: { Uniqueness is the degree to which the values of a property are unique. { Density is the degree to which a property is lled with values. { Keyness combines the two former dimensions: Properties that are highly unique and highly dense are good key candidates.
Each of these dimensions is determined at all levels of a class hierarchy, leading to insights about which properties best distinguish objects of a class and its subclasses. We evaluate the usefulness of our approach by showing various insights we gained analyzing the DBpedia and LinkedGeoData datasets. 2
A plethora of tools for pro ling Linked Datasets and gathering comprehensive
statistics, most tools focus on a speci c pro ling task. One example for the area
of schema induction is ExpLOD [
Others have worked more generally on generating statistics that describe
datasets on the Web of Data and thereby help understanding them. LODStats
computes statistical information for datasets from the Data Hub [
While there are some RDF pro ling tools already available, few tackle key
discovery. KD2R allows the automatic discovery of composite key constraints in
RDF datasets by deriving maximal non-keys and from these minimal keys [
All these existing approaches do not deliver key candidates for each and every dataset. This is where our approach is superior as it calculates the keyness for all properties.
As Linked Datasets are usually sparsely populated, minimal unique property combinations (key candidates) often consist of either multiple low-density properties or cannot be found at all. Novel property attributes, such as the uniqueness, density, and keyness of a property are needed to discover the set of properties that likely identi es an entity, the key candidates. Furthermore, since ontologies are topically clustered by their underlying ontologies, these attributes can be determined per cluster and give some detailed insights into the properties that serve as key candidates per topic. 3.1
A Linked Dataset's class hierarchy is the taxonomy de ned by its ontology and therein the rdfs:subClassOf relations between the classes. A cluster Cc for a class c consists of all the entities e that are of rdf:type c, which includes all subclasses of c.
Cc = feje rdf:typ!e cg Clusters can contain entities e that are not in any of its subclusters d. We cluster these entities separately and call the resulting clusters unspecialized clusters, denoted as C0 .
c
Cc0 = Cc n fe j e rdf:typ!e d; d rdfs:subClassO!f cg We omit the c subscript where it is irrelevant in the context. As an additional complication, properties on the Web of Data can have multiple property values. E.g., in the DBpedia dataset we nd the following four values for the property dbpedia:birthPlace for the entity of Albert Einstein: dbpedia:Albert Einstein dbpedia:birthPlace dbpedia:Ulm, dbpedia:Kingdom of Wuerttemberg, dbpedia:German Empire dbpedia:Baden-Wuerttemberg .
We denote the set of property values of an entity e and property p as V (e; p). To count the number of entities in a cluster C that have at least one value for p, we de ne V (C; p) = fe j jV (e; p)j > 0; e 2 Cg. Property values of a property p and two entities e1 and e2 are equal if V (e1; p) = V (e2; p), i.e., if the two sets are identical. With this de nition we further de ne the set of unique value sets as Vuq(C; p) = fV (e; p) j e 2 Cg.
We are now ready to de ne the three attributes, uniqueness, density, and keyness, of a property. The uniqueness uq of a property p for a cluster C is the number of unique value sets Vuq(C; p) per number of total value sets V (C; p) for the given property.
uq(C; p) = jVuq(C; p)j jV (C; p)j (1) The density d of a property p for a cluster C is the ratio of entities in C that have p to the overall number of entities in C.
d(C; p) = jV (C; p)j jCj
We call a property full key candidate if its density and uniqueness are both 1. For cases where they are not both 1 we de ne its keyness as a useful attribute. The keyness k of a property p for a cluster C is the harmonic mean of its uniqueness and density. The harmonic mean emphasizes that both parameters must be high to achieve an overall high keyness:
k(C; p) = 2 uq(C; p) d(C; p) uq(C; p) + d(C; p) We call a property key candidate if its keyness is above some threshold.
We investigate the three attributes of an RDF property, uniqueness, density, and keyness, for the given cluster types C, and C0. Determining uniqueness, density, and keyness for a property p in a cluster Cc requires analyzing all property value sets for all entities in the given cluster. We observe all kinds of speci cities of properties for clusters and their subclusters that allow for a ne-grained, cluster-based retrieval of key candidates. (2) (3) 4
Our approach has been implemented in ProLod++, a web-based tool for
proling and mining Linked Datasets [
In combination, having these property attributes at hand, the user can better decide on which properties serve as keys, especially on class level and gain further insight into the completeness and structure of the dataset at hand. 4.1
We evaluated our approach using two datasets, DBpedia v.3.9 [
For DBpedia we analyzed the Person cluster and several subclusters including Athlete and its subclusters, and Scientist (see Table 1). We deliberately omit the arti cial class Agent, subclass of owl:Thing and superclass of dbpedia:Person, due to its main function to de ne properties that are also needed for the Organization and Family class on the same class hierarchy level as Person.
Table 1 lists some subclasses of the DBpedia Person class along with the number of entities and number of properties in the respective cluster. 35% of the entities in DBpedia are persons due to Wikipedia mainly covering persons, places, and sports topics. The Person cluster is a diverse one with 255 properties being used, half of them (127) also occurring on the Athlete subclass. The Athlete class has several subclasses from which we chose representative ones. Furthermore, we included the Scientist class as a comparison in our evaluation, which has no further subclasses and only 40 properties.
This analysis shows that having some basic pro ling results on property usage at hand can already be useful. While there are 2,333 properties de ned in the DBpedia 3.9 ontology, only 1,376 are used by at least one entity. When browsing through Linked Dataset class hierarchies, the information on which properties are actually being used, compared to the de ned ones, can help to narrow down the properties of interest for tasks like key discovery.
For LinkedGeoData we analyzed the 2013 version and therein the Amenity cluster and the subclusters shown in Table 2. Due to its automatic conversion from OpenStreetMaps, which is publicly curated by a large number of people, the number of properties to describe amenities is very high.
Figure 1 plots the uniqueness and density for all properties in the DBpedia Person, Athlete, and SoccerPlayer cluster, highlighting selected properties. Overall, the property densities are noticeably low, while the uniqueness is distributed over the entire x-axis. The DBpedia Person cluster has only two properties (foaf:name and rdfs:label) with a high uniqueness (above 0.9) and density (roughly 0.7). For the subclasses there are a few more properties with a high density and uniqueness. We can already see that there is di erent behaviour in property uniqueness and density along the class hierarchy. While the uniqueness for dbpedia:birthPlace stays approximately equal for Person, Athlete, and SoccerPlayer, dbpedia:team becomes more unique for Athlete than for Person and even more unique for SoccerPlayer. The density of both properties increases.
Table 3 shows some of the 255 properties in the Person cluster along with their uniqueness, density, and keyness, ordered by keyness. What can already be observed from this selection are some typical characteristics of Linked Datasets. They often contain properties with only few property values but a high uniqueness (nearly 1), e.g., dbpedia:pseudonym. Many properties have a high uniqueness but their density is not 1, e.g., foaf:name, and rdfs:label. The density rarely reaches 0.5 (for only eight properties) and only in one of 255 properties (rdf:type) reaches 1. 86 % of the properties have only up to 5 % values available.
For example out of the 185,081 athletes in DBpedia, only 36 have a dbpedia:espnId value, yet all of these values are unique. This would identify dbpedia:espnId as a key candidate for athletes using traditional key discovery approaches. This observation emphasizes the need to take into account further details like the keyness of a property when choosing key candidates.
Figure 2 shows the uniqueness and density for all properties in the LinkedGeoData Amenity, Shop, and Bakery clusters, again highlighting selected properties. wgs84:lat is the latitude of an amenity's position. Uniqueness and density stay approximately equal for the classes along the hierarchy. The same can be observed for the label rdfs:label of entities in LinkedGeoData. Positions and labels are the two most used properties in LinkedGeoData. The overall property density is again low, which is due to the enormous mostly manual e ort to add metadata for all the 49,355,161 entities in OpenStreetMaps/LinkedGeoData.
Even more than DBpedia, LinkedGeoData is sparsely populated with property values. Table 4 shows some of the 12,371 properties in the Amenity cluster along with their uniqueness, density, and keyness, ordered by keyness. Only ve properties have a keyness above 0.8 and as we have already observed in Figure 2, the overall property density is low. Only ten properties have a density above 0.5, and two of them, dcterms:modi ed and lgd:changeset, are metadata properties. The average property uniqueness is 0.64, the average property density and keyness are 0.00. These numbers re ect the enormous number of places in LinkedGeoData and the according e ort to add metadata for all of them. 4.3
Furthermore, we evaluated the uniqueness, density, and keyness of selected properties along the class hierarchy. Table 5 shows the uniqueness, density, and keyness for the properties dbpedia:birthDate and dbpedia:team along the Person class hierarchy. As already observed in Figure 1, the keyness for dbpedia:team increases for Athlete and subclasses of Athlete as it is speci c to the sports theme but not existent for the Scientist cluster at all. The dbpedia:birthDate property has a high density for all persons but its uniqueness is naturally not very high. The coverage of athletes' birth dates starts only in the 17th century: the oldest athlete on DBpedia is a cricketer called William Bedle, born 1679.
In the Person' and Athlete' clusters only few properties are used, which explains the missing dbpedia:team property. Generally, these clusters contain entities that could not be further classi ed. When identifying key candidates, we observe that the keyness for dbpedia:birthDate is an outlier compared with the main clusters. Thus the keyness of Person and Athlete are of higher con dence. Table 6 in the appendix shows the analogous analysis for selected LinkedGeoData properties.
To summarize our ndings, we identi ed three types of property keyness along the class hierarchy: { Less speci c, i.e., keyness decreases per class level in the class hierarchy. An example is dbpedia:deathPlace whose keyness for Person is 0.18, for Athlete 0.14, and for SoccerPlayer 0.08. { Generic, i.e., keyness stays approximately equal throughout the class hierarchy. An example is dbpedia:birthPlace, whose keyness for Person is 0.28, for Athlete 0.29, and for SoccerPlayer 0.28. { More speci c, i.e., keyness increases per class level in the class hierarchy. An example is dbpedia:team which keyness for Person is 0.34, for Athlete 0.61, and for SoccerPlayer 0.93.
Figures 1 and 2 already depict these types of property keyness. In DBpedia we can nd all three types of property keyness: the keyness for dbpedia:birthPlace stays approximately equal for Person, Athlete, and SoccerPlayer (generic). For dbpedia:team the keyness increases signi cantly from Person to Athlete and nally to SoccerPlayer (more speci c). The keyness for dbpedia:deathPlace decreases along the class hierarchy to SoccerPlayer (less speci c). This can be explained with the fact that DBpedia is an ever-evolving knowledge base and at the time of writing most death places covered for soccer players were in a certain town in England, namely Stoke-on-Trent. In LinkedGeoData the properties' keyness is mostly generic, like rdfs:label and wgs84:lat, but also sometimes gets more speci c on the lower class hierarchy levels.
Finally, Figure 3 shows the keyness distribution for all properties along the DBpedia class hierarchy. Class level 1 contains all properties of owl:Thing, level 2 all properties of subclasses of owl:Thing and so forth. Overall, the keyness is increasing per class level. For the root class level 1 out of 1,376 properties only one has a keyness higher than 0.8, for class level 7 this increases to 7 out of 22 properties. This observation leads to the conclusion that class level-based keys are a better choice than high-level keys. Key features for athletes might be too high-level for soccer players and should be rede ned on that level.
Our evaluation shows that the property keyness can help discovering key candidates for Linked Datasets. It also highlights the advantages of analyzing the class hierarchy in order to observe property behaviour for classes along it and make better choices when identifying key candidates for speci c classes. 5
We have introduced the concept of keyness (and therein uniqueness and density) of a property to address the sparsity on the Web of Data and thus create the possibility to nd key candidates where traditional approaches fail.
Our approach has been implemented in ProLod++ and provides users with the uniqueness, density, and keyness for all properties. Having these pro ling results at hand helps users in nding key candidates and analyzing the relevance of properties along class hierarchies in Linked Datasets.
While the keyness of a property is already useful for discovering key candidates, the keyness values rarely reach 0.8 due to dataset sparsity. Thus we plan to extend the keyness concept to sets of properties. Because minimal unique property combinations rely only on a high combined density, they are not the ideal approach here. It seems reasonable, for instance, to consider the amount of overlap of properties in combination with the properties' keyness.
In analogy to Table 5 for persons, Table 6 shows the uniqueness, density, and keyness for the selected LinkedGeoData properties wgs84:lat and rdfs:label along the Amenity class hierarchy. For the position properties it is noticeable that the keyness stays high (above 0.79) for all the classes along the hierarchy. The fewer the entities in the class cluster (butchers and ice cream shops), the higher the property keyness. For the label the keyness also is quite stable along the class hierarchy (around 0.6) but is especially high in bakeries due to the uniqueness in labels and a high density.