GraphGists

Introduction

Here I tell you a story to present a solution to an everyday problem. How many times it happens that you go for a travel in the hyperspace with other rebels, you go on a mission with a couple of Jedi or, in general, you do something together with other people with which you have to share expenses?

Often in those situations it happens that there is someone owing money to someone else owing money to the first.

Here I present the story of how the Republic solved the issue in an elegant way using Neo4j.

The story

A long time ago in a galaxy far far away there were four people travelling together to save the republic.

They were brave but tolls and gasoline for the hyperspace are not for free; they weren’t rich and didn’t have a centralised financial system but rather a distributed one made by their savings.

Luckily they had in addition to Force also a Neo4j database to take care of this distributed finance.

So there were Rey the brave Jedi girl, Finn the repentant, Han the history and Chewbacca the furry alien.

They had a mission: get from the Neo4j planet the technology to manage the finances of the Republic and find a way to use it in the right way.

The first bit was easy, they got to the planet with a USB key and got the database, but they had to find a way to use it in the right way to solve Organa’s problem. They decided to make a small experiment with their return journey.

Before departing they added themselves to the database as nodes with their names as properties and labelised as `Friend`s.

CREATE (f:Friend {name:'Rey'}) RETURN f;
CREATE (f:Friend {name:'Finn'}) RETURN f;
CREATE (f:Friend {name:'Han'}) RETURN f;
CREATE (f:Friend {name:'Chewbacca'}) RETURN f;

Then they had to fill the fuel tanks so Han put 1000 republic credits (from now we’ll call them £) of gasoline in the Millenium Falcon, this way the others owed him 250£ each (1000 / 4 = 250).

They decided to represent as Expense nodes the 250£ and the relationship between the crewmen and Han is a Credit node containing the total amount of the money owed to the creditor - in this case 250£ -. Each Credit is linked to the creditor through a :CREDIT relationship and to the debitor through a :DEBIT relationship. In Cypher, with Han as a creditor and Rey as a debitor is:

MATCH (creditor:Friend {name:'Han'}), (debitor:Friend {name:'Rey'})
CREATE UNIQUE (creditor)-[:CREDIT]->(c:Credit {Creditor: creditor.name, Debitor: debitor.name})-[:DEBIT]->(debitor)
CREATE UNIQUE (c)<-[:EXPENSE]-(exp:Expense {Creditor: creditor.name, Debitor: debitor.name, Amount: 250, Description: 'Fuel Millenium Falcon'})
WITH c
MATCH (c)<-[:EXPENSE]-(exp)
WITH c, SUM(exp.Amount) AS total
SET c.Amount = total;
MATCH (creditor:Friend {name:'Han'}), (debitor:Friend)
WHERE debitor.name IN ['Finn', 'Chewbacca']
CREATE UNIQUE (creditor)-[:CREDIT]->(c:Credit {Creditor: creditor.name, Debitor: debitor.name})-[:DEBIT]->(debitor)
CREATE UNIQUE (c)<-[:EXPENSE]-(exp:Expense {Creditor: creditor.name, Debitor: debitor.name, Amount: 250, Description: 'Fuel Millenium Falcon'})
WITH c
MATCH (c)<-[:EXPENSE]-(exp)
WITH c, SUM(exp.Amount) AS total
SET c.Amount = total;

that becomes for all the group:

MATCH (n)
RETURN n

After the fuel they started the journey but after a while it becomes lunch time so they stopped to a service area where Chewbacca got some Quarren food for 80£.

In the same way they added the expense to their Neo4j database so they owed Chewbacca 20£ each:

At this point there is an interesting poing: Chewbacca owes 250£ to Han and Han owes 20£ to Chewbacca. This means their credits are linked.

MATCH p=(c:Friend {name:'Chewbacca'})-[:CREDIT|DEBIT*2]-(h:Friend {name:'Han'})
RETURN p

They wanted to describe this link so they defined a relationship between two credits of the same person as a :CHAIN, this states there is a money flow between his inbound and outbound credits.

In this case we have a :CHAIN relationship between Han’s debit and credit, and the same is for Chewbacca:

MATCH (credit:Credit)<-[:CREDIT]-(creditor:Friend {name:'Han'})<-[:DEBIT]-(debit :Credit)
MERGE (credit)<-[chain:CHAIN]-(debit);

MATCH (credit:Credit)<-[:CREDIT]-(creditor:Friend {name:'Chewbacca'})<-[:DEBIT]-(debit :Credit)
MERGE (credit)<-[chain:CHAIN]-(debit);

(Here there is the link to a clear picture of the model unfortunately I’ve not been able to link to Dropbox image :( )

Here starts the magic because they discover they can ask Neo4j to find if there is a compensation between credits and settle them up:

MATCH (creditor:Friend {name:'Chewbacca'})-[:CREDIT]->(credit:Credit),
p = (credit)-[:CHAIN*1..]->(credit)
WITH TAIL(NODES(p)) AS ns, credit

WITH ns,
	SIZE(ns) AS Chain_length,
    extract(x IN ns | x.Creditor) AS People_involved,
    REDUCE(comp = credit.Amount, n in ns | CASE WHEN comp < n.Amount THEN comp ELSE n.Amount END) AS Compensation
WHERE Compensation > 0
FOREACH (credit in ns| SET credit.Amount = credit.Amount - Compensation)
RETURN Chain_length, People_involved, Compensation;

In this case there was a compensation of 20£ between Chewbacca and Han following a chain of length 2. The query MATCH started from Chewbacca because his last credit update could have arisen a chain.

Till here it’s trivial but lets go forward with the story to see the power of the tool.

After they resumed the journey they encountered a meteor shower that damaged the shields.

So they went to get a mechanical part to replace the broken one and Rey paid 1200£ (300£ each).

This complicates some more the network because they got some more compensations:

MATCH (creditor:Friend)-[:CREDIT]->(credit:Credit),
p = (credit)-[:CHAIN*1..]->(credit)
WITH TAIL(NODES(p)) AS ns, credit

WITH ns,
	SIZE(ns) AS Chain_length,
    extract(x IN ns | x.Creditor) AS People_involved,
    REDUCE(comp = credit.Amount, n in ns | CASE WHEN comp < n.Amount THEN comp ELSE n.Amount END) AS Compensation
WHERE Compensation > 0 AND
ALL(n in People_involved where
          1=length(filter(m in People_involved where m=n)))
RETURN Chain_length, People_involved, Compensation
ORDER BY Compensation DESC, Chain_length DESC

Now there is the tricky part: we’ve got different chains with different compensation values but with some credit nodes in common. This doesn’t allow us to compensate everything like we did for Chewbacca and Han. We have to proceed with caution compensating one chain at time. The best soultion possible is the one compensating the most with the maximum chain length (when the compensating value is the same it’s better to satisfy the highest number of people).

MATCH (creditor:Friend)-[:CREDIT]->(credit:Credit),
p = (credit)-[:CHAIN*1..]->(credit)
WITH TAIL(NODES(p)) AS ns, credit

WITH ns,
	SIZE(ns) AS Chain_length,
    extract(x IN ns | x.Creditor) AS People_involved,
    REDUCE(comp = credit.Amount, n in ns | CASE WHEN comp < n.Amount THEN comp ELSE n.Amount END) AS Compensation
WHERE Compensation > 0 AND
ALL(n in People_involved where
          1=length(filter(m in People_involved where m=n)))

WITH Chain_length, People_involved, Compensation, ns
ORDER BY Compensation DESC, Chain_length DESC
LIMIT 1
FOREACH (credit in ns| SET credit.Amount = credit.Amount - Compensation)
RETURN Chain_length, People_involved, Compensation

Going on with the story, once they’ve got the shield parts they go to a mechanic and Finn pays for the job 600£ (150£ each), that they add to the system.

In the meanwhile Chewbacca and Han decide to get a Bantha Milk Cocktail and a Jedi Beer to the Cantina where Chewbacca pays 50£ for the two (25£ each).

Again the database comes to help and finds some compensations to flatten credits.

MATCH (creditor:Friend)-[:CREDIT]->(credit:Credit),
p = (credit)-[:CHAIN*1..]->(credit)
WITH TAIL(NODES(p)) AS ns, credit

WITH ns,
	SIZE(ns) AS Chain_length,
    extract(x IN ns | x.Creditor) AS People_involved,
    REDUCE(comp = credit.Amount, n in ns | CASE WHEN comp < n.Amount THEN comp ELSE n.Amount END) AS Compensation
WHERE Compensation > 0 AND
ALL(n in People_involved where
          1=length(filter(m in People_involved where m=n)))

WITH Chain_length, People_involved, Compensation, ns
ORDER BY Compensation DESC, Chain_length DESC
LIMIT 1
FOREACH (credit in ns| SET credit.Amount = credit.Amount - Compensation)
RETURN Chain_length, People_involved, Compensation

And running the query many times they get to a point where everything gets compensated.

MATCH (creditor:Friend)-[:CREDIT]->(credit:Credit),
p = (credit)-[:CHAIN*1..]->(credit)
WITH TAIL(NODES(p)) AS ns, credit

WITH ns,
	SIZE(ns) AS Chain_length,
    extract(x IN ns | x.Creditor) AS People_involved,
    REDUCE(comp = credit.Amount, n in ns | CASE WHEN comp < n.Amount THEN comp ELSE n.Amount END) AS Compensation
WHERE Compensation > 0 AND
ALL(n in People_involved where
          1=length(filter(m in People_involved where m=n)))

WITH Chain_length, People_involved, Compensation, ns
ORDER BY Compensation DESC, Chain_length DESC
LIMIT 1
FOREACH (credit in ns| SET credit.Amount = credit.Amount - Compensation)
RETURN Chain_length, People_involved, Compensation
MATCH (creditor:Friend)-[:CREDIT]->(credit:Credit),
p = (credit)-[:CHAIN*1..]->(credit)
WITH TAIL(NODES(p)) AS ns, credit

WITH ns,
	SIZE(ns) AS Chain_length,
    extract(x IN ns | x.Creditor) AS People_involved,
    REDUCE(comp = credit.Amount, n in ns | CASE WHEN comp < n.Amount THEN comp ELSE n.Amount END) AS Compensation
WHERE Compensation > 0 AND
ALL(n in People_involved where
          1=length(filter(m in People_involved where m=n)))

WITH Chain_length, People_involved, Compensation, ns
ORDER BY Compensation DESC, Chain_length DESC
LIMIT 1
FOREACH (credit in ns| SET credit.Amount = credit.Amount - Compensation)
RETURN Chain_length, People_involved, Compensation

They knew this technoloy was the beginning of the new revolution. This could really simplify all the financial system of the rebels and save a lot of money and time.

They flew to their planet and illustrated their discovery to Organa general.

The rest of the story is well known but until this moment no one explained how the poor rebels managed their money in such a sparse republic.

Future developments

In my work I explain a way to compensate chains that is a little bit mechanical but I’m quite confident there are better ways to do it. First of all it would be really interesting to describe a query to compensate all disjointed sub networks, furthermore it would be nice to find a way to compensate everything all at once.

Conclusions

This was a fun story to explain a use case were graph databases really can do their best, it is possible to describe such an intrinsecally interconnected network and perform very descriptive queries on the data. My job is just an approach to the problem of finding subnetworks sharing credits and could be an idea to develop a distributed economical system. I really have to thank Neo4j because its approach to the description of connected data opens the way of thinking and allowes to have better insights of the real value of the information.