On the data complexity of consistent query answering over graph databases

作者：

Highlights：

• The data complexity of consistent query answering over graph databases is studied.

• Queries and constraints are based on conjunctive regular path queries (CRPQs).

• We prove intractability and/or undecidability even in restricted scenarios.

• By restricting the data or the constraints we obtain relevant tractable cases.

摘要

•The data complexity of consistent query answering over graph databases is studied.•Queries and constraints are based on conjunctive regular path queries (CRPQs).•We prove intractability and/or undecidability even in restricted scenarios.•By restricting the data or the constraints we obtain relevant tractable cases.

论文关键词：Graph databases,Regular path queries,Consistent query answering,Description logics,Rewrite systems

论文评审过程：Received 7 September 2015, Revised 14 March 2017, Accepted 31 March 2017, Available online 25 April 2017, Version of Record 11 June 2017.

论文官网地址：https://doi.org/10.1016/j.jcss.2017.03.015