4 papers
Complexity of Evaluating GQL Queries
Diego Figueira, Anthony W. Lin, Liat Peterfreund
GQL has recently emerged as the standard query language over graph databases (particularly, the property graph model). Indeed, this is analogous to the role of SQL for relational d…
Project-connex Decompositions and Tractability of Aggregate Group-by Conjunctive Queries
Diego Figueira, Cibele Freire
We introduce 'project-connex' tree-width as a measure of tractability for counting and aggregate conjunctive queries over semirings with 'group-by' projection (also known as 'AJAR'…
Minimizing Conjunctive Regular Path Queries
Diego Figueira, Rémi Morvan, Miguel Romero
We study the minimization problem for Conjunctive Regular Path Queries (CRPQs) and unions of CRPQs (UCRPQs). This is the problem of checking, given a query and a number , whethe…
Boundedness for Unions of Conjunctive Regular Path Queries over Simple Regular Expressions
Diego Figueira, S. Krishna, Om Swostik Mishra +1
The problem of checking whether a recursive query can be rewritten as query without recursion is a fundamental reasoning task, known as the boundedness problem. Here we study the b…