Query Answering over Contextualized RDF/OWL Knowledge with Expressive Bridge Rules: Decidable classes

In this thesis, we study the problem of reasoning and query answering over contextualized knowledge in quad format augmented with expressive forall-existential bridge rules. Such bridge rules contain conjunctions, existentially quantified variables in the head, and are strictly more expressive than the bridge rules considered so far in similar setting. A set of quads together with forall-existential bridge rules is called a quad-system. We show that query answering over quad-systems in their unrestricted form is undecidable, in general. We propose various subclasses of quad-systems, for which query answering is decidable. Context-acyclic quad-systems do not allow the context dependency graph of the bridge rules to have cycles passing through triple-generating (value-generating) contexts, and hence guarantees the chase (deductive closure) to be finite. Csafe, msafe and safe classes of quad-systems restricts the structure of descendance graph of Skolem blank nodes generated during chase process to be directed acyclic graphs (DAGs) of bounded depth, and hence has finite chases. RR and restricted RR quad-systems do not allow for the creation of Skolem blank nodes, and hence restrict the chase to be of polynomial size. Besides the undecidability result of unrestricted quad-systems, tight complexity bounds has been established for each of the classes we have introduced. We then compare the problems, (resp. classes,) we address (resp. derive) in this thesis, for quad-systems with analogous problems (resp. classes) in the realm of forall-existential rules. We show that the query answering problem over quad-systems is polynomially equivalent to the query answering problem over ternary forall-existential rules, and the technique of safety, we propose, is strictly more expressive than existing well known techniques such joint acyclicity and model maithful acyclicity, used for decidability guarantees, in the realm of forall-existential rules.