Hi Michael,I realize that the implementation of IndexedRelationship can in fact support returning relationships, and I have a preliminary version running locally now.The returned relationships can support all methods of the Relationship interface, returning the node pointing to the treeRoot as the startNode, and returning the node set as the key_value as the endNode.All relationship properties will be stored on the KEY_VALUE relationship pointing to the endNode.There is one caveat to this solution, the returned relationships cannot support the getId() method,and will throw an UnsupportedOperationException when being called.IndexedRelationship will implement Iterable<Relationship>.With these changes, it is possible to create an Expander and I am working right now to implement that.Niels
> From: pd_aficion...@hotmail.com > To: user@lists.neo4j.org > Date: Thu, 7 Jul 2011 14:46:35 +0200 > Subject: Re: [Neo4j] Indexed relationships > > > Hi Michael, > > I haven't yet worked on an example. > > There are tests for the SortedTree implementation, > but didn't add those to the IndexedRelationship class, > which is simply a wrapper around SortedTree. > Having a test would have caught the error > that no relationship to the treeNode was created > (fixed that bug and pushed it to Git) > (note to self: always create a unit test, > especially when code seems trivial). > > There is no relationship expander that uses this. > The RelationshipExpander has a method Iterable<Relationship> expand(Node > node) > which cannot be supported, since there is no direct relationship from > startnode to endnode. > Instead there is a path through the index tree. > > It's not possible to support the original relationship-traversal API > since the IndexedRelationship class is not a wrapper around a node, > but a wrapper around the relationships of a certain RelationshipType in the > OUTGOING direction. > > As to the name of the class. > It is essentially an indexed relationship, > and not just a solution to the densely-connected-node problem. > An indexed relationship can also be used to maintain > a sorted set of relationships of any size, > and can be used to guarantee unicity constraints. Niels > > From: michael.hun...@neotechnology.com > > Date: Thu, 7 Jul 2011 13:27:00 +0200 > > To: user@lists.neo4j.org > > Subject: Re: [Neo4j] Indexed relationships > > > > Good work, > > > > do you have an example ready (and/or some tests that show how it works/is > > used) ? > > > > In creation, manual traversal and automatic traversal (i.e. is there a > > RelationshipExpander that uses it). > > > > And in the constructor if there is no relationship to the treeNode, you > > create a new one, but that new treeNode is not connected to the actual node? > > > > I'm not sure if it should support the original relationship-traversal API / > > methods (getRelationships(Dir,type), etc). > > > > Perhaps that IndexedRelationship should rather be just a wrapper around a > > SuperNode ? So probably rename it to "SuperNode(Wrapper) or > > HeavilyConnectedNode(Wrapper) ?) > > > > Cheers > > > > Michael > > > > Am 07.07.2011 um 12:51 schrieb Niels Hoogeveen: > > > > > > > > Finished the implementation of indexed relationships. The graph > > > collections component now contains the package > > > https://github.com/peterneubauer/graph-collections/tree/master/src/main/java/org/neo4j/collections/indexedrelationship, > > > containing the IndexedRelationship class. > > > This class can be used instead of regular relationships > > > when:relationships need to be stored in a particular sort ordera unicity > > > constraint needs to be guaranteed nodes become densely populated with > > > relationships. > > > The implementation is traverser friendly. Given a start nodes all end > > > nodes can be found by following four relationships types in outgoing > > > direction. Given an end node the start node can be found by following > > > these four relationship types in incoming direction. Of course this > > > functionality is also covered in the API. > > > Niels > > > > > >> From: pd_aficion...@hotmail.com > > >> To: user@lists.neo4j.org > > >> Date: Thu, 7 Jul 2011 02:36:29 +0200 > > >> Subject: Re: [Neo4j] Indexed relationships > > >> > > >> > > >> Pushed SortedTree to Git after adding a unit test and doing some > > >> debugging. > > >> TODO:Add API for indexed relationships using SortedTree as the > > >> implementation.Make SortedTree thread safe. > > >> With regard to the latter issue. I am considering the following > > >> solution. Acquire a lock (delete a non existent property) on the node > > >> that points to the root of the tree at the start of AddNode, RemoveNode > > >> and Delete. No other node in the SortedTree is really stable, even the > > >> rootnode may be moved down, turning another node into the new rootnode, > > >> while after a couple of remove actions the original rootnode may even be > > >> deleted. > > >> Locking the node pointing to the rootnode, prevents all other > > >> threads/transactions from updating the tree. This may seem restrictive, > > >> but a single new entry or a single removal may in fact have impact on > > >> much of the tree, due to balancing. More selective locking would require > > >> a prebalancing tree walk, determining the affected subtrees, lock them > > >> and once every affected subtree is locked, perform the actual balancing. > > >> Please let me hear if there are any objections to locking the node > > >> pointing to the tree as the a solution to make SortedTree thread safe. > > >> Niels > > >> > > >>> Date: Tue, 5 Jul 2011 08:27:57 +0200 > > >>> From: neubauer.pe...@gmail.com > > >>> To: user@lists.neo4j.org > > >>> Subject: Re: [Neo4j] Indexed relationships > > >>> > > >>> Great work Nils! > > >>> > > >>> /peter > > >>> > > >>> Sent from my phone. > > >>> On Jul 4, 2011 11:39 PM, "Niels Hoogeveen" <pd_aficion...@hotmail.com> > > >>> wrote: > > >>>> > > >>>> Made some more changes to the SortedTree implementation. Previously > > >>> SortedTree would throw an exception if a duplicate entry was being > > >>> added. > > >>>> I changed SortedTree to allow a key to point to more than one node, > > >>>> unless > > >>> the SortedTree is created as a unique index, in which case an exception > > >>> is > > >>> raised when an attempt is made to add a node to an existing key entry. > > >>>> A SortedTree once defined as unique can not be changed to a non-unique > > >>> index or vice-versa. > > >>>> SortedTrees now have a name, which is stored in the a property of the > > >>> TREE_ROOT relationship and in the KEY_VALUE relationship (a new > > >>> relationship > > >>> that points from the SortedTree to the Node inserted in the > > >>> SortedTree). The > > >>> name of a SortedTree can not be changed. > > >>>> SortedTrees now store the class of the Comparator, so a SortedTree, > > >>>> once > > >>> created, can not be used with a different Comparator. > > >>>> SortedTree is now an Iterable, making it possible to use it in a > > >>> foreach-loop. > > >>>> Since there are as of yet, no unit tests for SortedTree, I will create > > >>> those first before pushing my changes to Git. Preliminary results so > > >>> far are > > >>> good. I integrated the changes in my own application and it seems to > > >>> work > > >>> fine. > > >>>> Todo: > > >>>> Decide on an API for indexed relationships. (Community input still > > >>> welcome).Write unit tests.Make SortedTree thread safe (Community help > > >>> still > > >>> welcome). > > >>>> Niels > > >>>> > > >>>>> From: pd_aficion...@hotmail.com > > >>>>> To: user@lists.neo4j.org > > >>>>> Date: Mon, 4 Jul 2011 15:49:45 +0200 > > >>>>> Subject: Re: [Neo4j] Indexed relationships > > >>>>> > > >>>>> > > >>>>> I forgot to add another recurrent issue that can be solved with > > >>>>> indexed > > >>> relationships: guaranteed unicity constraints. > > >>>>>> From: pd_aficion...@hotmail.com > > >>>>>> To: user@lists.neo4j.org > > >>>>>> Date: Mon, 4 Jul 2011 01:55:08 +0200 > > >>>>>> Subject: [Neo4j] Indexed relationships > > >>>>>> > > >>>>>> > > >>>>>> In the thread [Neo4j] traversing densely populated nodes we discussed > > >>> the problems arising when large numbers of relationships are added to > > >>> the > > >>> same node. > > >>>>>> Over the weekend, I have worked on a solution for the > > >>> dense-relationship-nodes using SortedTree in the neo-graph-collections > > >>> component. After some minor tweaks to the implementation of SortedTree, > > >>> I > > >>> have managed to get a workable solution, where two nodes are not > > >>> directly > > >>> linked by a relationship, but by means of a BTree (entirely stored in > > >>> the > > >>> graph). > > >>>>>> Before continuing this work, I'd like to have a discussion about > > >>> features, since what we have now is not just a solution for the dense > > >>> populated node issue, but is actually a full fledges indexed > > >>> relationship, > > >>> which makes it suitable for other purposes too. > > >>>>>> An indexed relationship can for example be used to maintain a sorted > > >>> set of relationships in the graph, that is not necessarily huge, but > > >>> large > > >>> enough to make sorting on internal memory too expensive an operation, or > > >>> situations where only one out of a large number of relationships is > > >>> actually > > >>> traversed in most cases. > > >>>>>> There are probably more use cases for in-graph indexed relationships, > > >>> so I'd like to know what features are desirable and what API would Neo4J > > >>> users appreciate. > > >>>>>> P.S. I still think it would be good to consider, if technically > > >>> possible, partitioning the relationship store per relationship type and > > >>> per > > >>> direction. The indexed relationship solution works, but is of course > > >>> slower > > >>> than a direct relationship, both with respect to insert time and > > >>> traversal > > >>> time. If dense relationships are never traversed going out of the dense > > >>> node, the extra structure maintained by the BTree is only extra burden. > > >>>>>> P.P.S. If there are people with experience to make an implementation > > >>> thread safe, please volunteer to help make the implementation production > > >>> proof. > > >>>>>> Niels > > >>>>>> _______________________________________________ > > >>>>>> Neo4j mailing list > > >>>>>> User@lists.neo4j.org > > >>>>>> https://lists.neo4j.org/mailman/listinfo/user > > >>>>> > > >>>>> _______________________________________________ > > >>>>> Neo4j mailing list > > >>>>> User@lists.neo4j.org > > >>>>> https://lists.neo4j.org/mailman/listinfo/user > > >>>> > > >>>> _______________________________________________ > > >>>> Neo4j mailing list > > >>>> User@lists.neo4j.org > > >>>> https://lists.neo4j.org/mailman/listinfo/user > > >>> _______________________________________________ > > >>> Neo4j mailing list > > >>> User@lists.neo4j.org > > >>> https://lists.neo4j.org/mailman/listinfo/user > > >> > > >> _______________________________________________ > > >> Neo4j mailing list > > >> User@lists.neo4j.org > > >> https://lists.neo4j.org/mailman/listinfo/user > > > > > > _______________________________________________ > > > Neo4j mailing list > > > User@lists.neo4j.org > > > https://lists.neo4j.org/mailman/listinfo/user > > > > _______________________________________________ > > Neo4j mailing list > > User@lists.neo4j.org > > https://lists.neo4j.org/mailman/listinfo/user > > _______________________________________________ > Neo4j mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user _______________________________________________ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
