{"id":1534,"date":"2013-07-12T15:54:26","date_gmt":"2013-07-12T15:54:26","guid":{"rendered":"https:\/\/notebooks.dataone.org\/?p=1534"},"modified":"2013-07-23T17:20:17","modified_gmt":"2013-07-23T17:20:17","slug":"week-4-more-on-cypher-queries-and-its-comparison-with-other-graph-query-languages","status":"publish","type":"post","link":"https:\/\/notebooks.dataone.org\/pbase\/week-4-more-on-cypher-queries-and-its-comparison-with-other-graph-query-languages\/","title":{"rendered":"Week 4: More on Cypher and its Comparison with other Graph Query Languages"},"content":{"rendered":"

The main focus of this week was on translating some of the main provenance queries into Cypher format and compare it with its equivalence in Gremlin.<\/p>\n

The first thing to do was to add some proper indexes to our Neo4j database. Currently, we have only one property for each node (name) with an auto_index<\/a> on it. Depending on the type of queries, we might need to add some other properties of provenance traces to the Neo4j database later. Writing recursive queries for a single node path (e.g. finding parents of a node) in Cypher is quite straight forward and this makes it a perfect choice for writing provenance lineage queries. Figure 1 shows a recursive query for a social networking graph, Figure 2 shows how to find all actors and data artifacts involved in producing a data node, and Figure 3 shows the use a WHERE clause to filter on pattern and return only the data artifacts (this is not a perfect solution in terms of performance issues because it finds the set of all data artifacts and actors and then filters data artifacts from them. I am still looking to see if I can find a way to define a recursive query for paths with more than one relationship or a repeat of a series of pattern matches. In other words, we need to be able to define something like MATCH n-{<\/strong>[:wasGeneratedBy]->()-[:used]}*<\/strong>->a which, with this format, is not supported by Cypher). One simple solution is to add some extra edges to the graph to directly connect each node with its parent data node and skip the actor between them. For example,<\/p>\n

n- [: wasGeneratedBy]-> () – [:used]-> a<\/p>\n

can be converted to: \u00a0\u00a0n – [:wasDerivedFrom] -> a<\/p>\n

\"2\"<\/a>
Figure 1. An Example of Cypher Recursive Queries<\/figcaption><\/figure>\n
\"Figure<\/a>
Figure 2. Find All Ancestors<\/figcaption><\/figure>\n
\"Figure<\/a>
Figure 3. Find All Data Artifacts Ancestors<\/figcaption><\/figure>\n

Cypher has some other useful clauses, e.g. SKIP, LIMIT to return a subset of results, WITH for chaining queries together, as well as, CREATE, DELETE, SET for modifying the database. Figure 4 shows a Cypher query that creates a star graph.<\/p>\n

\"Figure<\/a>
Figure 4. A Star Graph (click for a larger view)<\/figcaption><\/figure>\n

We can also use regular expressions in Cypher\u2019s WHERE clause.<\/p>\n

\"Using<\/a>
Figure 5. Using Regular Expressions (click for a larger view)<\/figcaption><\/figure>\n

Also, I spent some time on studying two other alternatives for querying graphs: RPQs and Gremlin to see how they compare to Cypher and if they can be used as a complement for Cypher in PBase project.<\/p>\n

Gremlin<\/em><\/a> is a graph traversal language written in the Groovy<\/em> programming language. As opposed to Cypher, Gremlin is an imperative language and is not Neo4j-specific. Gremlin operations are like a series of pipes<\/em>. Each pipe takes an input collection and pushes a an output collection, where a collection can have one item, many items, or no items, and items are vertices, edges, or property values. For example “outE” takes a collection of vertices as input and outputs a collection of edges. A pipeline<\/em> is a collection of pipes that expresses what the problem is in a declarative manner. Thus, Gremlin is a language for building pipelines. Below is a simple example for finding actors that were immediately involved in producing “e38” data node:<\/p>\n

\"1\"<\/a>
Figure 6. Immediate Parents of a Data Node<\/figcaption><\/figure>\n

Gremlin is a traversal-based graph pattern matching language: using “loops” we can traverse other levels of a graph (recursive pattern matching) and “back” enables backtracking.<\/p>\n

\"2\"<\/a>
Figure 7. Traversing More Levels, and Backward Traversing (click for a larger view)<\/figcaption><\/figure>\n

I find Cypher easier to pick up and more suitable for our provenance queries. “Cypher was created because Neo4j Java API was too verbose, Gremlin is too prescriptive, and SQL is unable to express the path”. However, depending on the future needs of the project, we can also use a mixture of the two as they serve for different purposes. It is also important to note that Gremlin might result in a better performance for larger traces [FP13].<\/p>\n

After ProvWG NY meeting, we have a list of general categories of queries that PBase should be able to address. I translated some of those into Cypher and tested them on the current Vistrail trace. Next week, I am going to finalize the queries and run them on some more traces (including traces of multiple run of a Wf). One implicit task will be to gather more traces and convert them to GEOFF format (for that we may need to make some modifications in the current convertor). Neo4j project has a\u00a0 Java code for running Cypher queries<\/a> which, with some modifications, can of use for running PBase project queries.<\/p>\n

All feedback and suggestions for provenance queries are welcome and will be appreciated.<\/p>\n

References.<\/strong><\/p>\n[FP13] Holzschuher, Florian, and Ren\u00e9 Peinl. “Performance of graph query languages: comparison of cypher, gremlin and native access in Neo4j.” In Proceedings of the Joint EDBT\/ICDT 2013 Workshops<\/i>, pp. 195-204. ACM, 2013.<\/p>\n

 <\/p>\n

 <\/p>\n","protected":false},"excerpt":{"rendered":"

The main focus of this week was on translating some of the main provenance queries into Cypher format and compare it with its equivalence in Gremlin. The first thing to do was to add some proper indexes to our Neo4j database. Currently, we have only one property for each node Continue reading Week 4: More on Cypher and its Comparison with other Graph Query Languages<\/span>→<\/span><\/a><\/p>\n","protected":false},"author":40,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[19],"tags":[],"_links":{"self":[{"href":"https:\/\/notebooks.dataone.org\/wp-json\/wp\/v2\/posts\/1534"}],"collection":[{"href":"https:\/\/notebooks.dataone.org\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/notebooks.dataone.org\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/notebooks.dataone.org\/wp-json\/wp\/v2\/users\/40"}],"replies":[{"embeddable":true,"href":"https:\/\/notebooks.dataone.org\/wp-json\/wp\/v2\/comments?post=1534"}],"version-history":[{"count":64,"href":"https:\/\/notebooks.dataone.org\/wp-json\/wp\/v2\/posts\/1534\/revisions"}],"predecessor-version":[{"id":1621,"href":"https:\/\/notebooks.dataone.org\/wp-json\/wp\/v2\/posts\/1534\/revisions\/1621"}],"wp:attachment":[{"href":"https:\/\/notebooks.dataone.org\/wp-json\/wp\/v2\/media?parent=1534"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/notebooks.dataone.org\/wp-json\/wp\/v2\/categories?post=1534"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/notebooks.dataone.org\/wp-json\/wp\/v2\/tags?post=1534"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}