Highlights Conference 2021 Conference Abstract
Efficiently Evaluating Extended CRPQ
- Varun Ramanathan
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.