We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Containment of UC2RPQ: The Hard and Easy Cases

19
 Cite
 Share
 Related Material
 Download
 Purchase
No logo availableInternational Conference on Database Theory (ICDT)
 Figueira, Diego

Formal Metadata

Title
Containment of UC2RPQ: The Hard and Easy Cases
Title of Series
Number of Parts
25
Author
License
CC Attribution - NoDerivatives 3.0 Germany:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
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.