I recently took a small detour to learing about graph databases.
Here are some notes about my findings:
A friend of a friend (Donald), runs a business that sells school books to
various schools (both public and charter).
Just like any other business, he feels that he can improve his bottom line and
reaches out to me, a “Consultant” :) for help
Here are his primary set of questions:
- How much inventory should I keep?
- How can I track my sales in all states where I have stores?
- How can I analyze what books are sold in what markets?
- When should I use promotions?
- How can I negotiate my RMAs (Return to Manufacturer Agreements)?
We engage and here is what emerges:
- BOOKs are published by PUBLISHERs
- PUBLISHERs have PRINTING_PRESSes
- PRINTING_PRESSes exist in COUNTRYs
- BOOKs have a PACKAGING
- BOOKs have a COLOR
- Some BOOKS have a SHIPPING_POLICY
- All BOOKs sold are recorded as a TRANSACTION where attributes of the sale are recorded.
At this time I’m tempted to place this information in a fully normalized RDBMS
like MySQL or Oracle.
What would that entail? Perhaps this ERD will be a good indication:
Challenges
However, here are some challenges that we have to solve:
- Not all BOOKs have the same attributes. This will cause the BOOK table to be
sparsely populated.
- Since BOOKs arrive at different STOREs from several PRINTING_PRESSes
around the country, the Id’s of these books do not always sync up.
So, Harry Potter - The Deathly Hallows sold in Seattle may have a different
id that the same book sold in NewYork. Therefore, in the TRANSACTION table,
we cannot rely on the fact that the same ID will refer to the same book.
This causes reports (that are used by the PUBLISHERs for analysis) built off
of the TRANSACTION table, to be messed up.
- This equivalence of Ids is different for different PUBLISHERs. For example,
some PUBLISHERs
consider a blue Harry Potter - Deathly Hallows to be the same as a red book
by the same name, but some PUBLISHERs would like them to be treated separately.
- As more reading material is published, the attributes that need to be tracked
with each BOOK, keep changing.
As we can see, the above challenges can be solved using a RDBMS based storage
solution (and have been for years). But in this post, I’d like to suggest how to use a
combination of a Graph db and an RDBMS to reduce the pain in addressing these
challenges.
A Graph based solution
Approach:
First we will identify fact tables and dimension tables: Based on our model above,
it is obvious that the TRANSACTION table is our fact table and all others
would be dimension tables.
Then we will store all dimension data in a Graph db and store the transaction
data in an RDBMS.
The rationale for this is that dimensions are what Graphs are good at manipulating and
maintaining. There is not much churn on fact tables, but their normalized nature
tends to make them good candidates for the RDBMS.
Note that dimension tables tend to be smaller than fact tables in most domains.
But that has no bearing on the above strategy.
The implementation
We will use Neo4J for our Graph db and MySQL for our RDBMS.
Please download and install
neo4j (Should take ~ 5 mins!)
Then experiment with the sample movie db (should take no more than an hour max)
Then, in your browser at localhost:7474, copy and paste this into your command window and execute it.
CREATE (physicsPendulum: Book {id: '001', name: 'Physics Pendulum', price: 15})
CREATE (mathMayhem: Book {id: '002', name: 'Math Mayhem', price: 9})
CREATE (chemistryChaos: Book {id: '003', name: 'Chemistry Chaos', price: 11})
CREATE (trigTurpitude: Book {id: '004', name: 'Trignometry Turpitude', price: 17})
CREATE (theCornerPub: Publisher {id: '005', name: 'The Corner Pub'})
CREATE (theGoodPub: Publisher {id: '006', name: 'The Good Pub'})
CREATE (peteThePublisher: Publisher {id: '007', name: 'Pete the Publisher'})
CREATE (inBlackAndWhite: PrintingPress {id: '008', name: 'In Black And White'})
CREATE (theStencil: PrintingPress {id: '009', name: 'The Stencil'})
CREATE (featherAndInk: PrintingPress {id: '010', name: 'Feather And Ink'})
CREATE (gautemala: Country {id: '011', name: 'Gautemala'})
CREATE (syria: Country {id: '012', name: 'Syria'})
CREATE (red: Color {id: '013', name: 'red'})
CREATE (blue: Color {id: '014', name: 'blue'})
CREATE (green: Color {id: '015', name: 'green'})
CREATE (hardcover: Packaging {id: '016', name: 'Hardcover'})
CREATE (paperback: Packaging {id: '017', name: 'Paperback'})
CREATE (booksNThings: Store {id: '018', name: 'Books and Things', city: 'Pittsburgh', state: 'PA'})
CREATE (bookWorm: Store {id: '019', name: 'Book Worm', city: 'Anahiem', state: 'CA'})
CREATE (nerdCorner: Store {id: '020', name: 'Nerd Corner', city: 'Armadillo', state: 'TX'})
// Relationships
CREATE
(physicsPendulum)-[:PUBLISHED_BY]->(printedPurgatory),
(physicsPendulum)-[:REFLECTS]->(red),
(physicsPendulum)-[:PACKAGED_IN]->(hardcover),
(mathMayhem)-[:PUBLISHED_BY]->(onlyGoodBooks),
(mathMayhem)-[:REFLECTS]->(blue),
(mathMayhem)-[:PACKAGED_IN]->(hardcover),
(chemistryChaos)-[:PUBLISHED_BY]->(printedPurgatory),
(chemistryChaos)-[:REFLECTS]->(green),
(chemistryChaos)-[:PACKAGED_IN]->(paperback),
(trigTurpitude)-[:PUBLISHED_BY]->(peteThePublisher),
(trigTurpitude)-[:REFLECTS]->(red),
// Note that the trig book is in both packaging
(trigTurpitude)-[:PACKAGED_IN]->(hardcover),
(trigTurpitude)-[:PACKAGED_IN]->(paperback)
CREATE
(printedPurgatory)-[:PRINTS_AT]->(inBlackAndWhite),
(onlyGoodBooks)-[:PRINTS_AT]->(theStencil),
(peteThePublisher)-[:PRINTS_AT]->(featherAndInk)
CREATE
(inBlackAndWhite)-[:LOCATED_IN]->(gautemala),
(theStencil)-[:LOCATED_IN]->(gautemala),
(featherAndInk)-[:LOCATED_IN]->(syria)
CREATE
(physicsPendulum)-[:SOLD_IN]->(booksNThings),
(booksNThings)-[:SELLS]->(physicsPendulum),
(mathMayhem)-[:SOLD_IN]->(bookWorm),
(bookWorm)-[:SELLS]->(mathMayhem),
(chemistryChaos)-[:SOLD_IN]->(booksNThings),
(booksNThings)-[:SELLS]->(chemistryChaos),
(trigTurpitude)-[:SOLD_IN]->(nerdCorner),
(nerdCorner)-[:SELLS]->(trigTurpitude)
By doing above we have created the Dimension entities in the Graph Db and also used the data
to establish relationship between them.
Let’s query and see what we have got so far:
Run the following to view the schema:
call db.schema;
This yields:
But since we don’t have much data, we can actually pull the entire dataset and view
relationships (without blowing up the browser!):
The first thing to notice is that the optional “properties” of color and
packaging is handled via a relationship instead of as an inline property of
the book (such as is the case with price).
Now let’s create the TRANSACTION table in MySQL.
Please create a database and run the appropriate DDL and INSERT statements to yield
the following data in the TRANSACTION table:
id bookId, qty, price, storeId
1 001 2 10.00 020
2 002 3 11.50 030
3 003 4 12.5 040
4 001 3 36.00 030
5 002 4 54.00 040
6 002 1 05.00 020
So now let us address the problem where the blue and red Harry Potter books are the
same for PUBLISHER1 but different for PUBLISHER2
For PUBLISHER1 book 001 and book 002 are euivalent
For PUBLISHER2 book 002 and 003 are equivalent.
This Cypher statement will establish that equivalence:
MATCH (b:Book {id: '001'})-[*]-(c: Book {id: '002'})
MERGE (b)-[e: EQUIVALENT {publisher: 'PUBLISHER1', equivalentId: '1001'}]->(c)
MATCH (b:Book {id: '002'})-[*]-(c: Book {id: '003'})
MERGE (b)-[e: EQUIVALENT {publisher: 'PUBLISHER2', equivalentId: '1002'}]->(c)
Notice how we have:
- Created publisher-specific relationships
- Identified the equivalent id for each pair in the relationship properties and
associated it to the relationship.
This yields the following schema:
And the same relationship is displayed with the data:
Querying
Now let’s see how we can write queries for the two publishers using this equivalence
relationship and the transaction data stored in a relational db.
First pull dimension data using Neo4J for PUBLISHER1.
MATCH (b1: Book)-[r1]-(b2: Book), (b: Book)-[*]-(p)-[*]-(r)-[*]-(c: Country)
WHERE r1.publisher = 'PUBLISHER2'
RETURN DISTINCT b1, b2, r1.equivalentId, b, p, r, c;
Fact data that is stored in MySQL can be accessed in either of two ways:
- Use the JDBC plugin for Neo4J to make a direct connection .
- Use the Neo4J API to programatically access data.
Here’s an example of how this model can be queried using plain Cypher querries:
Give me all books that are red in color, printed in Gautemala, sold in PA and cost
more than $10.00
MATCH (b:Book)-[:PUBLISHED_BY]->()-[:PRINTS_AT]->()-[:LOCATED_IN]->(c:Country),
(b:Book)-[:REFLECTS]-(r:Color),
(b:Book)-[:SOLD_IN]->(s:Store)
WHERE c.name = 'Gautemala'
AND b.price > 10
AND r.name = 'red'
AND s.state = 'PA'
RETURN b;
CREATE (easyPeasy:ShippingPolicy {id: '021', name: 'The Easy Policy'})
CREATE (hardAsNails:ShippingPolicy {id: '022', name: 'The Hard Policy'})
MATCH (b:Book)-[:PUBLISHED_BY]->()-[:PRINTS_AT]->()-[:LOCATED_IN]->(c:Country)
WHERE c.name = 'Gautemala'
CREATE
(b)-[:GOVERNED_BY]->(s:ShippingPolicy)
But now delete relationship at schema level
MATCH (a)-[r:GOVERNED_BY]->(b)
DELETE r;
And create the same at data level (for specific data that meets a condition):
MATCH (b:Book)-[:PUBLISHED_BY]->()-[:PRINTS_AT]->()-[:LOCATED_IN]->(c:Country)
MATCH (p:ShippingPolicy)
WHERE c.name = 'Gautemala'
AND p.name = 'The Easy Policy'
CREATE
(b)-[:GOVERNED_BY]->(p)
MATCH (b:Book)-[:PUBLISHED_BY]->()-[:PRINTS_AT]->()-[:LOCATED_IN]->(c:Country)
MATCH (p:ShippingPolicy)
WHERE c.name = 'Syria'
AND p.name = 'The Hard Policy'
CREATE
(b)-[:GOVERNED_BY]->(p)
