Week 1 Report

Exploring literature focusing on the following topic:
1. Graph queries and structure
2. Regular Path Queries (RPQ)
3. DataONE Open Provenance Modle(D-OPM)
Reading related papers and write a summary.

Selected papers:
[1] P. Wood, Query languages for graph databases.
[2] S. Dey, S. kohler, S. Bowers, B. Ludaescher, Datalog as a lingua franca for provenance querying and reasoning.
[3] Y. Liu, S. Stoller, Querying complex graphs.
[4] M. Wang, Implementing Regular Path Queries with RDBMSes, MS thesis.
[5] working draft by ProvWG about D-OPM

Brief summary:
[1] gives a nice survey of many graph query languages with two emphases: graph model and query languages and query functionality. Certain languages has certain advantage and the paper also gives a overview of RPQ for path finding.
[2] provides a connection between workflows and traces and unifies the representation of the provenance information using graph with labeled edges, which is easy for provenance querying and reasoning. This paper only introduced couple of definitions and brief overview the idea along with some examples. looking forward to the full version.
[3] presents a language for querying complex graph. The language is similar to RPQ but the label on the edges could contain parameters and scoping, which makes the query easier and more powerful. The paper also provides a transformation into datalog, a way to implement.
[4] is the Michael’s working thesis using SQl to implement RPQ, which is essentially built to query provenance. This thesis provides a detailed introduction to datalog, RPQ etc. also the approach to implement RPQ with examples. I’ll set up Michael’s engine next week for future use.
[5] D-OPM is an extension of OPM with certaion improvements, we’re still working on the draft.


Leave a Reply

Your email address will not be published. Required fields are marked *