;;; ;;; relation.scm - relational operations ;;; ;;; Copyright (c) 2005-2024 Shiro Kawai ;;; ;;; Redistribution and use in source and binary forms, with or without ;;; modification, are permitted provided that the following conditions ;;; are met: ;;; ;;; 1. Redistributions of source code must retain the above copyright ;;; notice, this list of conditions and the following disclaimer. ;;; ;;; 2. Redistributions in binary form must reproduce the above copyright ;;; notice, this list of conditions and the following disclaimer in the ;;; documentation and/or other materials provided with the distribution. ;;; ;;; 3. Neither the name of the authors nor the names of its contributors ;;; may be used to endorse or promote products derived from this ;;; software without specific prior written permission. ;;; ;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT ;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR ;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT ;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, ;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED ;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR ;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF ;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING ;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS ;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. ;;; ;;; Given set of values S1, S2, ..., Sn, a relation R is a set of tuples ;;; such that the first element of a tuple is from S1, the second from ;;; S2, ..., and the n-th from Sn. In another word, R is a subset of ;;; Cartesian product of S1, ..., Sn. ;;; ;;; (This is actually THE definition from the original Codd's 1970 paper, ;;; "A Relational Model of Data for Large Shared Data Banks", in ;;; CACM 13(6) pp.377--387.) ;;; ;;; This definition can be applied to various datasets: A set of Gauche ;;; instances is a relation, if you view each instance as a tuple and ;;; each slot value as the actual values. A list of lists can be a ;;; relation. A stream that reads from CSV table produces a relation. ;;; Thus it would be useful to provide a module that implements generic ;;; operations on relations, no matter how the actual representation is. ;;; ;;; From the operational point of view, we can treat any datastructure ;;; that provides the following two properties. ;;; ;;; - a collection of tuples (rows), which should be a or ;; one of its subclasses (e.g. ). ;;; - metadata to retrieve individual column value from a given tuple. ;;; ;;; One can implement a relation by writing at least four methods, ;;; relation-column-names, relation-column-getter and relation-column-setter, ;;; and relation-rows. ;;; ;;; On top of that abstraction, we can implement a bunch of useful stuff. ;;; We'll add them, but here are some ideas. ;;; ;;; - Codd's relational operations ;;; - A relation that wraps existing relations, adding index operation. (define-module util.relation (use gauche.sequence) (export relation-column-names relation-column-name? relation-column-getter relation-column-setter relation-rows relation-accessor relation-modifier relation-ref relation-set! relation-coercer relation-column-getters relation-column-setters relation-insertable? relation-insert! relation-deletable? relation-delete! relation-fold )) (select-module util.relation) ;; An abstract base class of . (define-class () ()) ;;;----------------------------------------------------------------- ;;; Minimal set of generic functions. Concrete implementations must ;;; implement the followings. ;; Should return a procedure that can be used as ;; (REF &optional ) (define-method relation-accessor ((r )) (error "accessor method isn't defined for the relation" r)) ;; Should return a procedure that can be used as ;; (SET! ) ;; If the relation is read-only, this method can return #f. (define-method relation-modifier ((r )) #f) ;; Should return a sequence of column names. (define-method relation-column-names ((r )) '()) ;; Should return a of rows. (For some relations, ;; the returned object can be .) (define-method relation-rows ((r )) '()) ;;;----------------------------------------------------------------- ;;; Optional methods. They can be implemented by the minimal methods ;;; above, but a concrete implementation may override these methods ;;; for efficiency. ;; Queries if COLUMN is a valid column name in a relation. ;; The default method assumes eq? comparison of the column name. (define-method relation-column-name? ((r ) column) (memq column (relation-column-names r))) ;; Returns a procedure that extracts the value of the column from ;; the given row. (define-method relation-column-getter ((r ) column) (let1 accessor (relation-accessor r) (lambda (row) (accessor row column)))) ;; Returns a procedure that takes a row and a value, and set row's ;; column by value. (define-method relation-column-setter ((r ) column) (let1 modifier (relation-modifier r) (lambda (row v) (modifier row column v)))) ;; Direct referencer (define-method relation-ref ((r ) row column . default) (apply (relation-accessor r) row column default)) ;; Direct modifier (define-method relation-set! ((r ) row column val) ((relation-modifier r) row column val)) (define-method (setter relation-ref) ((r ) row column val) (relation-set! r row column val)) ;; Returns full list of getters and setters. Usually the default ;; method is sufficient, but the implementation may want to cache ;; the list of getters, for example. (define-method relation-column-getters ((r )) (let1 accessor (relation-accessor r) (map (^c (lambda (row) (accessor row c))) (relation-column-names r)))) (define-method relation-column-setters ((r )) (let1 modifier (relation-modifier r) (map (^c (lambda (row val) (modifier row c val))) (relation-column-names r)))) ;; Returns a procedure that coerces a row into a sequence. ;; If the relation already uses a sequence to represent a row, it can ;; return row as is. The default method is generic but inefficient. (define-method relation-coercer ((r )) (let1 getters (relation-column-getters r) (lambda (row) (map (cut <> row) getters)))) ;; Optionally a subclass may provide them. (define-method relation-insertable? ((r )) #f) (define-method relation-insert! ((r ) row) #f) (define-method relation-deletable? ((r )) #f) (define-method relation-delete! ((r ) row) #f) ;;; ;;; Generic stuff ;;; ;; Cf. E.F.Codd: Extending the database relational model to capture ;; more meaning, ACM trans. on database systems 4(4) pp.397--434, Dec. 1979. ;; project ;; select ;; join (define-method relation-fold ((r ) proc seed . columns) (let1 getters (map (cut relation-column-getter r <>) columns) (fold (lambda (row seed) (apply proc (fold-right (lambda (getter seed) (cons (getter row) seed)) (list seed) getters))) seed (relation-rows r)))) ;;;============================================================= ;;; Concrete implementations ;;; ;; ;; ;; (define-class ( ) ((columns :init-keyword :columns :init-value '()) ;; sequence of symbols (rows :init-keyword :rows :init-value '())) ;; list of sequences ) (define-method call-with-iterator ((r ) proc . keys) (apply call-with-iterator (ref r 'rows) proc keys)) (define-method relation-rows ((r )) (slot-ref r 'rows)) (define-method relation-column-names ((r )) (ref r 'columns)) (define-method relation-accessor ((r )) (let1 columns (ref r 'columns) (lambda (row column . maybe-default) (cond ((find-index (cut eq? <> column) columns) => (cut ref row <>)) ((pair? maybe-default) (car maybe-default)) (else (error "simple-relation: invalid column:" column)))))) (define-method relation-modifier ((r )) (let1 columns (ref r 'columns) (lambda (row column val) (cond ((find-index (cut eq? <> column) columns) => (cut (setter ref) row <> val)) (else (error "simple-relation: invalid column:" column)))))) (define-method relation-column-getter ((r ) column) (let1 ind (find-index (cut eq? <> column) (ref r 'columns)) (unless ind (error "simple-relation: invalid column:" column)) (lambda (row) (ref row ind)))) (define-method relation-column-setter ((r ) column) (let1 ind (find-index (cut eq? <> column) (ref r 'columns)) (unless ind (error "simple-relation: invalid column:" column)) (lambda (row v) (set! (ref row ind) v)))) (define-method relation-coercer ((r )) identity) (define-method relation-insertable? ((r )) #t) (define-method relation-insert! ((r ) (row )) (unless (= (size-of row) (length (ref r 'columns))) (error "simple-relation: attempt to insert a row that doesn't match the relation:" row)) (push! (ref r 'rows) row)) (define-method relation-deletable? ((r )) #t) (define-method relation-delete! ((r ) (row )) (update! (ref r 'rows) (cut delete! row <> equal?))) ;; ;; ;; (define-class ( ) ((class :init-keyword :class :init-value ) (rows :init-keyword :rows :init-value '()) ;; list of instances of class )) (define-method call-with-iterator ((r ) proc . keys) (apply call-with-iterator (ref r 'rows) proc keys)) (define-method relation-rows ((r )) (slot-ref r 'rows)) (define-method relation-column-names ((r )) (map slot-definition-name (class-slots (ref r 'class)))) (define-method relation-column-name? ((r ) column) (find (lambda (slot) (eq? column (slot-definition-name slot))) (class-slots (ref r 'class)))) (define-method relation-column-getter ((r ) column) (unless (relation-column-name? r column) (error "object-set-relation: invalid column name:" column)) (lambda (row) (slot-ref row column))) (define-method relation-column-setter ((r ) column) (unless (relation-column-name? r column) (error "object-set-relation: invalid column name:" column)) (lambda (row v) (slot-set! row column v))) (define-method relation-accessor ((r )) slot-ref) (define-method relation-modifier ((r )) slot-set!) (define-method relation-coercer ((r )) (lambda (row) (map (^s (slot-ref row s)) (relation-column-names r)))) (define-method relation-insertable? ((r )) #t) (define-method relation-insert! ((r ) row) (unless (is-a? row (ref r 'class)) (error "object-set-relation: attempt to insert an object of mismatched class:" row)) (push! (ref r 'rows) row)) (define-method relation-deletable? ((r )) #t) (define-method relation-delete! ((r ) row) (update! (ref r 'rows) (cut delete! row <> equal?)))