Comment by v-yadli | Hacker News Reader

Comment by v-yadli | Hacker News Reader

Interesting question. I think it is critical to point out that, the underlying principles for a graph database is different from RDBMS, because the operators in a graph database may not comply to relational algebra.

Consider the following case:

Client A issues a query -- starting from a vertex, conduct bounded closure search, giving every visited vertex a mark (coloring, or lexical flag, whatever you would expect from a graph algorithm)

Client B issues a query -- clearing any marks applied to a particular vertex, which happens to be one of the visited vertex of Client A's query.

Now, race condition aside, let's assume we first process query A then B. Would we allow query B to succeed? It is clearly possible for query B to break the semantic of query A, for example, query A goes through a bridge and then query B cuts the bridge, so the connectivity information is lost.

Of course we could say that such query A should be a part of a transaction, and isolation can be more strictly enforced -- but again, to what degree? Poor locality will cause the transactions to be interconnected with each other. How does a graph database determine what is the true purpose of the algorithm under each query? What does it guarantee?

Many graph databases now claims ACID, but what do they really mean?

Is it just a fancy query language over a traditional data model? Say, you could also build graph queries for a SQL database -- what does a graph database provide that such graph-over-SQL cannot?

p.s. I work on Microsoft Graph Engine: https://github.com/Microsoft/GraphEngine. We decide to build a modular graph processor rather than calling it a graph database, because we don't really know by default, what kind of semantics does a user want. With GraphEngine, you could plug in linear query languages likq Gremlin or GraphQL, you can also plug in SPARQL, or traditional relational model with strong guarantees, or down to bare-metal key-value store with atomicity and durability only. I do think that a graph data model is very helpful in many scenarios, but I think we really need to advance the research on the semantic of graph management.

Transaction isolation is a no-brainer, so I don't think your example holds. Also, your example is not related to the algebra but to isolation.

"Claiming ACID" what is ambiguous about that? Transaction support with different serialization levels, like other databases that offer it.

And Neo4j originally started b/c RDBMS was not able to execute the complex deep traversals needed in real time. Dedicated storage & query engine for graphs allow you to run statements quickly that would otherwise take too long to execute.

Regarding the data model, the property-graph model is much closer to the object model but with richer relationships, it doesn't suffer from the object-rdbms impedance mismatch and is better suited to express real-world domains & scenarios. It also represents semantic relevant relationships as first class citizens in the database, allowing for proper information representation and much faster retrieval.

Disclaimer: I work with/for Neo4j, for 8+ years and still love it.

> "Claiming ACID" what is ambiguous about that? Transaction support with different serialization levels, like other databases that offer it.

A non-graph-database would not provide operators like deep traversals. Operations are tightly bound to ACID as a whole, not just isolation. Of course ACID would always hold if you strictly linearize everything, but that defeats the purpose of data management, and one would achieve the same goal with even macro processors like `m4`.

Getting traversals and other graph algorithms into the business means that there are lot of things that should be reconsidered, like constraints, and triggers.

For example, if you cannot write a constraint to limit the local clustering coefficient of every entity, you do not proceed in your traversal with a good upper bound time budget. However, it is the vertices that you _don't_ visit that will propagate these constraints back while you are halfway there. Parallelizing such queries, in my opinion, is beyond state-of-the-art research.

> A non-graph-database would not provide operators like deep traversals

You can do this with a recursive common table expression.

While this is technically true, in the SQL world this requires wizard level skills that most SQL developers do not possess, and when you arrive at this spot, you end up with a query that performs really, really badly.

Look, between the database formalisms, they're all "complete" in the sense that you can choose any database and solve all the problems. But certain databases are going to be pathologically bad at solving certain types of problems, which is why there are so many sub-niches that persist over time.

For deep path traversals, you can do it with RDBMS, but a graph DB is going to win every time in part because the data structure is just set up for that purpose. There are other queries where RDBMS will be best too. So it goes.

Recursive CTEs are breadth-first, which may not always be what you need.

ACID is whatever you define. In a RDBMS you can make a query returning dirty data, or that data is partially saved if an error happens. Or you can roll it into a full ACID compliant query/transaction.

I think that in a graph database, the ACID property comes at a greater cost, but to me it's a tool I use as a secondary store, derived from the "truth" in the RDBMS. I use it to store the data more efficiently for queries and to query data in a discovering fashion that would significantly more complicated in the underlying RDBMS.

this is a primary scenario for us -- knowledge graph streaming into the system, and graph queries run with private working sets, without touching the core data.

How mature is GE? Who's using it in production?

Reply on news.ycombinator.com