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

Joseph, Mathew (2015) Query Answering over Contextualized RDF/OWL Knowledge with Expressive Bridge Rules: Decidable classes. PhD thesis, University of Trento.

[img]PDF (PDF) - Doctoral Thesis
Restricted to Repository staff only until 9999.



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.

Item Type:Doctoral Thesis (PhD)
Doctoral School:Information and Communication Technology
PhD Cycle:25
Subjects:Area 01 - Scienze matematiche e informatiche > INF/01 INFORMATICA
Area 01 - Scienze matematiche e informatiche > MAT/01 LOGICA MATEMATICA
Uncontrolled Keywords:Contextualized RDF/OWL, Contextualized Knowledge Bases, Quads, Query Answering, Multi-Context Systems, Forall-Existential Rules, Datalog+-, Description Logics, Semantic Web, Knowledge Representation
Funders:Fondazione Bruno Kessler
Repository Staff approval on:10 Jun 2015 09:42

Related URLs:

Repository Staff Only: item control page