Efficiently Evaluating Extended CRPQ

We study the query evaluation problem for Extended Conjunctive Regular Path Queries (ECRPQ), a powerful class of queries used to extract information from graph databases. Generally, the problem is PSPACE-complete for ECRPQ, so a natural question emerges as to which subclasses of ECRPQ might have tractable query evaluation. We develop a new multi-hypergraph based abstraction of ECRPQs that answers this question in great detail, both for the query evaluation problem as well as its parameterized version.

Authors

• Varun Ramanathan

Keywords

No keywords are indexed for this paper.