Instance-uni¯cation is a prime example for uncertainty on the Semantic Web, as it is not always possible to automatically determine with absolute certainty whether two references denote the same object or not. In this paper, we present openacademia, a semantics-based system for the management of distributed bibliographic information collected from the Web, in which the Instance Uni¯cation problem is ubiquitous. Our tentative solution is Rough DL, a simple extension of classical Description Logics, which allows for approximations of vague concept. This shows that already a simple formalism for dealing with uncertain information in a qualitative way can provide an elegant solution to practical problems on the Semantic Web.
When information is gathered from the Web it often occurs that multiple descriptions of the same resource are found. In that case the duplicate resources should be identi¯ed and their descriptions have to be combined.
Failing to e®ectively deal with duplicate results negatively a®ects the
workings of all search engines. In a search system for publications instance uni¯cation
is important for at least two types of information: persons and publications. If
coreferences of persons [
The most common way of representing the results of instance uni¯cation is to declare the objects to be logically equivalent. This has the consequence that all properties of one resource are also properties of the other resource. However, this implementation has several drawbacks. First, it often represents a logical overcommitment. Only in very limited cases are we absolutely certain that two instances are equivalent, in most cases we only have some partial evidence that two descriptions refer to the same object (e.g. name similarity). Further, it is not possible to distinguish between di®erent levels of con¯dence in similarity relations. Moreover, transitivity of equivalence often causes an undesired propagation of equivalence over similarity relations.
In this paper, we will introduce an alternative to complete instance uni¯cation, which allows for reasoning over gradually weakening notions of similarity. Our tentative solution is an extension to standard DL that can be used for de¯ning approximations of concepts without increasing the complexity of the language.
We illustrate the use of this language in openacademia,1 an open source
webbased system for collecting, aggregating and querying publication metadata in
a group or community setting. openacademia o®ers an interactive, AJAX-based
search interface for querying publications by a combination of facets. Query
results can be visualized in a number of ways, including the possibility to generate
various dynamic HTML representations that can be easily inserted into personal
homepages or institutional publication pages. Integrating descriptions of similar
persons and publications is an important task of this system, which is in this
context sometimes called smushing [
In the subsequent sections, we introduce the language for de¯ning approximations, and apply it to model di®erent levels of similarity of persons and publications in openacademia. The °exible instance uni¯cation using Rough DL illustrates how already rather simple mechanisms for dealing with uncertainty in a qualitative way can be used to elegantly solve practical problems on the Web.
Of course, we do not claim that our practical problem could not have been solved by other, for example more quantitative formalisms. However, we believe that the simplicity of our approach makes it an attractive alternative for dealing with uncertainty on the Semantic Web. 2
In [
De¯nition 1. A relation is called a similarity (or tolerance) relation if it is re°exive and symmetric. An equivalence relation is a transitive similarity relation.
As equivalence relations extend similarity relations, we de¯ne Rough DL using the latter. We will use the notation Csim and Csim to describe the approximations of a class C with respect to a similarity relation sim. We will omit the 1 http://www.openacademia.org 2 As the relation between OWL and Description Logics is well established, we only introduce rough DL. The extension to rough OWL is conceptually trivial. lower-script and upper-script sim whenever the choice of relation is irrelevant. The intuition regarding Csim is that it denotes the set of all elements that are possibly in C, whereas Csim is meant to describe all elements de¯nitively in C. Often such an operator is useful when C cannot be speci¯ed in a crisp way. By way of the approximation(s) we can at least restrict C with an upper, and a lower, bound.
An illustrating example The following picture illustrates the general idea. In
the spirit of Rough Set theory [
Each square denotes a set of domain elements, which cannot further be discerned by some available criterion at hand. The encircling line denotes the set of Semantic Web authors, i.e., the vague concept which we are incapable to formally de¯ne. If we capture this lack of criteria to discern between two objects as a indiscernibility relation indis, we can formalize the upper approximation as the authors that are indiscernible from at least one Semantic Web author.
Similarly, we can de¯ne the lower approximation as the set of authors containing all, and only those authors, for which it is known that all indiscernible authors must be Semantic Web authors.
In our picture, the upper approximation is depicted as the union of the dark squares (the lower approximation), and the gray squares, the boundary. Note that in our example, following the literature on Rough Sets, the similarity of objects is determined by the indiscernibility of resources. This is an equivalence relation, which makes it appropriate to denote the sets of indiscernible instances as disjoint squares.
This intuition suggests two uses for Rough DL: ¯rst as a modeling language for representing vague knowledge and, secondly, as a language to query over similarity in a domain.
Modeling vague concepts Even if it is impossible to formally de¯ne a concept such as SWAuthor, we can often specify the approximations. The class of Semantic Web authors cannot be de¯ned in a crisp way, but it is easy to think of an upper approximation (the possible Semantic Web authors, e.g. all authors having published in a Semantic Web conference or Journal). Rough DL semantics enforce restrictions on the class SWAuthor indirectly. We will discuss modeling with Rough DL concepts later in more detail. Qualitative querying over similarities In the case of instance uni¯cation Rough DL can be used for querying classes of objects, and objects that were identi¯ed as being similar. Suppose we have a particular author author who is uniquely identi¯able, say via his FOAF pro¯le. Now, an algorithm Alg for object de-referencing creates a relation simAlg of pairs (author1,author2). Based on this relation each algorithm for referencing induces a set PossiblyAlg(author) for each author author, i.e. a set of objects of the domain U which possibly correspond to this particular author author, with the formal de¯nition: PossiblyAlg(author) = fi 2 U j9j 2 U : (i; j) 2 simAlg & j 2 oneOf(author)g; which corresponds almost exactly to the formal semantics of an upper approximation. Most of the remainder of this paper will be about using Rough DL for querying ontologies with explicit similarities. 2.1
Semantics of Rough DL
Using this property we can de¯ne the semantics of the approximations formally:
De¯nition 2. Let a rough interpretation be a triple I = (U; R»; ¢I ), where U is
a universe, ¢I an interpretation function, and R» an equivalence relation over
U . The function ¢I maps RDL concepts to subsets and role names to relations
over the domain U . It extends to the new constructs as follows:
{ (C)I = fi 2 U j 9j 2 U : (i; j) 2 R» & j 2 CIg
{ (C)I = fi 2 U j 8j 2 U : (i; j) 2 R» ! j 2 CIg
The semantics of the lower approximation is de¯ned as usual as the dual operator
Csim = ::Csim with its respective semantics. Depending on the speci¯cs of the
similarity relation, these semantics enforce powerful terminological consequences.
In [
Related to these semantic consequences is the question of reasoning support, i.e. the existence of tools that can calculate consequences such as the ones discussed above in reasonable time. This points to the nice property of Rough DL being a conservative extension of OWL, in the sense that any Rough DL ontology can be translated into a logically equivalent OWL ontology. This means that reasoning for our language comes for free, as we can use standard reasoners to calculate class hierarchies, consistency and all instances of a particular class. The latter is the reasoning most needed in openacademia.
We can now relate these semantics of Rough DL to our example of instance uni¯cation given before. If we identify the class TBL with the singleton set t.b-l, i.e. de¯ne TBL to be equivalent to oneOf(t.b-l), the set PossiblyAlg(t.b-l) semantically corresponds to the upper approximation of TBL according to the indiscernibility relation simAlg.
Adapting Rough DL for openacademia As already mentioned, for
application of Rough DL in openacademia we need a slightly di®erent formalism from
the one introduced in [
Similarity versus equivalence In openacademia, approximations based on similarity relations are used in addition to equivalence relations. Some smushing algorithms indeed produce equivalences, e.g. when two instances are identi¯ed through equivalence of the value of an inverse functional property. But even in logically weaker cases, there will be methods which indicate most likely equivalence between objects.
On the other hand, there are weaker methods, which will give indications for similarity, and which are not transitive. A simple example is edit distance: a similarity between two instances which is de¯ned by an edit distance smaller or equal to 1 is non-transitive.
Hierarchies on similarities & approximations In an application such as openacademia there is no unique best way to identify co-reference of instances. This means that there will usually be several algorithms, such as the ones described in the following section, which produce several possible similarity relations. Often inclusion properties of such relations are easily created, and are often even more meaningful than quantitative values. In an RDF(S) based framework we can make use of hierarchies on relations to specify con¯dence in smushing algorithms in a qualitative way.
A simple logical consequence of specifying similarities in hierarchies of properties is that it implies hierarchies of the approximations. More concretely, suppose that two algorithms A1 and A2 produce two similarities oa:similarToA1 and oa:similarToA2 where, by construction, individual1 oa:similarToA1 individual2 implies that individual1 oa:similarToA2 individual2. This is a typical case, as smushing algorithms often include results of other algorithms. In this case, it can be shown that an upper approximation based on oa:similarToA1 is more speci¯c than an upper approximation based on oa:similarToA2.
We make use of this property to construct hierarchies of approximations based on the underlying similarity relations, which can be very useful for controlled query relaxation. 3
The current interface of openacademia allows to query for publications using combinations of di®erent criteria, such as \author", \title", \year", \type" and \group". With respect to the author criteria, users can provide a string that is matched to a part of the author name.
This is a suboptimal solution when one wants to have precise control over the search results, as there is no way to distinguish between publications of di®erent authors with a similar name. Regardless of instance uni¯cation, the result will be a mix of publications of possibly di®erent persons.
A ¯rst requirement for controlled instance uni¯cation is to search by the URI of the resource instead of its label. For example, the system could search by label and return a list of publications. Then, the user could select a speci¯c instance of an author in the result list, whose URI is used for the subsequent searches.
openacademia currently uses several methods to determine similarity between authors and publications, which are sometimes called smushing algorithms. 1. The most certain way to determine the equivalence of two resources is by comparing the values for their owl:InverseFunctionalProperty's. When two resources have the same value for such a property they can be considered as equivalent. The FOAF-speci¯cation de¯nes a number of properties, including foaf:mbox and foaf:homepage as inverse functional. 2. Another method is based on the comparison of the labels of resources. In openacademia we use several heuristics with di®erent certainty to determine possible equivalences. For example, we consider instances of foaf:Person as uni¯cation candidates if both their ¯rst and last names match exactly (i.e. the string is identical), or if their last name and their initials match, or if their last name and ¯rst name are within a certain edit-distance. 3. An alternative method exploits the similarity of related resources. If, e.g., two instances of swrc:Publication are determined to be equivalent, we assume that the resources in the author-list are also equivalent.
Di®erent from related work that focuses on learning the rules of smushing
(e.g. [
To re°ect the fact that di®erent algorithms have a di®erent certainty, we add similarity statements of the form individual1 oa:similarToX individual2 to the repository. Each individual must be identi¯ed by a URI and oa:similarToX is a similarity relation of instances returned by one of the algorithms discussed. 3.1
Bene¯ts of Rough DL In the context of openacademia, Rough DL has two functions: it o®ers an appealing conceptual framework for querying over similarities, and it provides the possibility to model vague concepts, such as typical Semantic Web authors. We will discuss both features in more detail. Querying over similarities Using similarities for object-dereferencing is a relatively obvious proposal as the problems of ad-hoc solutions (such as using owl:sameAs) are known. However, most people decide to use the slight overcommitment of owl:sameAs in order to be able to continue to use the automatic reasoning support for OWL, i.e. in order to avoid having to deal with similarities explicitly.
Rough DL o®ers an attractive alternative, as it provides a conceptually elegant framework for querying an RDF(S) repository including similarity relations by two simple operators (¢) and (¢), the approximations. Let us start with a simple example of how Rough DL can help in order to formulate concise queries over graphs including similarities.
Suppose we have identi¯ed two resources, a1 and a2, each of type foaf:Person. Each resource is connected via a swrc:author property to a number of resources of type swrc:Publication (p1. . . p4). Besides this, a1 and a2 each have an rdfs: label. One of the similarity heuristics discovered a similarity between the labels of a1 and a2, which is represented by a property oa:similarTo between both resources.
J.Smith rdfs:label
a1 swrc:author oa:similarTo p3
p4 swrc:author p1 p2 a2
John Smith rdfs:label The obvious query to take from this graph is to ¯nd all publications of the resource a1, uniquely identi¯ed by the URI <http://www.uni1.edu/~personA/pubs.bib#john_smith>, and every resource that is similar.
Formulating this as instance checking in Rough DL is simply to ask for all instances of class oneOff...#john smithg (for the resource). Already for such a simple Rough DL query, the corresponding SeRQL query requires explicit knowledge of the structure of the graph, and of the similarity relation used. SELECT distinct Pub FROM {Pub} swrc:author {Person}, {Person} oa:nameSimilarTo3
{<http://www.uni1.edu/~personA/pubs.bib#john_smith>}
Another example exploits similarities between publications. Suppose that we add di®erent kinds of similarity relations between publications. For example, two publications could be connected via a property oa:hasJointAuthors if they share at least two authors. Or, another possibility, they can be connected via oa:hasRelatedKeywords if their keywords are related according to some metric, e.g. because the keywords are semantically close to each other in some topic hierarchy. One could even add similarity relations based on the textual overlap of the abstract.
Now, the Rough DL framework allows queries for upper approximations | according to a speci¯c type of similarity | of publications that ful¯ll speci¯c criteria. For example, if we use the \author overlap" similarity, we could query for the upper approximation of papers with \OWL" as a keyword by simply asking for the instances of the Rough DL class restriction(keyword hasValue("OWL")). When we have oa:hasJointAuthors in place as a similarity relation we get as the result all papers of authors that together have published papers with OWL as a keyword. Again, the corresponding SeRQL query is simple, but we could easily use a di®erent similarity measure without requiring any change for the user. SELECT DISTINCT Pub FROM {Pub}
oa:hasJointAuthors {Other}, WHERE {Other} IN (SELECT Pub FROM {Pub} swrc:keyword {"OWL"}) Modeling vague concepts in OA Up to now we discussed the use of Rough DL for formulating queries over an RDF(S) repository with similarity relations. But of course, the language can also be used to model vague concepts directly in the repository. Imagine that one wants to model Semantic Web conferences and authors, obviously terms that describe vague concepts for which it will be impossible to ¯nd commonly agreed upon de¯nitions. What is possible, on the other hand, is to de¯ne approximations for both classes. Most people would agree that there are three prototypical Semantic Web conferences: the International and European Semantic Web conferences (ISWC and ESWC), and the World-Wide Web conference (WWW). De¯ning the lower approximation of a class SWconference can then be done simply as SWconference = WWW t ISWC t ESWC where the conferences are described as classes (e.g. ISWC) containing at least one uniquely identifying resource (e.g., ns:iswc). Here, we chose the lower approximations of the resources for the conferences as we want to avoid ambiguity through spelling variants or other forms of synonymy (e.g. ESWC also refers to the Electronic Sports World Cup).
Semantic Web authors can now be de¯ned as authors having published at possible Semantic Web conference, i.e.
SWauthor = 9 publishedIn.SWconference
Even though Rough DL is a conservative extension of OWL DL this example shows that modeling the same information without approximation operators would be extremely cumbersome. Using Rough DL, and the reasoning machinery that comes for free, thanks to the translation back to OWL, allows queries such as for all possible Semantic Web authors i : SWauthor?, which even for this simple example is non-trivial on a larger data set.
Furthermore, for the Rough DL fragment built on the OWL DL dialect, the usual reasoning services, such as query entailment, satis¯ability checking or subsumption hierarchies can be easily calculated.
For openacademia querying with Rough DL is the more prominent
application, and we have not yet pursued modeling of rough concepts in openacademia.
Technically, and conceptually, it is easy to add Rough DL axioms to the Sesame
repository. By adding rules, part of the OWL semantics can be captured, but
completeness cannot be achieved. A more detailed study of this, e.g.,
considering the alternative semantics proposed in [
Technical Issues The application of Rough DL in openacademia ampli¯es a discrepancy of two Knowledge Representation frameworks that is present in many practical approaches to the Semantic Web. With query languages such as SeRQL or SPARQL for RDF(S) ontologies and the advent of robust and fast RDF repositories, e±cient data access is now made possible even for very large data sets. On the other hand, the expressivity of OWL makes it possible to model ontological knowledge in very elegant ways, which is needed for many realistic applications. Unfortunately, theoretically both paradigms are less easily integrated than one would hope for, and than could be expected at ¯rst glance. 1. A ¯rst issue is the use of a query-language such as SeRQL for a repository containing OWL statements. 2. The second problem to be addressed is the question of Open- versus Closed
World Assumption.
For lack of space both issues can only be discussed brie°y.
First, to make use of the best of both worlds, many people include OWL
ontologies in RDF repositories, and query those with traditional RDF query
languages. The problem with such an approach is that completeness cannot be
guaranteed in general. For openacademia we do the same: particular knowledge
is represented in OWL (e.g. de¯ning a property as transitive or functional), but
SeRQL is used for querying. In the case of openacademia, however, the problem
of incompleteness can be circumvented. This is done by including parts of the
OWL semantics in the Sesame inference engine (in the style of [
Secondly, querying a triple store such as Sesame usually employs a CloseWorld assumption, i.e. a universally quanti¯ed statement is evaluated as true if all known instances in the relation have the required property. This is di®erent than DL, where an Open-World Assumption is taken. For the lower approximation this means that the DL interpretation di®ers from the interpretation of a natural SeRQL encoding. As a DL query for lower approximations will only return relevant results when there are explicit universal statements (or approximations) in the ontology, our current research focuses on the use of the upper approximation for querying. 4
To illustrate the bene¯ts of Rough DL descriptions in practice, we show the e®ect of applying di®erent approximations in openacademia. For this, we use the approximation interface as shown in Figure 1. This interface translates a restricted set of Rough DL queries into SeRQL.
We apply Rough DL for author similarity, using a hierarchy of similarities. Suppose we want to query for publications of \Marta Sabou" with several entries in our database. We start with a URI <http://www.uni1.edu/~personA/pubs.bib# marta_sabou> in our own BibTeX ¯les, which gives high con¯dence that the resource represents the right person.
No approximation Without approximation, a query for the publications of this resource results in 3 publications, which were all speci¯ed in <http: //www.uni1.edu/~personA/pubs.bib>.
Exploiting inverse functional properties Smushing adds oa:nameSimilarTo1 statements between all resources with the same value for an inverse functional property. As Marta's email is listed in her FOAF-pro¯le, an oa:nameSimilarTo1 statement is added between the original resource and <http://www.uni1.edu/ swhome/person/marta>, an RDF representation of a personnel database. When querying for the upper approximation of the resource, the search results now include the publications on Marta's homepage.
Exact match of fullname A second level of approximation uses the label of the resources of type foaf:Person. When the ¯rst and lastname of a person exactly match, a oa:nameSimilarTo2 is added. This results in similarity statements between the original resource and <http://www.uni2.edu/~personB/ biblio/bnaic2002.bib#marta_sabou> and <http://www.uni3.edu/~personC/pubs. bib#marta_sabou>. When using this property as similarity in the Rough DL framework, the search result contains 7 publications.
Exact match of lastname and initial The next level of approximation exploits the oa:nameSimilarTo3 statements that are added when both the lastnames match and the initial of one resource matches the ¯rst character of the ¯rstname of another resource. This results in similarity statements to the resource <http://www.uni3.org/~personD/publications.bib#m_sabou> with the label \M. Sabou" and the resource <http://www.uni1.edu/swhome/person/marta> with the label \M.R. Sabou", yielding in one new publication.
Fuzzy match on fullname The ¯nal level of approximation uses n-gram distance between labels of two resources and adds oa:nameSimilarTo4 when the distance is above some threshold. In our data set there is such a statement between the original resource and <http://www.uni4.edu/publications/ins.bib# martha_sabou>, which has \Martha Sabou" as label. This again added one additional publication, resulting in 9 publications.
Note that we only discussed the additional search results in the description above. However, when exploiting the similarities between the authors in the search, we also get duplicate resources for publications for which we apply a similar strategy to combine publication resources. 5
Summary Rough DL is a conservative extension of DL, i.e. an extension of DL with new operators for modeling vague concepts, that does not increase the expressive power of the original language. We show that this language is suitable for reasoning over similarities or equivalences introduced into an ontology through co-reference resolution. Rough DL provides a qualitative way of representing vague concepts, and to reason and query over similarities. By applying Rough DL to openacademia we show that AI techniques can elegantly solve practical problems on the web.
To make the Rough DL version of openacademia robust and e±cient for large collections, e.g., crawled on the WWW, the application has initially been restricted to querying. Large scale experiments with Rough DL modeling are planned as future work to evaluate scalability of this theoretically promising framework.
Related Work The related work covers modeling vagueness in ontologies, most
prominently in combining fuzzy logic with Semantic Web research, as
exempli¯ed in [
There, however, lies the biggest di®erence to our approach, which focuses on qualitative modeling of vagueness and querying over similarities. For some domains and particular applications, such as for access to distributed data sources, this approach can be more appropriate. This does not just hold for bibliographic data, but for any data integration where the identity of resources cannot always be established with absolute certainty, and where qualitative querying over similarities can provide a ¯ne-grained access to collections.
Future Work The application of Rough DL to openacademia is a ¯rst step towards achieving the full potential of the language. Currently, SeRQL queries are automatically created for narrowing or broadening search results. A next step will be to extend querying to more expressive Rough DL queries, and to integrate Rough DL in the ontology. Together with such an extension of the functionality we will have to undertake a detailed investigation of the scalability of the system, and a qualitative and quantitative analysis of the e®ects on the querying results in openacademia.