Foundations of semantic web databases

TLDR

The Semantic Web augments web data with machine‑readable semantics through RDF, a subset of binary first‑order logic that supports anonymous objects, and its extension RDFS, which adds reification, typing, and inheritance, thereby creating formal challenges for studying RDF/RDFS sets and query languages that have received limited foundational work. The authors aim to investigate these foundational aspects, particularly the computational properties of entailment and redundancy in RDF/RDFS. They propose a query language with formally defined semantics and analyze the complexity of query processing, containment, and answer simplification.

Abstract

The Semantic Web is based on the idea of adding more machine-readable semantics to web information via annotations written in a language called the Resource Description Framework (RDF). RDF resembles a subset of binary first-order logic including the ability to refer to anonymous objects. Its extended version, RDFS, supports reification, typing and inheritance. These features introduce new challenges into the formal study of sets of RDF/RDFS statements and languages for querying them. Although several such query languages have been proposed, there has been little work on foundational aspects. We investigate these, including computational aspects of testing entailment and redundancy. We propose a query language with well-defined semantics and study the complexity of query processing, query containment, and simplification of answers.