On implementing provenance-aware regular path queries with relational query engines

Saumen Dey, Víctor Cuevas-Vicenttín, Sven Köhler, Eric Gribkoff, Michael Wang, Bertram Ludäscher

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Use of graphs is growing rapidly in social networks, semantic web, biological databases, scientific workflow provenance, and other areas. Regular Path Queries (RPQs) can be seen as a core graph query language to answer pattern-based reachability queries. Unfortunately, the number of freely available systems for querying graphs using RPQs is rather limited, and available implementations do not provide direct support for a number of desirable variants of RPQs, e.g., to return those edges that are contained in some (or all) paths that match the given regular expression R. Thus, by returning not just a pair (x, y) of end points of paths that match R, but also "witness edges" (u, v) inbetween, our RPQ variants can be understood as returning additional provenance information about the answer (x, y), i.e., those edges (u, v) that are in some (or all) paths from x to y matching R. We propose a number of such RPQ variants and show how they can be implemented using either Datalog or a suitable RDBMS. Our initial experimental results indicate that RPQs and our provenance-aware variants (RPQProv), when implemented using conventional relational technologies, yield reasonable performance even for relatively large graphs. On the other hand, the overhead associated with some of these variants also makes efficient handling of provenance-aware graph queries an interesting challenge for future research.

Original languageEnglish (US)
Title of host publicationJoint EDBT/ICDT 2013 Workshops - Proceedings
Number of pages10
StatePublished - May 2 2013
Externally publishedYes
EventJoint EDBT/ICDT 2013 Workshops - Genoa, Italy
Duration: Mar 18 2013Mar 22 2013

Publication series

NameACM International Conference Proceeding Series


OtherJoint EDBT/ICDT 2013 Workshops


  • datalog
  • graph querying
  • regular path queries

ASJC Scopus subject areas

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'On implementing provenance-aware regular path queries with relational query engines'. Together they form a unique fingerprint.

  • Cite this

    Dey, S., Cuevas-Vicenttín, V., Köhler, S., Gribkoff, E., Wang, M., & Ludäscher, B. (2013). On implementing provenance-aware regular path queries with relational query engines. In Joint EDBT/ICDT 2013 Workshops - Proceedings (pp. 214-223). (ACM International Conference Proceeding Series). https://doi.org/10.1145/2457317.2457353