(disclaimer: I am VP of Engineering at RelationalAI where we are building a graph database that uses the relational model)
Thanks, this is a great question with many technical, social, and commercial aspects to it.
TLDR: the relational model has a super power for data management systems: it decouples the logical from the physical representation and will eventually always win. There are technical reasons why it was hard until recently to build a graph database based on the relational model.
Database were not always relational: In the 1960s databases actually had a navigational paradigm and used a hierarchical or network data model (not unlike some current graph databases).
The 1970s saw the rise of relational database management systems with early proofpoints of Ingres and System R. The important improvement here was that the physical organization of data is separated from its logical organization in relations. This is the super power of the relational model. This innovation led to an explosion of commercial activity with Oracle, DB2, Sybase (licensed to become Microsoft SQL Server) and some more. Many of these are now still industry giants.
The 90s was a big hype of objected-oriented programming and some got the idea that database management systems should be following the object-oriented model as well. This was mostly a catastrophic failure and instead systems based on the relational model kept improving and won in the end.
In the 2000s there was a large emphasis on scalability to large numbers of users and data, and the development of NoSQL systems started. Most of these did not follow the relational model. These are the key value stores, document databases etc. Key value stores addressed the problem of poor scalability but compromised on the data model and transactions. Document databases have better locality of data and made schema changes easier. They all had something in common: compromise on the relational model to gain an advantage over existing relational systems. However, systems based on the relational model kept improving the meantime and have gradually started to gain market (or mind) share again (eg Aurora, Snowflake, Spanner, CockroachDB).
In my opinion, graph databases are next. Graph databases identified a weakness, which in this case is modelling and the inability of current relational systems to handle graph structured data well. Graph data involves many joins and often recursive computations, which current commercial SQL relational systems do not do well. However, the new graph databases are not superior universally. For example, take TPC-H (OLAP - analytical) or TPC-C (OLTP - transactional), put that on a graph database and you'll typically see pretty terrible performance even though the data can easily be modeled as a graph. Several popular graph database systems do not even scale well beyond a single node.
I think you are absolutely right that graph data models are easier to work with. Starting from an ER diagram (or similar) it's not straightforward to go to tables. Assuming that your ER model is a good model, you're grouping stuff into tables based on functional dependencies. Tables here are a collection of relations, eg for an _order_, the SQL table might include relations to the customer, order date, etc. It does not include relations to products included in the order, because these have a different primary key. This is difficult for users to understand.
Predictably, the relational model is catching up though with graph database systems. A major research innovation in databases from recent years are better join algorithms, specifically for joins involving many relations, self-joins and skewed data. They're called worst-case optimal join algorithms (WCOJ) and several early prototype systems have shown promising results with these.
Based on these ideas, RelationalAI ( https://docs.relational.ai/ , https://twitter.com/RelationalAI ) is building a graph database management system based on the relational model. Presumably, this is the relational model utilizing its super power again and demonstrating that relational models will always win and innovate to incorporate legit limitations of previous systems.
I'm a huge fan of LogicBlox and RelationalAI, and the research done at both had a huge impact on me as an undergrad!
While you're here, could you provide some insight on why you folks went with arbitrary width tuples for your datamodel?
Limiting youself to triples seems to drastically ease the implementation of WCOJ algorithms without much loss of expressivity, and provides compatibility with existing RDF research.
E.g. in our system we materialize the 3!(6) indices required, which allows us to pick variable/intersection orderings on the fly without a planner.
With triples you need to reify hyper edges into nodes (a relation is just a hyper edge). This can lead to pretty awkward models, for example for temporal data. Most graph databases (eg Neo4J) have the same limitation and as a result struggle with temporal data or other higher-dimensional data.
We prefer to support general relations (hyper edges) and face the complications of query planning. We really want a general relational system that decouples the complications in query processing from the way you need to model your data and write your queries
This gets particularly important for what we do besides graphs: we also aim to support machine learning workloads (we have some references to papers on our website).
We still do automatic index selection, but indeed it is important that you do not create too many of these unnecessarily if you relations with arity bigger than triples.
Thanks for the insight!
Having the best and brightest of the west coast database departments at your disposal allows for some different tradeoffs I guess ^^'!
I'm actually surprised that RelationalAI and Materialize Inc haven't merged yet, for ultimate world domination.
It's a shame though that both LogicBlox and RelationalAI historically only target large enterprise customers.
It forces us commoners that want to get out of the tarpit too to bolt relational operators to our existing languages. :D
Stay tuned for that :). RelationalAI is developed as a multi-tenant service that has a pay-as-you-go model. This should make it possible for everybody to use the product. I expect we will have some free tier options too, but we have not decided on the exact model for that yet. We are starting to onboard individual preview users already.
We're good friends with Materialize.io and use similar techniques for general incremental view maintenance, but their product is quite a bit different: their purpose is to design for SQL. RAI offers a different programming model to capture complex application and business logic (the language for that is called Rel, and docs are public).
Looking at RelationalAI documentation, it's fairly clear that you designed a more powerful and "cleaner" query language than SQL, good for graph-oriented tasks and without many of the traditional limitations and compromises found in typical databases.
But this is the front end. In the back end that writes files, elaborates query execution plans and executes concurrent transactions, what price are you paying on the performance side? What are the unavoidable costs of graph queries?
This is really hard to answer in a short comment, but I'll try to highlight a few things:
- We use compute/storage separation as in Snowflake and Aurora. This means that data is stored in object storage (for example S3) and computing resources are transient. This is the de facto standard now for new database management systems. Systems that are not designed for object storage are gradually going to be less relevant. The Snowflake papers are a great resource on this ( http://pages.cs.wisc.edu/~yxy/cs839-s20/papers/snowflake.pdf ) . It's also a recurring topic in the CMU database talks. Our memory management is based on LeanStore and Umbra.
- The database is entirely versioned with an immutable data structure, so read-only scaling does not require locking: you can provision new compute instances that work on a snapshot of the database that is 100% guaranteed to be consistent. This means that you can run an analytical job on your production database with a 100% guarantee that the performance of your primary system is not impacted. For concurrent writes we aim to use incremental maintenance techniques.
- All our data is indexed so that the WCOJ algorithms can do their job. Indexes maintenance can be expensive, so we have write-optimized data structures for that (B-epsilon trees - http://supertech.csail.mit.edu/papers/BenderFaJa15.pdf ). The performance of those is really good, and they can be compacted in the background. The combination of our graph normal form (narrow relations) and WCOJ addresses the index selection problem in a novel way.
- WCOJ are our work horse join algorithm. We have different query evaluation techniques, including JIT compilation and vectorization. For queries that do not require worst-case optimal joins the plans are similar to more conventional systems due to optimizations applied to the plan (talk: https://www.youtube.com/watch?v=C_mBEq_o4HE )
Graph workloads have a few interesting properties: 1) Analytical queries are often recursive. Systems like Neo4J do not really address this in general because the query language does not support general recursion. Instead, it offers bindings to algorithms implemented in Java. 2) Queries often do joins across many relations. 3) There is lots of skew.
(2) and (3) are handled by WCOJ. For (1) we use algorithms similar differential dataflow. Differential Dataflow already has great proof points for graph analytical queries (mainly created by Frank McSherry)
In the end, of course all that matters are the actual benchmarks. We are developed those for standard relational workloads (like TPC-H) and graph workloads (for example LDBC SNB, graph analytical workloads). It's a little too early for us to claim results at scale, but we have isolated proof points that the design works.
Thanks, this is a great question with many technical, social, and commercial aspects to it.
TLDR: the relational model has a super power for data management systems: it decouples the logical from the physical representation and will eventually always win. There are technical reasons why it was hard until recently to build a graph database based on the relational model.
Database were not always relational: In the 1960s databases actually had a navigational paradigm and used a hierarchical or network data model (not unlike some current graph databases).
The 1970s saw the rise of relational database management systems with early proofpoints of Ingres and System R. The important improvement here was that the physical organization of data is separated from its logical organization in relations. This is the super power of the relational model. This innovation led to an explosion of commercial activity with Oracle, DB2, Sybase (licensed to become Microsoft SQL Server) and some more. Many of these are now still industry giants.
The 90s was a big hype of objected-oriented programming and some got the idea that database management systems should be following the object-oriented model as well. This was mostly a catastrophic failure and instead systems based on the relational model kept improving and won in the end.
In the 2000s there was a large emphasis on scalability to large numbers of users and data, and the development of NoSQL systems started. Most of these did not follow the relational model. These are the key value stores, document databases etc. Key value stores addressed the problem of poor scalability but compromised on the data model and transactions. Document databases have better locality of data and made schema changes easier. They all had something in common: compromise on the relational model to gain an advantage over existing relational systems. However, systems based on the relational model kept improving the meantime and have gradually started to gain market (or mind) share again (eg Aurora, Snowflake, Spanner, CockroachDB).
In my opinion, graph databases are next. Graph databases identified a weakness, which in this case is modelling and the inability of current relational systems to handle graph structured data well. Graph data involves many joins and often recursive computations, which current commercial SQL relational systems do not do well. However, the new graph databases are not superior universally. For example, take TPC-H (OLAP - analytical) or TPC-C (OLTP - transactional), put that on a graph database and you'll typically see pretty terrible performance even though the data can easily be modeled as a graph. Several popular graph database systems do not even scale well beyond a single node.
I think you are absolutely right that graph data models are easier to work with. Starting from an ER diagram (or similar) it's not straightforward to go to tables. Assuming that your ER model is a good model, you're grouping stuff into tables based on functional dependencies. Tables here are a collection of relations, eg for an _order_, the SQL table might include relations to the customer, order date, etc. It does not include relations to products included in the order, because these have a different primary key. This is difficult for users to understand.
Predictably, the relational model is catching up though with graph database systems. A major research innovation in databases from recent years are better join algorithms, specifically for joins involving many relations, self-joins and skewed data. They're called worst-case optimal join algorithms (WCOJ) and several early prototype systems have shown promising results with these.
Based on these ideas, RelationalAI ( https://docs.relational.ai/ , https://twitter.com/RelationalAI ) is building a graph database management system based on the relational model. Presumably, this is the relational model utilizing its super power again and demonstrating that relational models will always win and innovate to incorporate legit limitations of previous systems.