How pattern matching works?

[Martin Troup]

Hello to all!

I was looking at Traversal Framework Java API, but it is still not clear for me how pattern matching works...

1)

Let say I want to retrieve all general triangles like this: (a)—(b)—(c)—(a) from the database. How does that work? Does that mean I have to loop over all nodes in the database and in each iteration do depth-first search (or breadth-first search) with current node as start node and look for matches?

2)

What would be algorithmic complexity of finding all those triangles, or at best, of pattern matching in general?

Thanks so much for your reply!

[Sumit Gupta]

Hi Martin,

Did you consulted the Docs -

http://neo4j.com/docs/stable/tutorial-traversal-concepts.html

http://neo4j.com/docs/stable/tutorial-traversal-java-api.html. 

Traversal API defines various ways to include/ exclude nodes and various other critrieas to define the scope of your traversals.

Also for finding the distance between 2 given Nodes you can use different Graph Algorithms - http://neo4j.com/docs/stable/tutorials-java-embedded-graph-algo.html

Thanks,

Sumit

[Martin Troup]

Hi Sumit,

thanks for your reply at first!

I have went through the docs and I familiar with the way how to use the framework. But that was not my question.

Let me describe it in a better way and sorry for that confusion:

I want to know what exactly happens when I execute this cypher query: MATCH (a)--(b)--(c)--(a) RETURN a, b, c

At first I thought such query is somehow transformed in non-declarative way so Traversal API could handle it (thats why I have looked at the Traversal framework at the beginning). But maybe there is a different way how this query is actually processed.

I would like to know how the whole process of pattern matching works, so I can estimate its algorithmic complexity.

I am a student and I am currently writing a part of my master's thesis where I focus on algorithmic complexity of general pattern (meaning no specific information is added when querying) matching in Neo4j.

Dne úterý 19. května 2015 23:43:10 UTC+2 Sumit Gupta napsal(a):

[Michael Hunger]

Cypher doesn't use the traversal framework

it has its own operations (expand, expand(into), etc)  that, depending on your query, bound nodes and relationships, filters, and database statistics will combine differently into a query execution?

You see it best in the visual query plan of your query.

And in the manual: http://neo4j.com/docs/stable/execution-plans.html

Cheers, Michael

--
You received this message because you are subscribed to the Google Groups "Neo4j" group.
To unsubscribe from this group and stop receiving emails from it, send an email to neo4j+un...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Martin Troup]

Thanks Michael, that helps a lot!

One more question then. When I want to compare two Cypher queries that do the same thing... Is there any relevant metric I can use to compare those queries? So I can say which one is easier to execute? I have already measured execution time for both of them, but I would also like to compare how complex they are. Maybe total number of DbHits for each query? Would that be relevant?

Thanks, again, for your answer.

Dne středa 20. května 2015 10:17:52 UTC+2 Michael Hunger napsal(a):

[Michael Hunger]

If you run your queries with EXPLAIN you see estimated db-hits and estimated rows 

or with PROFILE you see also real db-hits and total db-hits

In the bin/neo4j-shell you get textual output and in browser visual output.

Michael