The amount of Linked Open Data available on the Web is rapidly growing. The quality of the provided data, however, is generally-speaking not fundamentally improving, hampering its wide-scale deployment for many real-world applications. A key data quality aspect for Linked Open Data can be expressed in terms of its adherence to an underlying wellde ned schema or ontology, which serves both as a documentation for the end-users as well as a xed reference for automated processing over the data. In this paper, we rst report on an analysis of the schema adherence of domains and ranges for Linked Open Data. We then propose new techniques to improve the correctness of domains and ranges by i) identifying the cases in which a property is used in the data with several di erent semantics, and ii) resolving them by updating the underlying schema and/or by modifying the data without compromising its retro-compatibility. We experimentally show the validity of our methods through an empirical evaluation over DBpedia by creating expert judgements of the proposed xes over a sample of the data.
Linked Open Data (LOD) is rapidly growing in terms of the number of available datasets moving from 295 available datasets in 2011 to 1'014 datasets in 20141. As we report in Section 2, LOD quality has already been analyzed from different angles; one key LOD quality issue is the fact that the data does not always adhere to its corresponding schema, as we discuss in more detail in Section 3. That is, factual statements (i.e., RDF triples) do not always follow the de nitions given in the related RDF Schemas or ontologies. Having a schema which the published data adheres to allows for better parsing, automated processing, reasoning, or anomaly detection over the data. Also, it serves as a de facto documentation for the end-users querying the LOD datasets, fostering an easier deployment of Linked Data in practice.
To mitigate the issues related to the non-conformity of the
data, statistical methods for inducing the schema over the
data have been proposed. Voelker et al. [
In this work, we focus on one particular issue of LOD schema adherence: the proper de nition of the properties' domains and ranges in LOD. More precisely, we propose (see Section 4) a new data-driven technique that amends both the schema and the instance data in order to assign better domains and ranges to properties; this goal is achieved by detecting the cases through which a property is used for di erent purposes (i.e., with di erent semantics) and by disambiguating its di erent uses by dynamically creating new sub-properties extending the original property. Thus, our approach modi es both the schema (new sub-properties are created) and the data (occurrences of the original property that were used with some given semantics are replaced with the newly created sub-property). One of the interesting properties of our approach is that the modi ed data is retrocompatible, that is, a query made over the original version of the data can be posed as is over the amended version.
We evaluate our methods in Section 5 by rst comparing how much data it can x by adjusting di erent parameters, and then by asking Semantic Web experts to judge the quality of the modi cations suggested by our approach. 2.
One of the most comprehensive piece of work describing
LOD is the article by Schmachtenberg et al. [
Data quality is a thoroughly-studied area in the context of
companies [
There is also a vast literature ( [
The motivation that led us to the research we are presenting is summarized in Table 1. Its upper part reports the top-5 properties in DBpedia2 and Freebase3 The table reports on the number of times the properties appear with a wrong domain, together with their Wrong Domain Rate (WDR), that is, the ratio between the number of times the property is used with a wrong domain to its total number of uses. Analogously, the lower part of the table reports on the top-5 properties by number of range violations and their Wrong Range Rate (WRR).4 We observe that the absolute number of occurrences of wrong domains/ranges in Freebase is two orders of magnitude greater than that of DBpedia. This cannot be explained only by the di erent number of entities contained in the two knowledge bases since the number of topics covered by Freebase is only one order of magnitude greater than that of DBpedia (approximately 47:43 and 4:58 million topics, respectively, according to their Web-pages). We deduce that in Freebase the data adheres to the schema less than in DBpedia. This 2We used the English version of DBpedia 2014 (http:// dbpedia.org/Downloads2014). 3 We used a dump downloaded on March 30th 2014 (http: //freebase.com). 4When computing WDR and WRR we do take into account the type hierarchy for computing the violation rate. That is, if a property has `Actor' as range and is used in a RDF triple where the object is an `American Actor' we consider it as correct as `American Actor' is a subtype of `Actor'. is also suggested by the fact that the top-3 most frequent properties de ned in the DBpedia ontology, namely dpo:birthPlace, dpo:birthYear, and birthDate, have WDR and WRR smaller than 0:01, while the top-3 most used property in Freebase, namely fb:type.object.type, fb:type.type.instance, and fb:type.object.key, have an average WDR of 0:30 and an average WRR of 0:87. This disparity can in part be explained by the fact that the Freebase ontology is a forest of trees rather than a tree with a single root note (as in DBpedia). Thus, while one could expect that each entity in the dataset should descend from `object', this is not the case when looking at the data. In addition, we noticed that in DBpedia, out of the 1'368 properties actually used in the data, 1'109 have a domain declaration in the ontology and 1'181 have a range declaration. Conversely, Freebase speci es domain and range of 65'019 properties but only 18'841 properties are used in the data.
In this paper we argue that a number of occurrences of wrong domains or ranges are due to the fact that the same property is used in di erent contexts, thus with di erent semantics. The property dpo:gender, for example, whose domain is not speci ed in the DBpedia ontology, is used both to indicate the gender of a given person and the gender of a school (that is, if it accepts only boys, girls or both). Hence, dpo:gender appears both in the context of dpo:GivenName and of dpo:School. While this can make sense in spoken language, we believe that the two cases should be distinct in a knowledge base. However, we cannot make a general rule out of this sole example as, for instance, we have that foaf:name (whose domain is not de ned in the DBpedia ontology) is attached to 25 direct subtypes of owl:Thing out of 33; these types include dpo:Agent (the parent of dpo:Person and dpo:Organization), dpo:Event, and dpo:Place. In this case, it does not make sense to claim that all these occurrences represent di erent contexts in which the property appears, since the right domain for this case is indeed owl:Thing, as speci ed by the FOAF Vocabulary Speci cation.5 Moreover, in this case creating a new property for each subtype would lead to an overcomplicated schema. Finally, the fact that dpo:name is not attached to all the subtypes of owl:Thing suggests that the property is optional.
What follows describes the intuition given by this example in terms of statistics computed on the knowledge base. In addition, we also present algorithms to identify the use of properties in di erent contexts. 4.
In this section, we describe in detail the algorithm we propose, namely, LeRiXt (LEft and RIght conteXT). For the sake of presentation, we rst describe a simpler version of the method we call LeXt (LEft conteXT) that uses the types of the entities appearing as subjects of the property in order to identify properties that are used in di erent contexts (multi-context properties). We then present the full algorithm as an extension of this simpler version. For the description of the algorithm, we make use of the notation de ned in Table 2. 4.1
5http://xmlns.com/foaf/spec/.
dpo:years dpo:currentMember dpo:class dpo:managerClub dpo:address
dpo:starring dpo:associatedMusicalArtist dpo:instrument dpo:city dpo:hometown
LeXt makes use of two main statistics: Pr(tL j p), that is, the conditional probability of nding an entity of type t as the subject of a triple having p as predicate (i.e., nding t \to the Left" of p), and the probability Pr(p j tL), that is, the probability of seeing a property p given a triple whose subject is an instance of t. Equation 1 formally de nes those two probabilities.
Pr(tL j p) = j f (s; p0; o) 2 KB j s a t; p = p0 g j
j f (s; p0; o) 2 KB j p = p0 g j Pr(p j tL) = j f (s; p0; o) 2 KB j s a t; p = p0 g j j f (s; p0; o) 2 KB j s 2 t g j (1) As one can imagine, Pr(tL j p) = 1 indicates that t is a suitable domain for p, however, t can be very generic. In particular Pr(>L j p) = 1 for every property p where > is the root of the type hierarchy. Conversely, Pr(p j tL) measures how common a property is among the instances of a certain type. Pr(p j tL) = 1 suggests that the property is mandatory for t's instances. In addition, whenever we have strong indicators that a property is mandatory for many children ti of a given type t, that is, Pr(p j tiL) is close to 1 for all tis, we can deduce that t is a reasonable domain for p and that all the ti are using p as an inherited (possibly optional) property. For example, if in DBpedia we consider the property foaf:name p02P and we analyze Pr(p j tiL) for all ti 2 Ch(owl:Thing) we see that the probability is greater than 0 in 25 cases out of 33 and is greater than 0:50 in 18 cases, suggesting that all the tis do not constitute uses of the properties in other contexts but rather that the properties are used in the more general context identi ed by owl:Thing.
Computationally, we only need to maintain one value for each property p and for each type t, that is the number #(p ^ tL) of triples having as subject an instance of t and p as predicate. In fact, if we assume that whenever there is a triple stating that (e; a ; t) 2 KB there is also a triple (e; a ; t0) 2 KB for each ancestor t0 of t in the type hierarchy, we have that 8p 2 P:j (s; p0; o) 2 KB j p = p0 j = #(p ^ >L); 8p 2 P:j (s; p0; o) 2 KB j s 2 t j = X #(p0 ^ tL): The computation of all the #(p ^ tL) can be done with one map/reduce job similar to the well-known word-count example often used to show how the paradigm works, thus, it can be e ciently computed in a distributed environment allowing the algorithms we propose to scale to large amounts of data. Another interesting property implied by the type subsumptions of the underlying type hierarchy is that if t1 2 Ch(t0) then Pr(t1L j p) Pr(t0L j p). Assuming the same L premises, however, nothing can be said about Pr(p j t0 ) and Pr(p j t1L). 4.2
As previously anticipated, LeXt detects multi-context properties by exploiting the types of the entities found on the left-hand side of the property taken into consideration. Speci cally, given a property p, the algorithm makes a depth- rst search of the type hierarchy starting from the root to nd all cases for which there is enough evidence that the property is used with a di erent context. Practically, at each step, a type t|the current root of the tree|is analyzed and all the ti 2 Ch(t) having Pr(tiL j p) greater than a certain threshold are considered. If there is no such child, or if we are in a case similar to that of the foaf:name example described previously, a new sub-property t p of p is created with t as domain; otherwise the method is recursively called on each ti. Finally, cases analogous to the foaf:name example are H = 0.09
...
SportsTeamSeason0.55 ...
...
Organisation0.44 SoccerClubSeason0.55 ...
SportsTeam0.44 ...
H = 1.96
Soccer0.42 Baseball"1 ... Crick e"kt1 Rugb y"k detected by using the entropy of the probabilities Pr(p j tiD) with ti 2 Ch(t) that captures the intuition presented while introducing the above mentioned statistics. Since, in general, Pti2Cht Pr(p j tiL) 6= 1, we normalize each probability by dividing it by Z = P compute the entropy H using Equation 2t.i2Ch(t) ti and we H p j Ch(t) =
X ti2Ch(t)
Pr(p j ti)
Z log2
Pr(p j ti)
Z (2)
Algorithm 1 formally describes the full process. In the pseudo-code, a context of the input property is encoded with a triple (p0; dom(p0); coverage) where p0 is a property identifying the context, dom(p0) is its domain, and coverage is the rate of the occurrences of p covered by the context, denoted by Cov(p0). If the coverage is one, p is used in just one context (see Line 5). In Line 8, a new property p0 is created and its domain is set to curr root , while in Line 9, p0 is declared to be a sub-property of p: this makes the data retro-compatible under the assumption that the clients can resolve sub-properties. Ideally, after the execution of the algorithm, all the triples referring to the identi ed meanings should be updated. The algorithm can also be used to obtain hints on how to improve the knowledge base.
The execution steps of the algorithm on dpo:manager (m, for short) with = 0:4 and = 1 are depicted in Figure 1. The entity types are organized according to the DBpedia type hierarchy and each type t is subscripted by Pr(t j m). As can be observed, during the rst step the children of owl:Thing are analyzed: the entropy constraint is satis ed and two nodes satisfy the Pr(t j m) constraint. The exploration of the dpo:sportsSeason branch ends when dpo:SoccerClubSeason is reached. The triple (SoccerClubSeason manager, dpo:SoccerClubSeason, 0.55) is returned. The new property is a sub-property of dpo:manager that covers 55% of the occurrences. Finally, the algorithm goes down the other branch until the entropy constraint is violated and returns the context (SportsTeam manager, dpo:SportsTeam, 0:45). 4.3
The threshold sets a condition on the minimum degree of evidence we need to state that we have identi ed a new meaning for p, expressed in term of the Pr(t j p) probability. This threshold is of key importance in practice. On the one hand, low thresholds require little evidence and thus foster the creation of new properties, possibly over-populating the schema. On the other hand, high thresholds almost never accept a new meaning of a property, thus inferring coarser domains. In particular, with = 1 the exact domain of p is inferred (which in several cases can result to be >). In Algorithm 1 LeXt Section 5 we show how the algorithm behaves with varying levels of strictness.
The presented algorithm has a number of limitations. In particular, it does not explicitly cover the cases for which one type has more than one parent, thus multi-inheriting from several other types. In that case, an entity type can be processed several times (at most once per parent). We leave to future work studying if simply making sure that each node is processed once is enough to cover that case.
It is straightforward to de ne a variant of LeXt that considers property ranges instead of property domains by using Pr(tR j p) and Pr(p j tR). We call this method ReXt. In our implementation we only consider object properties, that is, properties that connect an entity to another entity (rather than, for example, to a literal since these values are not entities and thus are not in the type hierarchy).
Generalizing LeXt to identify multi-context properties based on both domains and ranges is a more complicated task. The solution we propose is called LeRiXt and consists in using two copies of the type hierarchy, one for the domains, and one for the ranges. At each step there is a \current domain" td and a \current range" tr whose children are analyzed (thus the algorithm takes one more parameter than LeXt). Instead of using the condition Pr(tD j p) to select the candidate types to explore, we use Pr(tiD ^ tjR j p) for each ti 2 Ch(td); tj 2 Ch(tr), and we recursively call LeRiXt for each pair of types satisfying the constraint (see Line 14 of Algorithm 1).
We empirically evaluate the three methods described in Section 4, namely, LeXt, ReXt, and LeRiXt, rst by studying how they behave when varying the threshold , and then by measuring the precision of the modi cations they suggest. The LOD dataset we selected for our evaluation is DBpedia 2014 since its entity types are organized in a well-speci ed tree, contrary to Freebase, whose type system is a forest. As we anticipated in Section 4.4, we consider only object properties when the range is used to identify multi-context properties by using ReXt and LeRiXt. The # 0 0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0
Threshold Value numbers of properties we take into consideration when running LeXt and the other two algorithms are 1'368 and 643, respectively. Finally, during our experimentation we x the threshold to 1. This value was chosen based on the analysis of the entropy stopping criterion on a small subset of properties.
The impact of on the output of the algorithms is studied in terms of average property coverage and number of generated sub-poperties. Recall that in Section 4.2 we de ned the coverage of a sub-property. Here we measure the property coverage, de ned as the overall rate of occurrences of a certain property p that is covered by its sub-properties, that is, the sum of Cov(p0) for all p0 generated sub-property of p.
In the upper part of Figure 2 the average over the property coverage is shown for various . We notice that, as expected, lower values of lead to a high coverage since many new properties covering small parts of the data are created. As the value of the threshold increases, fewer and fewer properties are created, reaching the minimum at = 1. Interestingly, we observe that the average coverage curve is M-shaped with a local minimum at = 0:5. That is the consequence of the fact that with 0:5 the new properties are required to cover at least half of the occurrences of the original property, leaving no space for other contexts, thus, at most one new context can be identi ed for each property. Finally, at = 1 the average coverage drops to 0 since no sub-property can cover all the instances of the original property.
In order to evaluate the output produced by the methods, 3 authors and 2 external experts evaluated the output of the algorithms computed on a sample of fty randomly selected DBpedia properties using = 0:1 and = 1. To decide whether the context separation proposed by the algorithm is correct or not, we built a web application showing to the judges the clickable URI of the original property together with the types of the entities it appears with. The judges had then to express their opinion on every generated subproperty.
The judgments were aggregated by majority vote and then precision was computed by dividing the number of positive judgments by the number of all judgments. LeXt, ReXt, and LeRiXt achieved a precision of 96:50%, 91:40%, and 87:00%, respectively.
We note that this result was obtained with just one conguration of the parameters|we leave a deeper evaluation of the algorithm as future work.
In practice, we envision our algorithms to be used as a decision-support tool for LOD curators rather than a fully automatic system to x LOD datasets. 6.
In this paper, we tackled the problem of extracting and then amending domain and range information from LOD. The main idea behind our work stems from the observation that many properties are misused at the instance level or used in several, distinct contexts. The three algorithms we proposed, namely, LeXt, ReXt, and LeRiXt, exploit statistics about the types of the entities appearing as subject and object in the triples involving the property analyzed in order to identify the various cases in which a multi-context property is used. Once a particular context is identi ed, a new sub-property is derived such that occurrences of the original property can be substituted using the newly generated sub-property. Our methods can also be used to provide insight into the knowledge base analyzed and how it should be revised in subsequent iterations. We evaluated our methods by studying their behavior with di erent parameter settings and by asking Semantic Web experts to evaluate the generated sub-properties.
The algorithms we propose require the entities contained in the dataset to be typed with types organized in a treestructured type hierarchy. As future work, we plan to run a deeper evaluation of our techniques, and to design a method that overcomes the limitation presented above by considering the case in which the entity types are organized in a Direct Acyclic Graph, thus supporting multiple inheritance.
This work was supported by the Haslerstiftung in the context of the Smart World 11005 (Mem0r1es) project and by the Swiss National Science Foundation under grant number PP00P2 128459.