Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A type-safe, realtime collaborative Graph Database in a CRDT

codemix.com

Post reply on HN
Print view View original

41–50 of 50 posts

Re: A type-safe, realtime collaborative Graph Database in a CRDT

#41

Post by cmrdporcupine »

UltraSane wrote: post #39
cmrdporcupine wrote: post #37

Earlier quoted context omitted.

Parent commenter was asking compare to datalog (not SQL) which eats recursive graph transitions like this for lunch, making the queries very elegant to read ... while still staying relational. I'm personally of the opinion that "graph databases" should be relational databases; the relational model can subsume "graph" queries, but for all the reasons Codd laid out back in the 60s... network (aka connected graph) datab…

JOINS make these kinds of queries get slower as the number of hops gets larger. And property graph databases have the big advantage of not having to mutilate their query results to fit into a flat table. A path query returns a path object of connected nodes. Property graphs are superior for applications with deep, variable-length connections, such as social networks, recommendation engines, fraud detection, and IT ne…

It'd going to get slower as the number of hops get bigger regardless of whether you accomplish that via relational join or pointer traversal. And doing it the former gives great opportunity for optimization during execution through vectorization or more appropriate index data structure usage.

Modern computers are also much more efficient at batch / vector processing than they are pointer hops. By either CPU or GPU, the whole system is much more tuned for working with data as sets / tensors rather than "hopping" through the data via pointer.

How you materialize your results for processing is your own business. The advantage of the relational model is its consistent throughout; the source data, the manipulation format for the operators, and the output are all relations. You can visualize it as "flat table" but that's an unimaginative visualization. You can just as easily twist that into a nested hierarchical structure in an object oriented language if you're so unfortunate as to be stuck working that way.

A "table" is only a visualization of the data, not the "form" the data actually takes and it's unfortunate that SQL chose this word.

It's better to conceive of a relation as a series of facts or propositions about the world. Each "row" is a statement. When read that way, it's a lot more elegant.

Re: A type-safe, realtime collaborative Graph Database in a CRDT

#42

Post by UltraSane »

cmrdporcupine wrote: post #41
UltraSane wrote: post #39

Earlier quoted context omitted.

JOINS make these kinds of queries get slower as the number of hops gets larger. And property graph databases have the big advantage of not having to mutilate their query results to fit into a flat table. A path query returns a path object of connected nodes. Property graphs are superior for applications with deep, variable-length connections, such as social networks, recommendation engines, fraud detection, and IT ne…

It'd going to get slower as the number of hops get bigger regardless of whether you accomplish that via relational join or pointer traversal. And doing it the former gives great opportunity for optimization during execution through vectorization or more appropriate index data structure usage. Modern computers are also much more efficient at batch / vector processing than they are pointer hops. By either CPU or GPU, t…

Neo4j-style index-free adjacency gives you O(1) per-hop neighbor lookup per node; cost is proportional to the subgraph actually visited. A k-way self-join on a relational edge table has to produce and filter intermediate tuples at each join step, and intermediate result size can blow up multiplicatively even if the final result is small. A k-way self-join on a relational edge table has to produce and filter intermediate tuples at each join step, and intermediate result size can blow up multiplicatively even if the final result is small. For deep traversals with selective endpoints, the relational plan's intermediate materialization is exactly the problem native graph engines were built to avoid.

You can just as easily see nodes and edges in a property graph as propositions about the world. The nice thing is that you can model relationships between entities as first class entities. nodes have the implicit property of being non-fungible.

Do you know of any relational database that returns a query result as normalized tables the way neo4j returns a sub-graph?

Re: A type-safe, realtime collaborative Graph Database in a CRDT

#44

Post by cmrdporcupine »

UltraSane wrote: post #42
cmrdporcupine wrote: post #41

Earlier quoted context omitted.

It'd going to get slower as the number of hops get bigger regardless of whether you accomplish that via relational join or pointer traversal. And doing it the former gives great opportunity for optimization during execution through vectorization or more appropriate index data structure usage. Modern computers are also much more efficient at batch / vector processing than they are pointer hops. By either CPU or GPU, t…

Neo4j-style index-free adjacency gives you O(1) per-hop neighbor lookup per node; cost is proportional to the subgraph actually visited. A k-way self-join on a relational edge table has to produce and filter intermediate tuples at each join step, and intermediate result size can blow up multiplicatively even if the final result is small. A k-way self-join on a relational edge table has to produce and filter intermedi…

Honestly, I won't convince you, so I'll leave you to the pleasure of your pointer chasing, L1 cache misses, multiplicative blowups, and fixed / inflexibly structured taxonomies.

Re: A type-safe, realtime collaborative Graph Database in a CRDT

#45

Post by UltraSane »

cmrdporcupine wrote: post #44
UltraSane wrote: post #42

Earlier quoted context omitted.

Neo4j-style index-free adjacency gives you O(1) per-hop neighbor lookup per node; cost is proportional to the subgraph actually visited. A k-way self-join on a relational edge table has to produce and filter intermediate tuples at each join step, and intermediate result size can blow up multiplicatively even if the final result is small. A k-way self-join on a relational edge table has to produce and filter intermedi…

Honestly, I won't convince you, so I'll leave you to the pleasure of your pointer chasing, L1 cache misses, multiplicative blowups, and fixed / inflexibly structured taxonomies.

In practice if you index the right properties and have the right relationships in Neo4j then queries are very fast. And neo4j doesn't have taxonomies. You might be thinking of RDF. One of the best things about Neo4j compared to relational databases is the lack of a rigid schema.

Re: A type-safe, realtime collaborative Graph Database in a CRDT

#46

Post by ghc »

cmrdporcupine wrote: post #37
UltraSane wrote: post #29

Earlier quoted context omitted.

The advantage for property graph databases using Cypher query language is that the queries for things like "show me all systems connected to this system by links greater than 10Gbps up to n hops away" are vastly easier to write and faster to complete compared to SQL and relational databases. Cypher lets you easily search for arbitrary graph patters and the result is also a graph, not a denormalized table.

Parent commenter was asking compare to datalog (not SQL) which eats recursive graph transitions like this for lunch, making the queries very elegant to read ... while still staying relational. I'm personally of the opinion that "graph databases" should be relational databases; the relational model can subsume "graph" queries, but for all the reasons Codd laid out back in the 60s... network (aka connected graph) datab…

> the relational model can subsume "graph" queries, but for all the reasons Codd laid out back in the 60s... network (aka connected graph) databases cannot do the latter.

Except network databases have little in common with graph databases...they're much more closely related to hierarchical databases.

I would say that Graph databases are now a strict superset of relational databases, not the other way around. In a graph database a node's named edge can naturally point to a node of any type or having any property schema. Doing this in a relational model requires one of several approaches that could only be classified as fighting against the model (or torturing it, as my PI liked to say).

Re: A type-safe, realtime collaborative Graph Database in a CRDT

#47

Post by UltraSane »

ghc wrote: post #46
cmrdporcupine wrote: post #37

Earlier quoted context omitted.

Parent commenter was asking compare to datalog (not SQL) which eats recursive graph transitions like this for lunch, making the queries very elegant to read ... while still staying relational. I'm personally of the opinion that "graph databases" should be relational databases; the relational model can subsume "graph" queries, but for all the reasons Codd laid out back in the 60s... network (aka connected graph) datab…

> the relational model can subsume "graph" queries, but for all the reasons Codd laid out back in the 60s... network (aka connected graph) databases cannot do the latter. Except network databases have little in common with graph databases...they're much more closely related to hierarchical databases. I would say that Graph databases are now a strict superset of relational databases, not the other way around. In a gra…

Working with relational databases after getting used to Neo4j feels like wearing handcuffs.

Re: A type-safe, realtime collaborative Graph Database in a CRDT

#48

Post by teleforce »

cmrdporcupine wrote: post #37
UltraSane wrote: post #29

Earlier quoted context omitted.

The advantage for property graph databases using Cypher query language is that the queries for things like "show me all systems connected to this system by links greater than 10Gbps up to n hops away" are vastly easier to write and faster to complete compared to SQL and relational databases. Cypher lets you easily search for arbitrary graph patters and the result is also a graph, not a denormalized table.

Parent commenter was asking compare to datalog (not SQL) which eats recursive graph transitions like this for lunch, making the queries very elegant to read ... while still staying relational. I'm personally of the opinion that "graph databases" should be relational databases; the relational model can subsume "graph" queries, but for all the reasons Codd laid out back in the 60s... network (aka connected graph) datab…

>I'm personally of the opinion that "graph databases" should be relational databases; the relational model can subsume "graph" queries

The MIT team which is also part of the team that proposed GraphQL already kind of solved this problem using D4M [1].

Essentially D4M is able to universally represent relational, graph, spreadsheet and matrices using the mathematic technique of associative algebra, they even wrote an entire book on the subject [2].

It's beyond me why they didn't push forward for D4M but instead propose a limited GraphQL. It seems that they're restricting the D4M capability and focusing on query language like GraphQL, perhaps due to the industry demand and bias.

Heck the same team also proposed TabulaROSA, a new database OS as the more efficient alternative for conventional file-system based OS like Unix/Linux [3].

[1] D4M: Dynamic Distributed Dimensional Data Model:

https://d4m.mit.edu/

[2] Mathematics of Big Data: Spreadsheets, Databases, Matrices, and Graphs:

https://mitpress.mit.edu/9780262038393/mathematics-of-big-da...

[3] TabulaROSA: tabular operating system architecture for massively parallel heterogeneous compute engines:

https://www.ll.mit.edu/r-d/publications/tabularosa-tabular-o...

Re: A type-safe, realtime collaborative Graph Database in a CRDT

#49

Post by rs545837 »

paul_h wrote: post #36
rs545837 wrote: post #32

Oh this is cool. The Yjs as storage backend trick is clever, you basically get CRDT sync for free without having to build your own replication layer. And the pluggable storage means you can develop against in-memory and then flip to YGraph for collab mode without touching your queries. That's a nice developer experience. The live queries also caught my eye. Having traversals auto reexecute when data changes sounds st…

Semantic merge. PlasticSCM had that a feature many years back

yeah definitely plastic scm has always been my inspiration, just trying to revive it.

Re: A type-safe, realtime collaborative Graph Database in a CRDT

#50

Post by kkollsg »

brianbcarter wrote: post #14

Cypher-over-Gremlin is a smart call — LLMs can write Cypher, makes the MCP angle viable in a new way. How dos Yjs handle schema migrations? If I add a property to a vertex type that existing peers have cached, does it conflict or drop the unknown field?

A cypher interface for an MCP is really efficient. I'm running multiple MCPs that way. The trick is also exposing a describe-style tool the model calls before writing queries. Having a schema-introspective tool means you don't have to deal with the schema directly. The knowledge graph deals with it itself, and lets the agent iteratively investigate the graph and then write a query that gives it exactly what it needs. I'm running MCPs across pretty different domains including legal, oil and gas, and codebases. It's surprisingly versatile.
Post reply on HN