Querying incomplete information in RDF with SPARQL

摘要

Incomplete information has been studied in-depth in relational databases and knowledge representation. In the context of the Web, incomplete information issues have been studied in detail for XML, but very few papers exist that do the same for RDF. In this paper we make the first general proposal for extending RDF with the ability to represent property values that exist but are unknown or partially known using constraints. Following ideas from incomplete information literature, we develop a semantics for this extension of RDF, called RDFi, and study query evaluation for SPARQL. We transfer the concept of representation systems from incomplete information in relational databases to the case of RDFi and identify two very important fragments of SPARQL that can be used to define a representation system for RDFi. The first corresponds to the monotone fragment of graph patterns that uses only the operators AND, UNION, and FILTER. The second corresponds to the well-designed graph patterns, that is, a fragment that uses only operators AND, FILTER, and OPT, and enjoys interesting properties that make query evaluation efficient. We prove that each of the two fragments can be used to define a representation system for CONSTRUCT queries without blank nodes in their templates. We also define the fundamental concept of certain answers to SPARQL queries over RDFi databases and present an algorithm for its computation. Then, we present complexity results for computing certain answers by considering equality, temporal, and spatial constraint languages and the class of CONSTRUCT queries of our representation systems. Finally, we demonstrate the usefulness of RDFi in geospatial Semantic Web applications by giving a number of examples and comparing the modeling capabilities of RDFi with related formalisms found in the literature.