Local First Tuple Database
github.com
github.com
"Database In Depth" is a really good book. Highly recommended. Short and clear.
Don't let SQL scare you off the relational model. It has given it a bad name.
Underneath every relational modeled system, there is a lower-level, much simpler system that implements the actual data storage as bytes - and the data access APIs like “scanKeyRange”, “readKey”, “writeKey” - over a sorted data structure like a B-tree.
An algebraic operation like “filter” or “selection” (σ) requires the relational layer to understand the layout of data in the storage layer if we want any kind of performance better than O(total number of tuples), right? But that adds complexity and indirection, regardless of the syntax / API used to express the relational algebra, SQL or KQL.
You can think of this project as such a storage layer. It is imperative, not declarative, as a primary objective. One could build a relational layer on top, though.
From the Motivation section:
> I've spent way too much time in Postgres manually denormalizing data and constructing elaborate indexes that perfectly complement a complex query with the goal of EXPLAIN outputting INDEX ONLY SCAN for optimal performance. This dance is a tiresome incidental complexity for application development.
How can a relational algebra system (with any form of query language or API) escape this issue? It seems inherent to the declarative nature of relational algebra.
The Background and Motivation sections go into a lot of detail, but a quick summary is that if I were to build Notion all over again, I would definitely use FoundationDb. It's a lower level of abstraction and is not for the faint of heart. But indexing user-defined properties and queries with many-to-many relationships is not simple.
I've since become interested in "Local-First Software" and built this abstraction to underpin my next projects which are in a similar domain that I've been calling "end-user data modeling".
If you have any questions, feel free to ask or open an issue on Github.
Interfaces & abstraction where you'd expect them to be, and leveraging Typescript's type system where you can. Looks awesome.
I have no idea what to use it on/with first but it will be at the back of my head for quite a while!
return db.scan({prefix: ["userByName", {last_name: lastName}]})
.map(({key, value}) => key)
.map(namedTupleToObject)
SELECT id, first_name FROM user
WHERE last_name = $lastName
FROM user
WHERE last_name = $lastName
SELECT id, first_nameIn the relational algebra "select" is actually a "filter" operation. It's what the "where clause" implies. The other name for it is "Restrict." It reduces the result set down to the tuples that match on the supplied predicates.
SQL does a funny thing by putting it at the front of the query, but it does so as a way of saying "Hey, I'm about to begin a relational query."
What you've done here is more incorrect. Maybe? Not sure of your intent.
The name for the operator which "chooses which attributes to put in my results" is "PROJECTION". That's the thing that some people seem to think "select" refers to.
In a more pure relational system it would look something like (syntax totally made up)
Project( (id, first_name), Select( Predicate(last_name = $lastName), Relation(User)))
Or maybe:
User.Select(last_name=$lastName).Project({id, first_name})
As for this "order of execution" thing, SQL explicitly doesn't do that on purpose because the entire point is that the query optimizer can and should re-order things for the most efficient result. The beauty of the relational algebra (which SQL only partially implements) is that the order of operations can in many cases be re-ordered (in logically provable ways). So there is no set execution order. The system can take care of that for you.
SQL's syntax is crap, but I don't see any advantages to this.
Chris Date's Tutorial D had alternate syntax proposals.
Personally I'd go for something more terse, like in the Rel Project's impl of the D concepts:
USER {ID, FIRST_NAME} WHERE LAST_NAME= NAME($lastName)
https://reldb.org/c/wp-content/uploads/2017/12/Rel-and-Tutor...
select id, first_name from user;
If we're making up new syntaxes for relational calculus, i think something pipey would feel most natural:
from user | restrict last_name = $last_name | project id, first_name;
from user
| project *, is_boss = role in ('manager', 'executive')
| restrict last_name = $last_name and is_boss
| project id, first_name;
from user
| restrict role = 'executive'
> boss
from department
| restrict location = 'HQ'
> hq_dept
join < boss < hq_dept on boss.id = hq_dept.head_id
| project first_name, last_name, dept_name
I read it as “I want the id and first name, you can get this from…” — the projection clause stating what you want, and the following clauses detailing how the information what you want can be found in is arranged.
You can also think of it like a recipe: “I'm, going to make a cake, from eggs, flour, …” rather than following the instructions then at the end being told what you are making.
While “from <here>, filtering by <condition>, pick <things>” better matches your view of what the database engine is going to do to service your request, matching what the engine does internally to service your request is not SQL's priority. As another example of this: with joins you are not telling the engine “this is how to do…” (well, you are, but indirectly) — what you are actually doing is describing how the information links together. With this information and other information it already has (from the schema, particularly what indexes are available) it will decide the best way to proceed, and in fact will sometimes effectively reorder your request for efficiency (some simple DB engines will always follow the order you state the objects to use, but that is their limitation not something dictated by SQL in theory).
users.filter((u) => u.lastName == "foo").map((u) => [u.id, u.firstName]);
[ (user.id, user.firstName) for user in users if user.lastName == "foo" ]As a practical matter, this is not true. If it were true, tools like EXPLAIN PLAN would not exist because it would not be necessary to manipulate queries to get good performance.
The developer is then responsible for selecting the index and storing their data appropriately, which gives more predictable performance and makes reasoning about the behavior of the query simpler(for beginners, not necessarily easier).
This is very much in the pattern of DynamoDB (which they cite), which gives highly predictable performance at all scales by removing the query planner layer and leaving the developer to work out what indexes they need, how to mold their data to them, and how too query them.