文章基本信息

标题：On the Data Complexity of Consistent Query Answering over Graph Databases
本地全文：下载
作者：Pablo Barcel{\'o ; Ga{\"e}lle Fontaine
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：31
页码：380-397
DOI：10.4230/LIPIcs.ICDT.2015.380
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：graph databases; regular path queries; consistent query answering; description logics; rewrite systems