diff options
Diffstat (limited to '')
| -rw-r--r-- | README.org | 35 | ||||
| -rw-r--r-- | docs/about.org | 47 | ||||
| -rw-r--r-- | docs/architecture.plantuml | 72 | ||||
| -rw-r--r-- | docs/karuta-integration.org | 130 | ||||
| -rw-r--r-- | docs/transaction-algo.org | 12 | ||||
| -rw-r--r-- | lib/manipulation.ml | 1 |
6 files changed, 190 insertions, 107 deletions
@@ -1,27 +1,16 @@ -#+TITLE: Relational Engine +#+TITLE: Sakura Relational Engine * About This is a relational engine. -* Roadmap -- [ ] State - - [ ] Add the schema modifications to the commit state hash - - [ ] Save a history of the schema -- [ ] Filesystem [0/6] - - [ ] Durability - - [ ] Immutable storage - - [ ] ARIES - - [ ] Merkle construction per virtual file - - [ ] Branching - - [ ] Branch merge strategies [0/3] - - [ ] Selected merge - - [ ] Union merge - - [ ] Biased union merge -- [ ] Language [0/4] - - [ ] Lexer - - [ ] Parser - - [ ] AST - - [ ] Unification and query terms -- [ ] Server [0/2] - - [ ] Authentication - - [ ] Multi-client coordination +* Glossary +** Conceptual model +A piece of the world of discourse. In a project to design a map of Scotland, this would be Scotland itself in reality alongside the business rules in natural language. +** Relation +A cartesian product of primitive domains (integer, natural, rational, etc) with a membership criteria over an intension (collection of business rules) +** Ephemeral Relation +We can ephemeral relations that relations that have its values generated on demand. They are catalogued on the database as normal relations, but act based on a generator function. In SQL, they would be views, but here they are much else, they are algebraic artifacts that come out of any relational operation, eg.: R2 <- project {field1, field2} R1. R2 in this case is an ephemeral relation. +** Provenance +From where an attribute comes from in a generated relation (ephemeral). For example, if a join occurs and blends the attributes from two different relations, the base relations are references on the new generated ephemeral relation as to identify its origins. This is what enables "updatable views", since we always know the source of an attribute. +** Lineage +What operation produced an attribute. A join, project, etc.
\ No newline at end of file diff --git a/docs/about.org b/docs/about.org new file mode 100644 index 0000000..6c64ceb --- /dev/null +++ b/docs/about.org @@ -0,0 +1,47 @@ +* About + +Sakura is a semantic-relational algebra engine inspired by +E. F. Codd's RM/T and D. McGoveran's (as understood by Fabian Pascal) +SRDM. It models relations in both intension and extension, providing +their manipulation as first-class elements of an algebra. + +* Motivation + +We believe the relational model was not ever fully implemented. The +fundamental necessity of expressing intent and binding meaning +enclosed to a conceptual model in data is seldom achieved by any +self-claimed relational database vendor. The emergence of different +physically concerned paradigms in the industry demonstrate not only a +large scale amnesia about fundamentals, but also a lethal +manifestation of problems that should not exist otherwise. The +relational data model as an applied theory is an universally rich and +concrete approach to reality that bases itself greatly in +moderate-realism applied to mathematics, as described in =An +Aristotelian Realist Philosophy of Mathematics: Mathematics as the +Science of Quantity and Structure= by J. Franklin. We believe that +unleashing the full potential of the relational model as refined over +the years despite overwhelming disregard of the industry as a whole, +will promote efficiency to a new scale never seen, that was very much +so cut short by relational pretenders and theoretically unsound +approaches. Our goal is to eliminate the application-database +distinction, while maintaining a clear separation between a first +order predicate logic algebra engine and a higher order predicate +logic decision engine (application) via an embedded data sublanguage +with Sakura as a possible auxiliary runtime. + +* Design Intent + +Sakura aims to treat relations as algebraic manipulation units with both: + +- extension (actual tuples, finite or generated) +- intension (schema + constraints + derivation meaning) + +The current engine already exposes the extension side robustly for +many operations, despite the lack of constraints greater than 1OP. +The main active work is making intension handling fully consistent and +reliable across planners/operators/protocols. + +* References + +- Codd, E. F. (1970), "A Relational Model of Data for Large Shared Data Banks" +- Codd, E. F. (1979), "Extending the Database Relational Model to Capture More Meaning" diff --git a/docs/architecture.plantuml b/docs/architecture.plantuml deleted file mode 100644 index 90985ba..0000000 --- a/docs/architecture.plantuml +++ /dev/null @@ -1,72 +0,0 @@ -@startuml -allowmixing - -package Client { - object "Query Interface" as query_interface -} - -package Algebra { - object "Unifier" as unifier - object "Bytecode Builder" as bytecode_builder - object "Parser" as parser - object "Lexer" as lexer -} - -query_interface --> lexer -lexer --> parser -parser --> unifier -unifier --> bytecode_builder - -package Query { - object "Schema Builder" as schema_builder - object "Facts Builder" as facts_builder - object "Optimizer" as optimizer - object "Commands Generator" as commands_generator - object "B+ Tree" as b_plus_tree -} - -bytecode_builder --> optimizer -optimizer --> commands_generator -facts_builder --> commands_generator -schema_builder --> commands_generator -commands_generator --> b_plus_tree -b_plus_tree --> query_interface - -package Coordinator { - object "File Historical Hashes" as file_historical_hashes - object "Location Hashes" as location_hashes - object "Command Parser" as command_parser - object "Curator" as curator -} - -commands_generator <-- command_parser - -package Disk { - object "Merkle Tree Root Generator" as merkle_tree - object "WAL Reader" as wal_reader - object "WAL Writer" as wal_writer - object "ARIES" as aries - object "SHA256 Hasher" as sha - object "Executor" as executor - map storage { - write => +λ - read => +λ - } - object "Courier" as courier - database Wal -} - -executor *--> merkle_tree -executor *--> sha -curator --> command_parser -command_parser --> executor -location_hashes *--> curator -file_historical_hashes *--> curator -executor --> aries -aries --> wal_reader -aries --> wal_writer -wal_writer --> Wal -wal_reader --> Wal -courier <-- wal_reader -courier --> storage -@enduml
\ No newline at end of file diff --git a/docs/karuta-integration.org b/docs/karuta-integration.org new file mode 100644 index 0000000..a144a25 --- /dev/null +++ b/docs/karuta-integration.org @@ -0,0 +1,130 @@ +* About Karuta + +Just like PostgreSQL and MySQL have SQL, Sakura has Karuta, a prolog-like language targetting the BEAM. [[karuta][https://github.com/dont-rely-on-nulls/karuta]] is the programming language that presents the different sublanguages to manage an RDBMS. + +We believe that what E. F. Codd envisioned was a stack of sublanguages that are embedded in a more powerful language, that expand it's abstraction scope as you move up the stack, trying to provide guarantees at each level. A data retrieval language should halt and has no business into being Turing Complete, but a predicate procedure language might. In light of this, Sakura is supposed to provide a common DSL that can differentiate between such sublanguages and execute things accordingly. + +The approach is that everything is a relation itself. So a constraint for instance is expressed as a relation less_than over NxN instead of simply being an operator '<'. + +* Sublanguages +Here's an overview of the sublanguages and how they are manifested in Karuta: + +** DRL (Data Retrieval Language) + +- Pure querying, total/terminating subset; +- No user recursion with no self references. + +** DCL (Data Constraint Language) + +- Integrity rules (key, FK-like, checks, assertions, aggregates-for-integrity). +- Semantically predicates, but with enforcement timing (on write/commit), not free query operators. + +** DML (Data Manipulation Language) + +- Insert/update/delete; +- Delta semantics, can trigger constraint evaluation. + +** DDL (Data Definition Language) + +- Define relations/views (ephemeral relations)/indexes/types/modules/predicate signatures and capabilities. + +** TCL (Transaction/Control Language) + +- Begin/commit/rollback, isolation/consistency controls, maybe savepoints. + +** PPL (Procedural Predicate Language) + +- Stored procedures/functions, recursion allowed, orchestration logic. +- Can call DRL/DML/DCL-aware operations, but not all PPL predicates are DRL-safe. + +** ACL (Authorization/Policy Language) (optional early, important later) + +- Who can query/mutate/define; row/predicate-level access policies. + +* Prototype + +#+begin_src prolog + % DDL + :- schema[users] { + :- signature[people-sig] { + person[_, _]. + another-person[string, natural]. + valid_age[natural]. + a-procedure[int, int]. + a-view[_, _, _]. + }. + :- module[people, people-sig] { + % This is using the arity directly, because the types are being specified in the signature. + % These Sakura-provided type extensions after '::' are the what informs Sakura through metadata on connection which type of Karuta predicate this is used as in Karuta. + another-person/2 :: sakura:persisted + another-person[Name, FavoriteNumber]. + + person[string, natural] :: sakura:persisted + person[Name, Age] :- valid_age[Age]. + + % DCL + another-constraint[list[person], string, natural] :: sakura:constraint + another-constraint[[], _, _]. + another-constraint[[person[Name, Age]|Rest], Whatever1, Whatever2] :- + (eq[Name, Whatever1] ; !eq[Name, Whatever1], !eq[Age, Whatever2]), + another-constraint[Rest, Whatever1, Whatever2]. + + % DCL + my-predicate[int, string, nat] :: sakura:constraint + my-predicate[Arg1, Arg2, Arg3] :- + another-module:my-predicate[Arg1, Arg2, Arg3], + on[insert, update], + timing[immediate]. + + % DCL + valid_age/1 :: sakura:constraint + valid_age[Age] with [karuta, sakura] :- + nat[Age], + greater_or_equal[Age, 0], + % DRL + aggregate[person, 2, Tuples], + another-constraint[Tuples, "lemos", 26], + on[insert, update], + timing[immediate], + target[age]. + + % PPL + a-procedure/2 :: sakura:stored + a-procedure[Arg1, Arg2] :- + eq[Arg1, Arg2]. + + % DDL + a-view[string, natural, natural] :: sakura:ephemeral + a-view[Name, Age, FavoriteNumber] :- + person[Name, Age], + another-person[Name, FavoriteNumber]. + }. + }. + + my-predicate[users:people:person, string, nat] :: signature + my-predicate[Arg1, Arg2, Arg3] :- + another-module:my-predicate[Arg1, Arg2, Arg3]. + + main[Arg1, Arg2] :- + karuta:plus[Arg1, Arg2, Out], + karuta:aggregate[numbers:inc, 2, Tuples], + + % Project directive should give us these configurations + project:sakura[Secret, Port, Host], + project:sakura:config[Users1, Commit], + + sakura:connect[Secret, Port, Host, Connection], + sakura:database[Connection, Users1, Commit, DB1Handle], + + % TCL + sakura:transaction[TXContext, DB1Handle], + + % DML + sakura:insert[users:people:person["Toad", 18], TXContext], + (sakura:error?[TXContext, Reason], sakura:rollback[TXContext], print["We rolled back: ~s!", Reason]) ; + (sakura:new[TXContext, [name], Difference1], + sakura:commit[TXContext, DB2Handle], + sakura:delta[DB1Handle, DB2Handle, Difference2], + % DRL + @relation1[Arg2, Out]). +#+end_src
\ No newline at end of file diff --git a/docs/transaction-algo.org b/docs/transaction-algo.org deleted file mode 100644 index 22903ec..0000000 --- a/docs/transaction-algo.org +++ /dev/null @@ -1,12 +0,0 @@ -* Check if temporary file with the command hash with exists -To hash the command, we must hash its bytes without the timestamp, -since it will always vary given it's a transactional time, and add -instead the commit HEAD of the state of the database. - -If such file exists, load the transaction and storage offsets -alongside the command and attempt to write it as a recovery. -* Get the transaction offset of the transaction graph file AND storage file -* Write the offsets to a tmp file -* Write the command with a flag **flushed** set to false to a tmp file -* Attempt to execute the command -* Delete the temporary file diff --git a/lib/manipulation.ml b/lib/manipulation.ml new file mode 100644 index 0000000..9b60306 --- /dev/null +++ b/lib/manipulation.ml @@ -0,0 +1 @@ +let create_database
\ No newline at end of file |