Hi, a graph homomorphism is a mapping (a function) that maps the vertices of a single source graph to the vertices of a single target graph such that whenever two vertices are adjacent in the source graph it holds that their mapped counterparts in the target graph will be adjacent, too (Neighbors stay neighbors under the mapping).
Notice that this only has to work in one direction. If the mapping works in both directions, it is both a graph homomorphism and a graph isomorphism. The term "graph query" is commonly used synonymously with subgraph matching. Subgraph matching boils down to finding all subgraphs that have a certain structure and possibly fulfill some additional criteria. This can be understood as finding all graph homomorphisms from the request (or query) graph (which serves as an abstract description of what the user is looking for) to the actual data graph (i.e. the graph database content). In actual query processing, this may be followed by additional filtering or by combining the results of multiple subgraph matching steps. These theoretical terms do ignore practical issues like properties and indices. I think it is valid to say that a graph traversal corresponds to matching a *connected* query graph and that relies on indices to limit the number of vertices that need to be searched, both for practical and performance reasons. Additionally, with a query language like cypher, multiple such traversals may be filtered and combined. To answer your question: A homomorphism does not take a request graph as input, instead a request graph describes a family (a set) of graph homomorphisms that each take request graph vertices as inputs and map them to data graph vertices. Applying a graph traversal computes the set of graph homomorphisms of the traversal's request graph against the current data graph. Hope this helps, Stefan Plantikow PS: In a way this ignores indices again. Taking that into account, applying a graph traversal may be understood as computing a set of request graphs (based on index content at the time of query instantiation) and finding the union of all those request graph's graph homomorphisms to the data graph. In the end, all this is very definition dependent. PPS: Not addressed here but related is the question of what kind of request graphs can be expressed with a single query/graph traversal and therefore what kind of graph homomorphisms may be found. This is naturally limited by what can be implemented efficiently. -- View this message in context: http://neo4j-community-discussions.438527.n3.nabble.com/Neo4j-Graph-homomorphism-vs-Graph-traversal-tp3390663p3391344.html Sent from the Neo4j Community Discussions mailing list archive at Nabble.com. _______________________________________________ Neo4j mailing list [email protected] https://lists.neo4j.org/mailman/listinfo/user
