**diff options**

author | pukkamustard <pukkamustard@posteo.net> | 2020-09-28 14:15:50 +0200 |
---|---|---|

committer | pukkamustard <pukkamustard@posteo.net> | 2020-09-28 14:15:50 +0200 |

commit | 707dab285804d63ab3896e0005e6d2ff1731aea8 (patch) | |

tree | 1620181c37c5a6d3c996a58daf5b8e8a7f77c061 | |

parent | ec38672da556d692c44b97cb2f6dcfc77c9c0906 (diff) |

(datalog relational-algebra2): notes on how to improve (datalog

relational-algebra)

-rw-r--r-- | datalog/relational-algebra2.scm | 81 |

1 files changed, 81 insertions, 0 deletions

diff --git a/datalog/relational-algebra2.scm b/datalog/relational-algebra2.scm new file mode 100644 index 0000000..7bf87ce --- /dev/null +++ b/datalog/relational-algebra2.scm @@ -0,0 +1,81 @@ +; SPDX-FileCopyrightText: 2020 pukkamustard <pukkamustard@posteo.net> +; +; SPDX-License-Identifier: GPL-3.0-or-later + +;; Some random notes on how to clean up the relational-algebra module. + +(define-module (datalog relational-algebra2) + #:use-module (schemantic lvar) + + #:use-module (srfi srfi-9) + #:use-module (srfi srfi-43) + #:use-module (srfi srfi-171) + #:use-module (srfi srfi-171 meta)) + + +;; Relational Algebra expressions are just trees. Operators are the nodes and relations are leafs. +;; +;; Instead of using goops it might be possible to use simple records with +;; transducers that define the operation of the node. This allows more streaming +;; evaluation and possibly even fibers. + +(define-record-type <operator> + (%make-operator type transducer children) + operator? + ;; the type is important for algebraic query rewriting. Does the node + ;; represent a cartesian product or a selection? This info is in the transducer but + ;; needs to be available before evaluation. + (type operator-type) + ;; performs the operation + (transducer operator-transducer) + ;; the children of the operator (the operands) + (children operator-children)) + +(define-record-type <relation> + (%make-relation predicate-symbol attributes) + relation? + (predicate-symbol relation-predicate-symbol) + (attributes relation-attributes)) + +;; How to rewrite the query?? +;; https://en.wikipedia.org/wiki/Relational_algebra#Use_of_algebraic_properties_for_query_optimization + +;; Transducing a tree + +(define-record-type <node> + (make-node transducer-fn children) + node? + (transducer-fn node-transducer) + (children node-children)) + +(define-record-type <leaf> + (make-leaf values) + leaf? + (values leaf-values)) + +(define (node-reduce f identity node) + (let* ((children (node-children node)) + (len (vector-length children))) + (let loop ((i 0) (acc identity)) + (let* ((child-mask (make-bitvector 2 #f)) + (rf ((compose + (tmap (lambda (x) (cons child-mask x))) + (node-transducer node)) f))) + (if (= i len) + acc + (loop (1+ i) (tree-reduce rf acc (vector-ref children i)))))))) + +(define (tree-reduce f identity tree) + (if (leaf? tree) + (list-reduce f identity (leaf-values tree)) + (node-reduce f identity tree))) + +;; tree-transduce -> (rf) +(define (tree-transduce rf tree) + (rf (tree-reduce rf (rf) tree))) + +(tree-transduce rcons (make-node (tmap identity) + (vector (make-leaf (list 1 2)) + (make-node (tmap identity) + (vector (make-leaf (list 3 4)) + (make-leaf (list 5 6))))))) |