5 ms·
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
by v-yadli 9y ago
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 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.
- polskibus 9y agoHow mature is GE? Who's using it in production?
- jexp 9y agoTransaction 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.
- v-yadli 9y ago> "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.
- twic 9y ago> A non-graph-database would not provide operators like deep traversals You can do this with a recursive common table expression.
- hvidgaard 9y agoACID 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.
- v-yadli 9y agothis 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.