Despite the recent growth in the size of the Linked Data Cloud, the absence of links between the vocabularies of the sources has resulted in heterogenous schemas. Our previous work tried to nd conceptual mapping between two sources and was successful in nding alignments, such as equivalence and subset relations, using the instances that are linked as equal. By using existential concepts and their intersections to de ne specialized classes (restriction classes), we were able to nd alignments where previously existing concepts in one source did not have corresponding equivalent concepts in the other source. Upon inspection, we found that though we were able to nd a good number of alignments, we were unable to completely cover one source with the other. In many cases we observed that even though a larger class could be de ned completely by the multiple smaller classes that it subsumed, we were unable to nd these alignments because our de nition of restriction classes did not contain the disjunction operator to de ne a union of concepts. In this paper we propose a method that discovers alignments such as these, where a (larger) concept of the rst source is aligned to the union of the subsumed (smaller) concepts from the other source. We apply this new algorithm to the Geospatial, Biological Classi cation, and Genetics domains and show that this approach is able to discover numerous concept coverings, where (in most cases) the subsumed classes are disjoint. The resulting alignments are useful for determining the mappings between ontologies, re ning existing ontologies, and nding inconsistencies that may indicate that some instances have been erroneously aligned.
The Web of Linked Data has seen huge growth in the past few years. As of
September 2011, the Linked Open Data Cloud has grown to a size of 31.6 billion
triples. This includes a wide range of data sources belonging to the government
(42%), geographic (19.4%), life sciences (9.6%) and other domains1. A common
way that the instances in these sources are linked to others is the use of the
owl:sameAs property. Though the size of Linked Data Cloud seems to be
increasing drastically (10% over the 28.5 billion triples in 2010), inspection of the
1 http://www4.wiwiss.fu-berlin.de/lodcloud/state/
sources at the ontology level reveals that only a few of them (15 out of the 190
sources) have some mapping of the vocabularies. For the success of the Semantic
Web, it is important that these heterogenous schemas be linked. As described in
our previous papers on Linking and Building Ontologies of Linked Data [
Though our algorithm was able to identify a good number of alignments, it was unable to completely cover one source with the classes in the other source. Upon closer look, we found that most of these alignments that we missed did not have a corresponding restriction class in the other source, and instead subsumed multiple restriction classes. While reviewing these subset relations, we discovered that in many cases the union of the smaller classes completely covered the larger class. In this paper, we describe how we extend our previous work to discover such concept coverings by introducing more expressive set of class descriptions (unions of value restrictions).2 In most of these coverings, the smaller classes are also found to be disjoint. In addition, further analysis of the alignments of these coverings provides a powerful tool to discover incorrect links in the Web of Linked Data, which can potentially be used to point out and rectify the inconsistencies in the instance alignments.
This paper is organized as follows. First, we describe the Linked Open Data
sources that we try to align in the paper. Second, we brie y review our alignment
algorithm from [
Sources Used for Alignments
Linked Data, by de nition, links the instances of multiple sources. Often, sources
conform to di erent, but related, ontologies that can also be meaningfully linked
[
Linking GeoNames with places in DBpedia : DBpedia (dbpedia.org) is
a knowledge base that covers multiple domains including around 526,000 places
and other geographical features from the Geospatial domain. We try to align
the concepts in DBpedia with GeoNames (geonames.org), which is a geographic
source with about 7.8 million things. It uses a at- le like ontology, where all
2 This work is an extended version of our workshop paper [
Linking LinkedGeoData with places in DBpedia : We also try to nd alignments between the ontologies behind LinkedGeoData (linkedgeodata.org) and DBpedia. LinkedGeoData is derived from the Open Street Map initiative with around 101,000 instances linked to DBpedia using the owl:sameAs property.
Linking species from Geospecies with DBpedia : The Geospecies (geospecies.org) knowledge base contains species belonging to plant, animal, and other kingdoms linked to species in DBpedia using the skos:closeMatch property. Since the instances in the taxonomies in both these sources are the same, the sources are ideal for nding the alignment between the vocabularies.
Linking genes from GeneID with MGI : The Bio2RDF (bio2rdf.org) project contains inter-linked life sciences data extracted from multiple data-sets that cover genes, chemicals, enzymes, etc. We consider two sources from the Genetics domain from Bio2RDF, GeneID (extracted from the National Center for Biotechnology Information database) and MGI (extracted from the Mouse Genome Informatics project), where the genes are marked equivalent.
Although we provide results of the above four mentioned alignments in Section 4, in the rest of this paper we explain our methodology by using the alignment of GeoNames with DBpedia as an example. 3
Aligning Ontologies on the Web of Linked Data First, we brie y describe our previous work on nding subset and equivalent alignments between restriction classes from two ontologies. Then, we describe how to use the subset alignments to nding more expressive union alignments. Finally, we discuss how outliers in these union alignments often identify incorrect links in the Web of Linked Data. 3.1
Our previous work on aligning ontologies of Linked Data
In [
Our algorithm explored the space of restriction classes from two ontologies
and was able to nd equivalent and subset alignments between these restriction
classes. Fig. 1 illustrates the instance sets considered to score an alignment
hypothesis. We rst nd the instances belonging to the restriction class r1 from
the rst source and r2 from the second source. We then compute the image
of r1 (denoted by I(r1)), which is the set of instances from the second source
linked to instances in r1 (dashed lines in the gure). By comparing r2 with the
intersection of I(r1) and r2 (shaded region), we can determine the relationship
between r1 and r2. We de ned two metrics P and R, as the ratio of jI(r1) \ r2j to
jI(r1)j and jr2j respectively, to quantify set-containment relations. For example,
two classes are equivalent if P = R = 1. In order to allow a certain margin
of error induced by the data-set, we used the relaxed versions P' and R' as
part of our scoring mechanism. In this case, two classes were considered
equivalent if P 0 > 0:9 and R0 > 0:9 For example, consider the alignment between
restriction classes (lgd:gnis%3AST alpha=NJ) from LinkedGeoData and
(dbpedia:Place#type=http://dbpedia.org/resource/City (New Jersey)) from
DBpedia. Based on the extension sets, our algorithm nds jI(r1)j = 39, jr2j = 40,
jI(r1) \ r2j = 39, R0 = 0.97 and P 0 = 1.0. Based on our error margins, we assert
the alignment as equivalent in an extensional sense. The exploration of the space
of alignments and the scoring procedure is described in detail in [
r1 r2
Key: I(r1)
Instance pairs where r1 holds
Though the approach produced a large number of equivalent alignments, we were not able to nd a complete coverage because some restriction classes did not have a corresponding equivalent restriction class and instead subsumed multiple smaller restriction classes. For example, in the GeoNames and DBpedia alignment, we found that frdf:type=dbpedia:EducationalInstitutiong from DBpedia subsumed fgeonames:featureCode=S.SCHg, fgeonames:featureCode=S.SCHCg and fgeonames:featureCode=S.UNIVg (i.e. Schools, Colleges and Universities from GeoNames). We discovered that taken together, the union of these three restriction classes completely de ne rdf:type=dbpedia:EducationalInstitution. To nd such previously undetected alignments we decided to extend the expressivity of our restriction classes by introducing a disjunction operator to detect concept coverings completely. 3.2
Identifying union alignments In our current work, we use the subset and equivalent alignments generated by the previous work to try and align a larger class from one ontology with a union of smaller subsumed restriction classes in the other ontology. Since the problem of nding alignments with conjunctions and disjunction of propertyvalue pairs of restriction classes is combinatorial in nature, we focus only on subset and equivalence relations that map to an restriction classes with a single property-value pair. This helps us nd the simplest de nitions of concepts and also makes the problem tractable. Alignments generated by our previous work that satisfy the single property-value pair constraint are rst grouped according to the subsuming restriction classes and then according to the property of the smaller classes. Since restriction classes are constructed by forming a set of instances that have one of the properties restricted to a single value, aggregating restriction classes from the group according to their properties builds a more intuitive de nition of the union. We can now de ne the disjunction operator that constructs the union concept from the smaller restriction classes in these sub-groups. The disjunction operator is de ned for restriction classes, such that i) the concept formed by the disjunction of the classes represents the union of their set of instances, ii) each of the classes that are aggregated contain only a single property-value pair and iii) the property for all those property-value pairs is the same. We then try to detect the alignment between the larger common restriction class and the union by using an extensional approach similar to our previous paper. We call such an alignment a hypothesis union alignment.
We de ne US as the set of instances that is the union of individual smaller restriction classes Union(r2); UL as the image of the larger class by itself, Img(r1)); and UA as the overlap between these sets, union(Img(r1) \ r2)). We check whether the larger restriction class is equivalent to the union concept by using scoring functions analogous to P 0 & R0 from our previous paper. The new scoring mechanism de nes P U0 as jjUUASjj and RU0 as jjUUALjj with relaxed scoring assumptions as in P 0 & R0. To accommodate errors in the data-set, we consider it a complete coverage when the score is greater than a relaxed score of 0.9. That is, the hypothesis union alignment is considered equivalent if P U0 > 0.9 & RU0 > 0.9. Since by construction, each of the subset already satis es P 0 > 0.9, then we are assured that P U0 is always going to be greater than 0.9. Thus, a union alignment is equivalent if RU0 > 0.9.
Figure 2 provides an example of the approach. Our previous algorithm nds that fgeonames:featureCode = S.SCHg, fgeonames:featureCode = S.SCHCg, fgeonames:featureCode = S.UNIVg are subsets of frdf:type=dbpedia:EducationalInstitutiong. As can be seen in the Venn diagram in Figure 2, UL is Img(frdf:type = dbpedia:EducationalInstitutiong), US is fgeonames:featureCode = S.SCHg [ fgeonames:featureCode = S.SCHCg [ fgeonames:featureCode = S.UNIVg, and UA is the intersection of the two. With the educational institutions example, RU0 for the alignment of dbpedia:EducationalInstitution to the union of S.SCH, S.SCHC & S.UNIV is 0.98. We can thus con rm the hypothesis and consider this union alignment equivalent. Section 4 shows additional examples of union alignments. 3.3
Using outliers in union mappings to identify linked data errors The computation of union alignments allows for a margin of error in the subset computation. It turns out that the outliers, the instances that do not satisfy the Img(r1) EducationalInstitution
Union(r2)
Key:
restriction classes in the alignments, are often due to incorrect links. Thus, our algorithm also provides a novel method to curate the Web of Linked Data.
Consider the outlier found in the fdbpedia:country = Spaing fgeonames:countryCode = ESg alignment. Of the 3918 instances of dbpedia:country=Spain, 3917 have a link to a geonames:countryCode=ES. The one instance not having country code ES has an assertion of country code IT (Italy) in GeoNames. The algorithm would ag this situation as a possible linking error, since there is overwhelming support for the ES being the country code of Spain. A more interesting case occurs in the alignment of frdf:type = dbpedia:EducationalInstitutiong to fgeonames:featureCode 2 fS.SCH, S.SCHC, S.UNIVgg. For frdf:type = dbpedia:EducationalInstitutiong, 396 instances out of the 404 Educational Institutions were accounted for as having their geonames:featureCode as one of S.SCH, S.SCHC or S.UNIV. From the 8 outliers, 1 does not have a geonames:featureCode property asserted. The other 7 have their feature codes as either S.BLDG (3 buildings), S.EST (1 establishment), S.HSP (1 hospital), S.LIBR (1 library) or S.MUS (1 museum). This case requires more sophisticated curation and the outliers may indicate a case for multiple inheritance. For example, the hospital instance in geonames may be a medical college that could be classi ed as a university.
Our union alignment algorithm is able to detect similar other outliers and provides a powerful tool to quickly focus on links that require human curation, or that could be automatically agged as problematic, and provides evidence for the error. 4
The results of union alignment algorithm over the four pairs of sources we consider appear in Table 1. In total, the 7069 union alignments explained (covered) 77966 subset alignments, for a compression ratio of 90%.
The resulting alignments were intuitive. Some interesting examples appear in Tables 2, 3 and 4. In the tables, for each union alignment, column 2 describes the large restriction class from ontology1 and colunm 3 describes the union of the (smaller) classes on ontology2 with the corresponding property and value set. The score of the union is noted in column 4 (RU0 = jUAj ) followed by jUAj jULj and jULj in columns 5 and 6. Column 7 describes the outliers, i.e. values of v2 that form restriction classes that are not direct subsets of the larger restriction class. Each of these outliers also has a fraction with the number of instances that belong to the intersection upon the the number of instances of the smaller restriction class (or jImg(r1)\r2j ). It can be seen that the fraction is less than our jr2j relaxed subset score. If the value of this fraction was greater than the relaxed subset score (i.e. 0.9), the set would have been included in column 3 instead. The last column mentions how many of the total UL instances were we able to explain using UA and the outliers. For example, the union alignment #1 of Table 2 is the Educational Institution example described before. It shows how educational institutions from DBpedia can be explained by schools, colleges and universities in GeoNames. Column 4, 5 and 6 explain the alignment score RU0 (0.98), the size UA (396) and the size of UL (404). Outliers (S.BLDG, S.EST, S.LIBR, S.MUS, S.HSP) along with their P 0 fractions appear in column 7. We were able to explain 403 of the total 404 instances (see column 8).
We nd other interesting alignments, a representative few of which are shown in the tables. In some cases, the union alignments found were intuitive because of an underlying hierarchical nature of the concepts involved, especially in case of alignments of administrative divisions in geospatial sources and alignments in the biological classi cation taxonomy. For example, #3 highlights alignments that re ect the containment properties of administrative divisions. Other interesting types of alignment were also found. For example #7 tries to map two non-similar concepts. It explains the license plate codes found in the state (bundesland) of Saarland3. Due to lack of space, we explain the other union alignments alongside in the tables. The complete set of alignments discovered by our algorithm are available on our group page.4
Outliers. In alignments that had inconsistencies, we identi ed three main reasons: (i)Incorrect instance alignments - outliers arising out of possible erro3 http://www.europlates.com/publish/euro-plate-info/german-city-codes 4 http://www.isi.edu/integration/data/UnionAlignments neous equivalence link between instances (e.g. #4, #8, etc.), (ii)Missing instance alignments - insu cient support for coverage due to missing links between instances or missing instances (e.g. #9, etc.), (iii) Incorrect values for properties - outliers arising out of possible erroneous assertion for property (e.g. #5, #6, etc.). In the tables, we also mention the classes that these inconsistencies belong to along with their support. 5
Ontology alignment and schema matching have been a well explored area of
research since the early days of ontologies[
Conclusions and Future Work We described an approach to identifying union alignments in data sources on the Web of Linked Data from the Geospatial, Biological Classi cation and Genetics E n
I # s . r ia ie ed lt p u B O D a t a D o e G d j e k L n U i j L j
A a i U d j ep Aj Lj B Uj Uj D s = e
0U m a R om 2g r v f
f s t n 2 e 2 m p N o e G e h t n g i l a e l p m a x E . 2 e l b a T
Finding Concept Coverings in Aligning Ontologies of Linked Data 9 . 6 ls 9 e 9 v 1 e l t n e m s ( , n s g i l n a o i p s g oh ap S e n
o c S y am itu ,S i:a tr lca
t 4 d un ie i eoGN litIsan itceon bedp= tceoh radnm irrceah
o h 1 G 1 3 2 1 D 1 1 0 ( o
T p
U0 D k 0 e . a 1 d 9 = t .0 G 90 -a e 1 jUjU D o D
L A B j j p .taa 062 jAU iead
9 j , A n 26 jU G e 1 L eo x a m 0 j s p e c i e s
D ow :S s e e c s r h i g o n o
l L , i n p l e o f a n i n c o r r e n t a l i g n m e n t , 93 l
a 1 red ," o n
e e o p t o g ir n h . s e n e P s e s s a l c a l e r r a e l c a n e s
e m r lo C n o e \ lil.eaagxep4Em vp22fg2 i:repdaood2i:i,rreaaoavdnC i:irreaaovnCg i-rseeeavbnnC i:repdaood2i,trreeoapn@ :iteaapdBg lttrrrcceeaoypb ililttreeegabnh :fsrbeydpuT= seeeogudng lffeooayudnnw f:srbeydpuT2litrsee/goxunCR ,,tseeeognnudPG illtscceeooyypm ssbeeyppdouuT= labT bd pbdf epdbd lsoan bd hCf db irohC treyp ib2of P ,eyw ib2o leopm eegm oonm :frd2 lsceaau rreodh treoph ll)re irrceahh Cf SAND t)seaxu ll)re ibo v o a h d c e r s ra g o e e p i n h , e m t = c e e j g b m o a it fo a w s m s e s e u ( ice la I
v d e s in ce Finding Concept Coverings in Aligning Ontologies of Linked Data 11 domains. By extending our de nition of restriction classes with the disjunction operator, we are able to nd alignments of union concepts from one source to larger concepts from the other source. Our approach produce coverings where concepts at di erent levels in the ontologies of two sources can be mapped even when there is no direct equivalence. We are also able to nd outliers that enable us to identify inconsistencies in the instances that are linked by looking at the alignment pattern. The results provide deeper insight into the nature of the alignments of Linked Data.
As part of our future work we want to try to nd a more complete descriptions for the sources. Our preliminary ndings show that the results of this paper can be used to nd patterns in the properties. For example, the countryCode property in GeoNames is closely associated with the country property in DBpedia, though their ranges are not exactly equal. We believe that an in-depth analysis of the alignment of ontologies of sources is warranted with the recent rise in the links in the Linked Data cloud. This is an extremely important step for the grand Semantic Web vision.