Normalizing property graph databases
Graph Data Modeling and Normalization
I see Graph Databases as the Relational Databases of the future. But I find it odd that there is virtually little to no best practices guide and modeling patterns out there. With the emergence of property graphs, the extra capabilities makes it possible to encode the same information in many graph forms. 
  Pre-reqs 
  Even though basic graph and relational database knowledge is required, it would be better if the reader is somewhat familiar with property graph databases, semantic graphs, normalization of relational databases (normal forms, transitive relationships, etc.) and RDF's. 
  Normalization in Graph vs. Relational Databases 
  Database normalization generally serves these purposes: 
   
   Reduces the size of data by reducing or eliminating redundancies 
   Improve Data integrity 
   Improves graph query performance in index-free adjacency graph engines 
   Simplifies incremental modeling 
   
  Like relational databases, graph databases are built on the concept of relations between entities (tables in relational, vertexes in graph). For that reason, all of the normalization techniques that apply to relational databases also apply for property graph databases. But with all the similarities, the two models are still different. So once more we must come up with new graph normalization concepts from the ground up. I'll have the first crack at it 
  The Entity Model 
  Lets see a conceptual entity data model 
   
   
  Figure 1 
  The blue diamonds represent relationships, the pipe represent connections, the grey boxes represent entities, and the green oval represents properties (1). Now, how do we put this model in a graph database. We are going to assume that we are using a property graph database and not an RDF store type database. The physical model might look as follows 
   
   
  Figure 2 
  In (2), The first line is represented by the pair of <id >:<Type>. The following lines represent properties in <key>:<value> format. 
  What is wrong with that picture? 
  First, assume the name of the person doesn't need decomposition and that the entity is in 1NF. The first thing we need to separate is the partial dependency in the relationship by creating two separate relations. We'll have the model in 3NF 
   
   
  Figure 3 
  Now that we have this model (3) in 3NF, lets call it Edge Normalized. 
  "Lost Identity" 
  Adding properties to graphs just makes it a multi-model database. it reminds me of PosgreSQL adding JSON support just to compete with NoSQL document databases. So lets make our data model more graph like. We need to make our entities value objects (Objects that represent one value). Why you may say? what if i wanted to query people who are 20 years of age for example without a full scan or creating an index on the name? the power of both graph and SQL databases lies with the ability to make adhoc queries and we'll take full advantage of it that way. 
   
   
  Figure 4 
  Now, lets look at the grey and green entities only in (4) (notice that i added in red text a new relationship to show future proofing in this model). They have Labels, values and no Unique ID's. Age for example is indexed by number of years (4). There is one value of the age 28. green and grey entities are Global Value Singletons. That allows us to make adhoc queries in the future without worry. 
  The Blue Box 
  Lets talk about the blue boxes. They represent Connecting Entities that are more closer to a relationship. Unlike value singletons, they have two associated values, a unique ID, and a value. We will find those types of relationships common in Weighted/Valued Many to Many relationships. The yellow highlighted ID key is not a meaningful value of an entity (4) (5). We mean that in different databases, they can have different values as long as they are unique. Value singletons however will have the same value across databases. Some connecting entities can have more than one value. for example: 
   
   
  Figure 5 
  :Friendship is a connecting entity that can have more than one property (5). However in the :Experience entity (4), the unit of years is the only value that we can measure experience with. 
  The good news is that the previous two graphs are in 5NF. Lets give it a "graphy" name also. Lets call it Vertex Normalized Graph. 
  Can We Do Better? 
  This next idea works only in property graphs so it will not apply to RDF style databases. 
  Behold, the AA Normalized Graph 
   
   
  Figure 6 
  In this graph (6), we introduce the concept of a Value Edge. Notice that we no longer have connecting entities. Value edges greatly reduce the number of normalized relationships but without sacrificing the information and readability of graphs. So if you have a property graph database, it would be ideal to have it in this format. 
  Tradeoffs 
  Since life is about tradeoffs, it is important to know that it is sometimes okay to Vertex Normalize instead of AA Normalize. For example, if we try to force AA Normalization on the friendship model, we might get something like this 
   
   
  Figure 7 
  The relationships are too specific and have too long of a name (7). We are better off replacing the two edges with a connecting entity. 
  Conclusion 
  We introduced some new concepts in this article: 
   
   Value Singletons are global vertexes with one specific value 
   Connecting Entities are relationship vertices that have one or more properties associated with them 
   Value Edges are weighted Edges(or edges with an associated value) 
   
  We also introduced three graph normalization forms: 
   
   Edge Normalized: Graphs with all edges with less than two weights or values 
   Vertex Normalized: Edge normalized Graphs with all vertices having a single coupled value with Connecting Entities 
   AA Normalized: Vertex Normalized Graphs without connecting entities, but with value edges instead 
   
  Always remember that your graph database is neither a document database, a time series database nor a relational database. Use the best tool for the job to reduce the pain and increase the gain!
 
