Simple-Run Semantics for RPQs

In database theory, RPQs (regular path queries) are the building block of most query languages for querying graph databases. RPQs are generally evaluated under homomorphism semantics; in particular only the endpoints of the matched walks are returned. On the contrary, due to user pressure, most real graph-database engines actually return the full matched walks. Under homomorphism semantics, there might be an infinite number of such walks. Hence each real query language had to adapt the semantics of RPQs in order to meet this popular demand, often neglecting theoretical implications. For instance, the most popular query language, Cypher, uses trail semantics: only walks with no repeated edges are returned. In that case, the result set is indeed finite, but the simplest computational problems are untractable. We propose new semantics for RPQs, called simple-run semantics, as a candidate to reconcile theoretical considerations with practical aspirations. Just as trail semantics, simple-run semantics aims at keeping the output finite by filtering out redundant results. Trail semantics filter based on redundancy in the computed walk: repeated edges are forbidden. Simple-run semantics filter based on redundancy in the run: a node can be reused only if the query computation did progress compared to the previous times the node was visited. Joint work with Claire David and Nadime Francis.

Authors

• Victor Marsault

Keywords

No keywords are indexed for this paper.