The question is how much easier a traverser can become when there were dedicated hyper edges. In a binary relation it is fairly easy to define one end of the relation as the source and the other as the target (start and end node), but in n-ary relationships the roles of the attached nodes become more complicated.
Suppose we have the GIVES relationship, where one attached node takes the role of subject (the giver), one node takes the role of direct object (the gift), and another node takes the role of indirect object (the recipient). To traverse such a graph, we need to know these different roles, otherwise we may end up traversing the wrong nodes. Suppose we the following statements: John gives Paul a servant. Paul visited Albania. Paul's servant visited Albania. We now want to know all people that received a gift from John and who visited Albania. Without properly denoting the roles in the ternary relationship stated by "John gives Paul a servant", the answer to the query may well be: Paul and Paul's servant. Both are persons, both have visited Albania and both are part of the GIVES relationship defined. When we have to define the exact roles of each part of an n-ary relationship for each traversal, it is just as complicated as defining a traversal based on binary relationships, where different relationship types denote the roles of each part of the n-ary relationship. If hyperedges were to be introduced, either as a library or in core, the entire notion of the graph and how traversals are performed need to be rethought. The concept of an edge as having a start and an end node doesn't translate well into the world of hyper edges. There is not necessarily a start node and an end node, instead there are various nodes that are distinctly attached to the hyper edge. One way to think about an edge in both the graph and in the hypergraph world is as a tuple. A binary relationship can be thought of as the tuple: (node1, node2, RelationshipType, Set(property)) A ternary relationship can be thought of as the tuple: (node1, node2, node3, RelationshipType, Set(property)) etc... Instead of marking a binary relationship as outgoing or incoming, we can use the position in the tuple to denote its role. We can say the first node in the tuple corresponds to the start node, and the second node in the tuple corresponds to the end node. Having two possible permutations relates to the two possible directions an edge can have. Position based definitions of relationships translate well into the domain of n-ary relationships, though the semantics of such relationships can easily become difficult. A ternary relationship already has 6 permutations for the attached nodes, while a 10-ary relationship has 3,628,800 possible permutations. It would be an interesting project to design a tuple-position-based traverser. For binary relationships it should have the exact same features as the current direction based traverser, but it would be possible to generalize that design to n-ary relationships. This can all be done as a libary. Only when perfomance can be really improved in core, does it make sense to request for native support. Niels > Date: Sat, 16 Jul 2011 19:31:22 +0200 > From: [email protected] > To: [email protected] > Subject: Re: [Neo4j] Hyperedges and Objects > > That's clear. Such mappings are more difficult to traverse since the > traverser has to know if there is such a hyper edge vertex. I'm > wondering if there is no need to provide an embedded solution for such a > transformation. Each user who is confronted with hyper edges has to > implement some kind of such mapping. It would be helpful, for example, > if each Neo4j relationship can manage hyper edges automatically and > provide an additional 'isHyper' method pointing out that there are > additional methods allowing to get all further incident nodes. This is > also a matter of performance. I think such a handling is implemented > most efficiently within the Neo4j engine. > > Best regards > > Norbert Tausch > > Am 16.07.2011 00:52, schrieb Niels Hoogeveen: > > Hyper edges can be emulated. > > Suppose you want to store the fact "John gives Pete a book". > > This is indeed a ternary relationship, which would call for an hyper edge. > > This fact can be stored as follows: > > Some act of giving --Giver-->JohnSome act of giving --Recipient--> PeteSome > > act of giving --Gift--> book > > N-ary relationships can generally be decomposed into N binary > > relationships, where a central node is used to used as a placeholder for > > the N-ary relationship. > > Complex types can either be stored into a byte array or if appropriate in > > multiple properties. > > > > > >> Date: Sat, 16 Jul 2011 00:04:15 +0200 > >> From: [email protected] > >> To: [email protected] > >> Subject: [Neo4j] Hyperedges and Objects > >> > >> Hi, > >> > >> is there a possibility to store hyper edges in Neo4j? Is there a plan to > >> implement this? > >> > >> Will Neo4j get the ability to store complex types in addition to > >> primitve data types for properties of nodes and relationships? > >> > >> -- > >> Best regards > >> > >> Norbert Tausch > >> > >> _______________________________________________ > >> Neo4j mailing list > >> [email protected] > >> https://lists.neo4j.org/mailman/listinfo/user > > > > _______________________________________________ > > Neo4j mailing list > > [email protected] > > https://lists.neo4j.org/mailman/listinfo/user > _______________________________________________ > Neo4j mailing list > [email protected] > https://lists.neo4j.org/mailman/listinfo/user _______________________________________________ Neo4j mailing list [email protected] https://lists.neo4j.org/mailman/listinfo/user
