On the data complexity of consistent query answering over graph databases

Abstract

Applications of graph databases are prone to inconsistency due to interoperability issues. This raises the need for studying query answering over inconsistent graph databases in a simple but general framework. We follow the approach of consistent query answering (CQA), and study its data complexity over graph databases for conjunctive regular-path queries (CRPQs) and conjunctive regular-path constraints (CRPCs). We deal with subset, superset and symmetric-difference repairs. Without restrictions, CQA is undecidable for the semantics of superset- and symmetric-difference repairs, and Pi(P)(2)-complete for subset repairs. However, we identify restrictions on CRPC5 and databases that lead to decidability, and even tractability of CQA. (C) 2017 Elsevier Inc. All rights reserved.