Top-k reasoning for the Semantic Web
Stefan Schlobach · Data Archiving and Networked Services (DANS) · 2011
Data on the Semantic Web (SW) is ordered, for instance, through orderings over literals (e.g., age, heights, location, rating etc), resources (e.g., popularity) or triples (e.g., provenance, confidence, timestamps). Recently orderings have been established as first class citizens in an extended SPARQL algebra, with an efficient calculus for finding, e.g., top-k answers. With this paper we attempt to stimulate a similar initiative for reasoning, by 1) discussing various types of orderings on the SW, 2) introduce the notion of top-k closure, and 3) sketch an algorithm for calculatign this closure based on top-k database joins. The Web of Data is ordered Orderings are omnipresent on the Web of Data. Sometimes resources are directly, and explicitly, described by triples containing ordered literals, providing information about the number of inhabitants of cities, ratings of restaurants, longitude and latitude or dates of birth etc. However, most data on the Web of Data also comes with a variety of implicit ordering measures, as resources are not just ordered by size or age, but also by meta-properties such as popularity. It is well-known that one of the prime criteria for ranking search results in Information Retrieval is based on the trust-worthiness of results, which is calculated using PageRank as a proxy, i.e. the number and importance of web-sites linking to the search result. Similarly, in web-scale semantic search, we cannot ignore the trust-worthiness of resources, and their available information. This implies that resources in Semantic Web ontologies intrinsically come with implicit orderings, which could/should be taken into account when answering queries. But not only are resources ordered, so are triples. There is plenty of literature on how to extend triple with meta-data and annotations, and most of those ideas induce (at least partial) orderings on triples: based on uncertainty, temporal dimensions, provenance, trust to name but a few [6,5,1]. Clearly, orderings occur everywhere, and in a variety of forms and contexts, and querying and reasoning over ordered data becomes a critical problem on the Web of Data. The Semantic Web community has started to cater for this need by including the ORDERED-BY operator into SPARQL, and recently, by extending the SPARQL algebra by a ranking operator [2]. This allows the application of optimisation from recent work in ranking in relational databases by extending the idea of efficient top-k joins to the SPARQL execution model. Unfortunately, these efforts have not yet found their counter-part on the reasoning side. More concretely, although novel querying algorithms make use of the orderings of resources and triples, and although a variety of extensions of RDF and more expressive ontology languages (such as RDFS and OWL) with annotations have been proposed there is to the best of our knowledge no attempt to provide generic methods for efficient reasoning over such orderings as of yet. Let us introduce the problem (slighly misusing notation for simplicity): A’dam owl:sameAs dbpedia:Amsterdam. LaTheatina hasRanking 5 ; locatedIn A’dam. VURestaurant hasRanking 1 ; locatedIn A’dam. LaValade rdf:type FrenchRestaurant; locatedIn dbpedia:Amsterdam. QuickFood hasRanking 2 ;