文章基本信息

标题：Containment of UC2RPQ: The Hard and Easy Cases
本地全文：下载
作者：Diego Figueira
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：155
页码：9:1-9:18
DOI：10.4230/LIPIcs.ICDT.2020.9
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study the containment problem for UC2RPQ, that is, two-way Regular Path Queries, closed under conjunction, projection and union. We show a dichotomy property between PSpace-c and ExpSpace-c based on a property on the underlying graph of queries. We show that for any class C of graphs, the containment problem for queries whose underlying graph is in C is in PSpace if and only if C has bounded bridgewidth. Bridgewidth is a graph measure we introduce to this end, defined as the maximum size of a minimal edge separator of a graph.
关键词：Regular Path Queries (RPQ); 2RPQ; CRPQ; C2RPQ; UC2RPQ; graph databases; containment; inclusion; equivalence; dichotomy; graph measure; bridge-width (bridgewidth); minimal edge separator; minimal cut-set; max-cut; tree-width (treewidth)