Preventing cycles in a neo4j graph where relationships are dated

[basefrequency]

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:

Max De Marzi – 26 Aug 15

Modeling Airline Flights in Neo4j

If you’ve come to any of the Neo4j Data Modeling classes I’ve taught, you’ve must have heard me say “your model depends on both your data and your queries” about a mil…

Max De Marzi – 24 May 17

Flight Search with Neo4j

I think I am going to take the opportunity to explain why I love graphs in this blog post. I’m going to try to explain why looking at problems from the graph point of view opens you up to cre…

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!