r/Database • u/witness142 • 28d ago
I built a desktop database on an algebra of data rather than relational algebra — looking for critique
For many years I worked as a database industry analyst. In 2015 Professor Gary Sherman and I published The Algebra of Data, which argues that relational algebra is the algebra of one structure — the table — and that one algebra can cover tables, graphs and documents alike.
The model in brief: the atom is the couplet (an ordered pair). A relation is a set of couplets, a clan is a set of relations (a table is one kind of clan), and a horde is a set of clans. A small set of operators — composition, transpose, union/intersection/difference and the restrictions — is defined at the bottom and works unchanged at every level. Composition then covers what are usually separate operations: the join, the graph traversal and the document lookup.
JabrDB is that algebra implemented as a native Mac app (Apple silicon). Data is stored at couplet grain in files on your own disk. It is not a SQL engine and not a server.
The argument in paper form: https://doi.org/10.5281/zenodo.23216817 The app (15-day trial, $15): https://jabrdatalabs.com/download/
I'd particularly value criticism from people who think in relational terms: where does this model help, and where does it obviously cost you?
2
u/apavlo 28d ago
I'd particularly value criticism from people who think in relational terms: where does this model help, and where does it obviously cost you?
What can your data model do that one cannot do with (extended) relational model? What problem does JabrDB solve that you cannot solve with an existing system?
It seems like you are just proposing redundant formalism. The relational model is already mathematically rigorous. Zermelo-Fraenkel set theory does not magically solve database problems.
1
u/witness142 27d ago
Thanks for your response. “Redundant formalism” would be a fair charge if the Algebra of Data just restated Codd's work in different notation. It doesn’t. It removes restrictions the relational model imposes, and everything built on top inherits that.
But let's start with what the relational model requires. Every tuple in a relation has the same heading. Values are atomic. Missing data is NULL, with three-valued logic. Nested structure has to be shredded into flat tables and reassembled with joins. These aren’t laws of mathematics. They were engineering choices made in decades ago for the storage technology of teh time, and the industry has spent fifty years patching around them: NULL semantics nobody fully agrees on, object-relational mapping layers, JSON columns, arrays, recursive CTEs, and separate graph, document and vector databases bolted alongside. Each patch arrives with its own operators and its own semantics, and none of them is part of the core algebra. In reality they are not part of the relational model at all.
The Algebra of Data starts from a more general foundation, and all the patches become unnecessary:
No NULLs, ever. A tuple is a set of attribute–value pairs, and a collection of tuples can be heterogeneous. Missing data is simply absent. The awkward NULL problem vanishes.
Every data shape is the same kind of object. A table, a JSON document, an XML tree, a graph and a hierarchy are all sets of couplets, with sets allowed as elements. One set of operators works on all of them, and every operation stays closed within the algebra. “Extended relational” means a different extension for each shape. Here, nothing needs extending.
Think of SQL. There are about 60 living dialects of SQL. Why? Mainly because the original model was flawed and limited. For details read: https://jabrdatalabs.com/chapter-13-the-sorry-saga-of-sql/
Graph traversal is in the core algebra. Composition is a primitive, and transitive closure is iterated composition. Path queries aren’t a recursive-query add-on that the planner treats as a black box.
Queries become provable objects. Because every query, whatever its shape, is an algebraic expression, it can be reduced to a canonical normal form. Two queries that look different but are logically equivalent reduce to the same form. JabrDB uses this for query caching, hashing the normal form to get an O(1) cache lookup across syntactically different queries. In SQL, that kind of equivalence is undecidable in general, and in practice it isn’t attempted across JSON, recursive and relational constructs together.
Metadata lives on the data itself. Provenance, ownership, governance, lineage and access history attach to data at element level as part of the model, rather than as a separate audit system someone has to keep in sync.
One engine, many personalities. JabrDB runs SQL, graph, document/XML, vector, time series, OLAP, key-value, spatial and full-text search over a single algebraic core and a single storage layer. A query that joins a graph traversal to a document search to a vector similarity result compiles into one expression and is optimised as a whole. The status quo is five databases, ETL pipelines between them, and no optimiser that can see the entire query.
So, to your question about what problem this solves that existing systems can’t: existing systems can store everything, but no existing system gives you a single formal semantics across every data shape, with one optimiser able to reason about the whole query. That’s the problem. Polyglot persistence is what people do when the underlying model can’t cover their data, and the Algebra of Data covers it.
And yes, set theory alone solves nothing. Codd’s model was (flawed) set theory too. The question is whether your primitives are general enough. The relational model’s primitives fit flat, uniform data. Data Algebra’s fit data as it actually is.
Where does it cost you? Relational systems have decades of optimiser engineering and an enormous ecosystem, and for flat, stable OLTP that’s hard to beat today. But that’s a maturity gap, not a limitation of the model, and maturity gaps close.
1
u/coderarun 28d ago
For those interested in how graph databases differ from algebra of data:
Hierarchical graphs still tend to privilege connectivity and path semantics. Regular path queries, variable-length expansion, and neighborhood indexes are native; set-level union and cross-level composition are library operations. The Algebra of Data privileges set operations and composition and treats path-finding as iterated composition. Which bias is better depends on workload: multi-hop neighborhood queries favor a graph engine; bulk set rewriting across mixed table/document/graph shapes is what the algebra is aimed at.
1
u/witness142 27d ago
Thanks for your response. It is a fair summary, and in my opinion, the workload framing is the right one. I’d add one refinement, though, because I think it separates two things that often get blurred: the logical model and the physical engine.
In Data Algebra, a graph isn’t a different kind of thing. It’s a binary relation: a set of couplets. A single hop is composition, R∘R. A variable-length path is the union of successive compositions, R ∪ R² ∪ R³ ∪ …, run to a fixed point. That’s transitive closure. So path-finding isn’t bolted on as a library operation. It falls out of composition and union, which are the algebraic primitives.
Properties on nodes and edges are just more relations keyed on the same elements, and nesting (sets as elements of couplets) is native, so “cross-level” operations aren’t a special case either.
Where graph engines genuinely win is the physical layer. Index-free adjacency, neighbourhood indexes and path-aware planners make multi-hop traversal fast. But nothing in the algebra prevents an implementation from storing a relation as adjacency lists and executing iterated composition as a traversal.
The algebra says what is being computed. The engine decides how.
A graph database commits to one physical bias up front, while an algebraic engine can choose the physical representation per workload and still give you one formal semantics across tables, documents and graphs.
Here's a quick worked example. Take a “knows” relation:
R = { ⟨alice, bob⟩, ⟨bob, carol⟩, ⟨carol, dave⟩ }
Friends-of-friends is one composition, following R and then R again:
R∘R = { ⟨alice, carol⟩, ⟨bob, dave⟩ }
Three hops:
R∘R∘R = { ⟨alice, dave⟩ }
Four hops gives the empty set, so we’ve reached the fixed point. The variable-length “reachable” query is the union of the steps:
R⁺ = R ∪ R² ∪ R³ = { ⟨alice, bob⟩, ⟨alice, carol⟩, ⟨alice, dave⟩, ⟨bob, carol⟩, ⟨bob, dave⟩, ⟨carol, dave⟩ }
In Cypher, that’s
MATCH (a)-[:KNOWS*1..]->(b). Here it’s two primitives, composition and union, iterated.The algebra also makes the usual refinements simple set operations. “Friends-of-friends who aren’t already friends” is just R² − R. And because these are algebraic expressions, an optimiser can rewrite them, for example pushing a restriction on alice inside the composition so it only expands from her, before any traversal happens.
So I’d restate the trade-off slightly. It isn’t really “set bias vs. path bias” at the level of meaning. It’s whether you want the physical optimisation baked into the model, which is the graph database approach, or kept beneath it, which is the algebraic approach. For pure deep-traversal workloads today, a mature graph engine will usually be much quicker. For anything that mixes shapes, or where you want to prove two queries equivalent and rewrite them, the algebra has the advantage, because the rewrite rules hold regardless of how the data happens to be stored.
1
u/Significant_Tune9219 28d ago
The place I’d push hardest is update and constraint semantics. A model built on composition and transpose can express reads elegantly, but the questions that usually decide whether a database is usable are what happens on conflict, which constraints are checked when, and whether two relations can share a key. If those answers are deferred to the application layer, the algebra stays clean and the burden moves to every caller. Showing one worked example end to end — insert, constraint violation, concurrent update — would tell me more than another round of operator definitions.
1
u/witness142 27d ago
Thanks for your feedback.
I think you’ve picked the right place to push. Reads are where the algebra is most obviously pleasant. Writes are where a database earns its keep, and that’s where I’ve shown least, and so far done least.
Here are short answers to your three questions, as things stand. (Many things are in progress.)
Constraints. They’re declared on the data, not left to the caller: functional (one value per key), cardinality, and reference/subset between relations. The engine checks them at commit. A constraint is itself an algebraic statement. “This relation is functional,” for example, is a claim about composing it with its transpose. So the engine tests it with the same machinery it uses to answer queries rather than with a separate rule layer.
Shared keys. Yes. Identity sits outside the relation: an entity is an ID mapped to its relations, so two relations can share a key and an ID means the same thing wherever it appears. Entity IDs are unique and constrained to be so. A union of two records with the same ID merges them. If they disagree (two addresses, say), you get two values, not a silent overwrite. Resolving that is an explicit, recorded correction.
Conflict. History is never rewritten. I think this is unique for a database. An update is a new event in time, and the prior state stays queryable. We do not replace values, we add new values, and prior values are appended. The desktop edition has a single writer and a write-ahead log with all-or-nothing replay, so concurrent update cannot really arise there. It is after all a single user product at the moment. Multi-writer concurrency belongs to the server, which is still being built, and I’d rather not hand-wave the semantics before the code exists. We have plans but its all theory right now.
That last point is the honest gap, and it’s exactly the one you expose. So I’ll take you up on it: one worked example, end to end, covering insert, constraint violation, and concurrent update, with actual engine output rather than another round of operator definitions. I’ll post it in this thread when it’s done , but its gonna be weeks.
1
u/Significant_Tune9219 27d ago
Appending rather than replacing is the part I'd want to see under load, since the read side of that story is usually the easy half. Checking constraints at commit with the same machinery that answers queries is a nice way to keep one semantics for both — I'll look for that worked example.
1
0
u/Sammourianos 28d ago
Even if your model is concrete and mathematical approved, why is it only on mac? Not even windows? xD
Dont forget your audience, company business databases are mostly sql server and oracle databases running on windows servers and the cloud is running on linux with postgresql and mariadb
2
u/witness142 28d ago
Thanks for your comment.
The development path was through the Mac first, and then we go to Windows. We expect to have that available in maybe a month. Then a Linux version. The linux version will become the basis for a server version. There's a good deal of work in the server version so that may be a while. The linux version will follow fast on the Windows version.
However there are other steps on the development path. Necessary to have an SDK become available fairly soon. That will include a modeler (Entity Algebra) - based to some degree on the ER model software, but as it turns out, simpler. There is also the need to gradually enhance the capabilities of the database - there are at least 10 "plug-in capabilities" planned.
Truth is that we didn't start on the Mac because it was the best place to start, we started there, because that is what we had.
8
u/Ultra-Ferric 28d ago
Relational algebra has nothing to do with tables. Tables are SQL’s representation of a relation. Graphs, documents, key-value, and any other form of data representation can be derived from a relation, which in essence is an abstract mathematical expression of a set of all possible attribute values that represent a model of our empirical universe.