Query Answering over Contextualized RDF Knowledge with Forall-Existential Bridge Rules: Attaining Decidability Using Acyclicity.
Mathew Joseph, Gabriel M. Kuper, Luciano Serafini · 2014
Abstract. The recent outburst of context-dependent knowledge on the Seman-tic Web (SW) has led to the realization of the importance of the quads in the SW community. Quads, which extend a standard RDF triple, by adding a new parameter of the ‘context ’ of an RDF triple, thus informs a reasoner to distin-guish between the knowledge in various contexts. Although this distinction sep-arates the triples in an RDF graph into various contexts, and allows the reasoning to be decoupled across various contexts, bridge rules need to be provided for inter-operating the knowledge across these contexts. We call a set of quads to-gether with the bridge rules, a quad-system. In this paper, we discuss the problem of query answering over quad-systems with expressive forall-existential bridge rules. It turns out the query answering over quad-systems is undecidable, in gen-eral. We derive a decidable class of quad-systems, namely context-acyclic quad-systems, for which query answering can be done using forward chaining. Tight bounds for data and combined complexity of query entailment has been estab-lished for the derived class.