DROPS

Document

DOI: 10.4230/LIPIcs.ICDT.2015.380

On the Data Complexity of Consistent Query Answering over Graph Databases

Authors: Pablo Barceló and Gaëlle Fontaine

Published in: LIPIcs, Volume 31, 18th International Conference on Database Theory (ICDT 2015)

Abstract

Areas in which graph databases are applied - such as the semantic web, social networks and scientific databases - are prone to inconsistency, mainly due to interoperability issues. This raises the need for understanding query answering over inconsistent graph databases in a framework that is simple yet general enough to accommodate many of its applications. We follow the well-known approach of consistent query answering (CQA), and study the data complexity of CQA over graph databases for regular path queries (RPQs) and regular path constraints (RPCs), which are frequently used. We concentrate on subset, superset and symmetric difference repairs. Without further restrictions, CQA is undecidable for the semantics based on superset and symmetric difference repairs, and Pi_2^P-complete for subset repairs. However, we provide several tractable restrictions on both RPCs and the structure of graph databases that lead to decidability, and even tractability of CQA. We also compare our results with those obtained for CQA in the context of relational databases.

Cite as

Pablo Barceló and Gaëlle Fontaine. On the Data Complexity of Consistent Query Answering over Graph Databases. In 18th International Conference on Database Theory (ICDT 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 31, pp. 380-397, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{barcelo_et_al:LIPIcs.ICDT.2015.380,
  author =	{Barcel\'{o}, Pablo and Fontaine, Ga\"{e}lle},
  title =	{{On the Data Complexity of Consistent Query Answering over Graph Databases}},
  booktitle =	{18th International Conference on Database Theory (ICDT 2015)},
  pages =	{380--397},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-79-8},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{31},
  editor =	{Arenas, Marcelo and Ugarte, Mart{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2015.380},
  URN =		{urn:nbn:de:0030-drops-49962},
  doi =		{10.4230/LIPIcs.ICDT.2015.380},
  annote =	{Keywords: graph databases, regular path queries, consistent query answering, description logics, rewrite systems}
}

Search Results

Documents authored by Fontaine, Gaëlle

On the Data Complexity of Consistent Query Answering over Graph Databases

Abstract

Cite as

Thanks for your feedback!

Could not send message