cancel
Showing results for 
Search instead for 
Did you mean: 

Preventing cycles in a neo4j graph where relationships are dated

I'm brand new to graph databases, but I'm trying to understand if a graph database is suited for my problem. Here we go!


I have a set of users who can relate to each other via a "Parent" relationship (i.e., they can be built into a tree / hierarchy). The "Parent" relationship from one user to another is said to "begin" as of a certain date, and the relationship only "ends" if/when another "Parent" relationships exists between the same users and with a later date.


Every user can have <= 1 parent as of any particular date, and can have >=0 children. I.e., at most one parent at a time, and no limit to the number of children.


I've read blog posts dealing with dated relationships, but they don't seem to address this level of complexity:

My challenge:

For a given set of users with existing "Parent" relationships, determine whether a new "Parent" relationship can be added "as of" a certain date WITHOUT creating a cycle anywhere in the timeline.


To help visualize an example, imagine we have four users Alice, Bob, Carlos, and David.


User Date Parent
Alice 09/13/2012 Bob
Alice 04/01/2021 David
Bob 01/31/2020 Carlos
Carlos 02/14/2008 David


Here is a (highly abstract) picture representing the current state of the data (time flows to the right):

https://i.stack.imgur.com/qdcbL.png


So in this example Alice has Bob as a parent from 9/13/2012 until 4/1/2021, at which point she begins to have David as a parent. Bob has no parent until 1/31/2020, at which point he gets Carlos as a parent. Etc.


I need to be able to determine whether an update/insert will create a cycle in the "parent" hierarchy at any point in time . So, for example, I'd like to be able to determine that it would be INVALID to set Carlos's parent to be Alice as of 10/22/2020 because then there would be a cycle in the hierarchy for the period between 10/22/2020 and 4/1/2021 (i.e., Alice-->Bob-->Carlos-->Alice). To help visualize it:

https://i.stack.imgur.com/xA2vv.png


But I also need to be able to determine that it would be VALID to set Carlos's parent to Alice as of 10/22/2021, as drawn here:

https://i.stack.imgur.com/9u0P4.png


In terms of modeling the data, I started by thinking of two different models.

First try:

I tried having my only nodes be "Users," and having my "Parent" relationships include a date in the relationship type. Since the range of dates is huge and the dates themselves are not known in advance, I'm not sure this is a good idea but decided to give it a shot anyway.




Cypher:

CREATE (n0:User {name: "Alice"})-[:P_2012_09_13]->(:User {name: "Bob"})-[:P_2020_01_31]->(:User {name: "Carlos"})-[:P_2008_02_14]->(:User {name: "David"})<-[:P_2021_04_01]-(n0)

Second try:

I tried creating "UserDay" nodes to capture the date element, thereby reducing the range of relationship types to only two (i.e., a 1:many "HAS" relationship from User to UserDay, then a 1:1 "P" relationship from UserDay to User).




Cypher:

CREATE (n8:UserDay {date: "2021-04-01"})<-[:HAS]-(:User {name: "Alice"})-[:HAS]->(:UserDay {date: "2012-09-13"})-[:P]->(:User {name: "Bob"})-[:HAS]->(:UserDay {date: "2020-01-31"})-[:P]->(:User {name: "Carlos"})-[:HAS]->(:UserDay {date: "2008-02-14"})-[:P]->(:User {name: "David"})<-[:P]-(n8)

Given a source User, destination User, and start date, I need to be able to determine if a cycle would be created in the hierarchy for any time in the timeline.

Carlos, Alice, 10/22/2020: should be INVALID
Carlos, Alice, 10/22/2021: should be VALID

I've been spinning my wheels reading through neo4j docs and googling, and finally decided to ask my very first question! Please let me know if you have any questions or if anything I've said is unclear.

Thanks in advance!
0 REPLIES 0
Nodes 2022
Nodes
NODES 2022, Neo4j Online Education Summit

On November 16 and 17 for 24 hours across all timezones, you’ll learn about best practices for beginners and experts alike.