diff options
| -rw-r--r-- | docs/relational-algebra.org | 191 |
1 files changed, 191 insertions, 0 deletions
diff --git a/docs/relational-algebra.org b/docs/relational-algebra.org new file mode 100644 index 0000000..54f28c5 --- /dev/null +++ b/docs/relational-algebra.org @@ -0,0 +1,191 @@ +* Relational Algebra + +Relational algebra is simply that, an algebra. It manipulates objects +in its space and outputs another element of the same space. SQL is +often seem as an attempt to encode the relational algebra, however it +lacks the ability to represent its objects from its algebra by a +substitution and weakening statics, which typed lambda calculus +can. It also cannot separate properly the boundaries of its +sublanguages, which are all mashed together in a huge mess. Our DRL +(Data Retrieval Language) is concerned with relational algebra +operations on relations (that is, no such thing as "denormalized +relations" should be accepted) in first order predicate +logic. =lib/algebra.ml= implements the core transformations that query +and manipulate relations. It's essentially an OCaml functor that works +with any storage backend, producing =ephemeral relations=. + +* Ephemeral Relations + +Ephemeral relations are generated objects that do not persist its own +tuples in storage. In other words, they are objects that are fully +relations themselves, but their data retrieval is by composition atop +of other base relations. Saying that a relation is *stored* is +logical-physical confusion (LPC). Only its data is. Since we are +attempting to apply a theory to a computer, we cannot resort however +to infinite relations where each transformation by constraints is +given by the axiom of choice over a substitution static, but we +simulate such by composition of defined relations over our DML +sublanguage; it's a compromise for simplicity. In a sense, the name +*ephemeral relation* is a contradiction in terms, but it is our way of +calling for the composition nature of such relations, while trying to +get away from R-tables as a representation, which are not relations, +only a tabular view of data; extension. + +* Implementation: The Functor Pattern + +=algebra.ml= is structured as an OCaml functor: + +#+begin_src ocaml +module Make(Storage : Management.Physical.S) = struct + (* implementation *) +end + +module Memory = Make(Management.Physical.Memory) +#+end_src + +This design allows the relational algebra to be agnostic of the +storage backend. The same algebra operations work with in-memory +storage, disk storage, or any future backend that implements the +=Physical.S= signature. + +* Generator-Based Lazy Evaluation + +Rather than materializing entire relations, =algebra.ml= uses lazy +generators (=Generator.t=, a function from position to the next value) +to produce tuples on demand. This avoids the overhead of computing and +storing all intermediate results. + +** Core Generator Utilities + +- =to_generator rel= :: Converts a relation into a generator. If the + relation is already ephemeral (has a generator), returns it; if + stored, loads tuples from the hash tree and wraps them in a + generator. + +- =drain gen= :: Exhausts a generator completely into a list. Used + when an operation needs all tuples at once (e.g., for the right side + of a join). + +- =list_generator ts= :: Creates a generator from a concrete tuple + list. + +- =of_generator ~name ~schema gen= :: Wraps a generator with metadata + (name, schema, constraints, cardinality) to create an ephemeral + =Relation.t=. All algebraic operations produce relations this way. + +* The Operators + +Each operator accepts one or two relations and returns a new ephemeral +relation whose generator lazily computes the result. + +** Selection (σ): Filtering by Predicate + +#+begin_src ocaml +select_fn storage predicate rel +#+end_src + +Filters tuples that satisfy the boolean predicate. The schema and +constraints are preserved unchanged. The resulting generator only +yields tuples for which =predicate t = true=. + +** Projection (π): Attribute Subset + +#+begin_src ocaml +project storage attrs rel +#+end_src + +Keeps only the specified attributes. The schema is reduced to match. +Importantly, constraints are filtered: only constraints that reference +only the projected attributes are retained. Constraints mentioning +dropped attributes are discarded to avoid invalidity. + +** Rename (ρ): Attribute Renaming + +#+begin_src ocaml +rename storage renames rel +#+end_src + +Applies a list of =(old_name, new_name)= pairs to rename attributes. +The schema is updated, and all constraints have their variable names +updated to match the renamed attributes. + +** Equijoin (⋈): Relation Joining + +#+begin_src ocaml +equijoin storage join_attrs left right +#+end_src + +Joins two relations on matching values of =join_attrs=. The operation: +1. Drains the right relation (materializes all right tuples) +2. Streams the left relation through a generator +3. For each left tuple, filters right tuples matching on the join attributes +4. Merges matching tuples by combining their attribute maps + +The resulting schema is the left schema plus non-join attributes from +the right (avoiding duplicates). Constraints from both relations are +merged if they coexist. + +** Union (∪): Relation Combination + +#+begin_src ocaml +union storage rel1 rel2 +#+end_src + +Chains two generators: first exhausts =rel1=, then =rel2=. The schema +is from the left relation. Constraints are dropped conservatively +(constraints only hold if both inputs agree on them). + +** Difference (−): Set Subtraction + +#+begin_src ocaml +diff storage rel1 rel2 +#+end_src + +Yields tuples from =rel1= that do not appear in =rel2=. Drains =rel2= +to materialize it for comparison, then streams =rel1= and filters out +matching tuples (using attribute equality). Constraints from =rel1= +are preserved. + +** Take (τ): Cardinality Limiting + +#+begin_src ocaml +take storage n rel +#+end_src + +Limits output to =n= tuples. The resulting relation's cardinality is +marked as =Finite n=. Schema and constraints are preserved. + +* Constraint Propagation + +Constraints attached to relations describe membership predicates on +tuples. As operations transform relations, constraints must be +updated: + +- *Preserved* (select): Filtering does not invalidate constraints; + they still apply to the output. +- *Filtered* (project): Constraints mentioning dropped attributes are + removed. +- *Renamed* (rename): Constraint variable names are updated to match + attribute renames. +- *Merged* (join, union): Constraints from both input relations are + combined, or dropped if uncertain (conservative approach). +- *Preserved* (diff, take): Constraints from the input relation carry + forward. + +* Materialization + +For cases where a concrete tuple list is needed (rather than a lazy +generator), the =materialize= function exhausts an ephemeral relation +into =Tuple.materialized list=. This is rarely needed in typical +algebraic compositions, but useful for final results or debugging. + +#+begin_src ocaml +materialize storage rel : Tuple.materialized list +#+end_src + +* Constant Relations + +The =const_relation= utility creates a single-tuple relation from a +list of key-value pairs. Useful for embedding literal values into +algebraic expressions. + |