| 1 |
;;; |
| 2 |
;;; relation.scm - relational operations |
| 3 |
;;; |
| 4 |
;;; Copyright (c) 2005-2024 Shiro Kawai <[email protected]> |
| 5 |
;;; |
| 6 |
;;; Redistribution and use in source and binary forms, with or without |
| 7 |
;;; modification, are permitted provided that the following conditions |
| 8 |
;;; are met: |
| 9 |
;;; |
| 10 |
;;; 1. Redistributions of source code must retain the above copyright |
| 11 |
;;; notice, this list of conditions and the following disclaimer. |
| 12 |
;;; |
| 13 |
;;; 2. Redistributions in binary form must reproduce the above copyright |
| 14 |
;;; notice, this list of conditions and the following disclaimer in the |
| 15 |
;;; documentation and/or other materials provided with the distribution. |
| 16 |
;;; |
| 17 |
;;; 3. Neither the name of the authors nor the names of its contributors |
| 18 |
;;; may be used to endorse or promote products derived from this |
| 19 |
;;; software without specific prior written permission. |
| 20 |
;;; |
| 21 |
;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 22 |
;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 23 |
;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 24 |
;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 25 |
;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 26 |
;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED |
| 27 |
;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| 28 |
;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF |
| 29 |
;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING |
| 30 |
;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
| 31 |
;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 32 |
;;; |
| 33 |
|
| 34 |
;;; Given set of values S1, S2, ..., Sn, a relation R is a set of tuples |
| 35 |
;;; such that the first element of a tuple is from S1, the second from |
| 36 |
;;; S2, ..., and the n-th from Sn. In another word, R is a subset of |
| 37 |
;;; Cartesian product of S1, ..., Sn. |
| 38 |
;;; |
| 39 |
;;; (This is actually THE definition from the original Codd's 1970 paper, |
| 40 |
;;; "A Relational Model of Data for Large Shared Data Banks", in |
| 41 |
;;; CACM 13(6) pp.377--387.) |
| 42 |
;;; |
| 43 |
;;; This definition can be applied to various datasets: A set of Gauche |
| 44 |
;;; instances is a relation, if you view each instance as a tuple and |
| 45 |
;;; each slot value as the actual values. A list of lists can be a |
| 46 |
;;; relation. A stream that reads from CSV table produces a relation. |
| 47 |
;;; Thus it would be useful to provide a module that implements generic |
| 48 |
;;; operations on relations, no matter how the actual representation is. |
| 49 |
;;; |
| 50 |
;;; From the operational point of view, we can treat any datastructure |
| 51 |
;;; that provides the following two properties. |
| 52 |
;;; |
| 53 |
;;; - a collection of tuples (rows), which should be a <collection> or |
| 54 |
;; one of its subclasses (e.g. <sequence>). |
| 55 |
;;; - metadata to retrieve individual column value from a given tuple. |
| 56 |
;;; |
| 57 |
;;; One can implement a relation by writing at least four methods, |
| 58 |
;;; relation-column-names, relation-column-getter and relation-column-setter, |
| 59 |
;;; and relation-rows. |
| 60 |
;;; |
| 61 |
;;; On top of that abstraction, we can implement a bunch of useful stuff. |
| 62 |
;;; We'll add them, but here are some ideas. |
| 63 |
;;; |
| 64 |
;;; - Codd's relational operations |
| 65 |
;;; - A relation that wraps existing relations, adding index operation. |
| 66 |
|
| 67 |
(define-module util.relation |
| 68 |
(use gauche.sequence) |
| 69 |
(export <relation> |
| 70 |
relation-column-names relation-column-name? |
| 71 |
relation-column-getter relation-column-setter |
| 72 |
relation-rows |
| 73 |
relation-accessor relation-modifier |
| 74 |
relation-ref relation-set! relation-coercer |
| 75 |
relation-column-getters relation-column-setters |
| 76 |
relation-insertable? relation-insert! |
| 77 |
relation-deletable? relation-delete! |
| 78 |
relation-fold |
| 79 |
<simple-relation> <object-set-relation> |
| 80 |
)) |
| 81 |
(select-module util.relation) |
| 82 |
|
| 83 |
;; An abstract base class of <relation>. |
| 84 |
(define-class <relation> () ()) |
| 85 |
|
| 86 |
;;;----------------------------------------------------------------- |
| 87 |
;;; Minimal set of generic functions. Concrete implementations must |
| 88 |
;;; implement the followings. |
| 89 |
|
| 90 |
;; Should return a procedure that can be used as |
| 91 |
;; (REF <row> <column> &optional <value>) |
| 92 |
(define-method relation-accessor ((r <relation>)) |
| 93 |
(error "accessor method isn't defined for the relation" r)) |
| 94 |
|
| 95 |
;; Should return a procedure that can be used as |
| 96 |
;; (SET! <row> <column> <value>) |
| 97 |
;; If the relation is read-only, this method can return #f. |
| 98 |
(define-method relation-modifier ((r <relation>)) |
| 99 |
#f) |
| 100 |
|
| 101 |
;; Should return a sequence of column names. |
| 102 |
(define-method relation-column-names ((r <relation>)) '()) |
| 103 |
|
| 104 |
;; Should return a <collection> of rows. (For some relations, |
| 105 |
;; the returned object can be <sequence>.) |
| 106 |
(define-method relation-rows ((r <relation>)) '()) |
| 107 |
|
| 108 |
;;;----------------------------------------------------------------- |
| 109 |
;;; Optional methods. They can be implemented by the minimal methods |
| 110 |
;;; above, but a concrete implementation may override these methods |
| 111 |
;;; for efficiency. |
| 112 |
|
| 113 |
;; Queries if COLUMN is a valid column name in a relation. |
| 114 |
;; The default method assumes eq? comparison of the column name. |
| 115 |
(define-method relation-column-name? ((r <relation>) column) |
| 116 |
(memq column (relation-column-names r))) |
| 117 |
|
| 118 |
;; Returns a procedure that extracts the value of the column from |
| 119 |
;; the given row. |
| 120 |
(define-method relation-column-getter ((r <relation>) column) |
| 121 |
(let1 accessor (relation-accessor r) |
| 122 |
(lambda (row) (accessor row column)))) |
| 123 |
|
| 124 |
;; Returns a procedure that takes a row and a value, and set row's |
| 125 |
;; column by value. |
| 126 |
(define-method relation-column-setter ((r <relation>) column) |
| 127 |
(let1 modifier (relation-modifier r) |
| 128 |
(lambda (row v) (modifier row column v)))) |
| 129 |
|
| 130 |
;; Direct referencer |
| 131 |
(define-method relation-ref ((r <relation>) row column . default) |
| 132 |
(apply (relation-accessor r) row column default)) |
| 133 |
|
| 134 |
;; Direct modifier |
| 135 |
(define-method relation-set! ((r <relation>) row column val) |
| 136 |
((relation-modifier r) row column val)) |
| 137 |
|
| 138 |
(define-method (setter relation-ref) ((r <relation>) row column val) |
| 139 |
(relation-set! r row column val)) |
| 140 |
|
| 141 |
;; Returns full list of getters and setters. Usually the default |
| 142 |
;; method is sufficient, but the implementation may want to cache |
| 143 |
;; the list of getters, for example. |
| 144 |
(define-method relation-column-getters ((r <relation>)) |
| 145 |
(let1 accessor (relation-accessor r) |
| 146 |
(map (^c (lambda (row) (accessor row c))) |
| 147 |
(relation-column-names r)))) |
| 148 |
|
| 149 |
(define-method relation-column-setters ((r <relation>)) |
| 150 |
(let1 modifier (relation-modifier r) |
| 151 |
(map (^c (lambda (row val) (modifier row c val))) |
| 152 |
(relation-column-names r)))) |
| 153 |
|
| 154 |
;; Returns a procedure that coerces a row into a sequence. |
| 155 |
;; If the relation already uses a sequence to represent a row, it can |
| 156 |
;; return row as is. The default method is generic but inefficient. |
| 157 |
(define-method relation-coercer ((r <relation>)) |
| 158 |
(let1 getters (relation-column-getters r) |
| 159 |
(lambda (row) (map (cut <> row) getters)))) |
| 160 |
|
| 161 |
;; Optionally a subclass may provide them. |
| 162 |
(define-method relation-insertable? ((r <relation>)) #f) |
| 163 |
(define-method relation-insert! ((r <relation>) row) #f) |
| 164 |
|
| 165 |
(define-method relation-deletable? ((r <relation>)) #f) |
| 166 |
(define-method relation-delete! ((r <relation>) row) #f) |
| 167 |
|
| 168 |
;;; |
| 169 |
;;; Generic stuff |
| 170 |
;;; |
| 171 |
|
| 172 |
;; Cf. E.F.Codd: Extending the database relational model to capture |
| 173 |
;; more meaning, ACM trans. on database systems 4(4) pp.397--434, Dec. 1979. |
| 174 |
|
| 175 |
;; project |
| 176 |
;; select |
| 177 |
;; join |
| 178 |
|
| 179 |
(define-method relation-fold ((r <relation>) proc seed . columns) |
| 180 |
(let1 getters (map (cut relation-column-getter r <>) columns) |
| 181 |
(fold (lambda (row seed) |
| 182 |
(apply proc (fold-right (lambda (getter seed) |
| 183 |
(cons (getter row) seed)) |
| 184 |
(list seed) |
| 185 |
getters))) |
| 186 |
seed (relation-rows r)))) |
| 187 |
|
| 188 |
;;;============================================================= |
| 189 |
;;; Concrete implementations |
| 190 |
;;; |
| 191 |
|
| 192 |
;; |
| 193 |
;; <simple-relation> |
| 194 |
;; |
| 195 |
|
| 196 |
(define-class <simple-relation> (<relation> <collection>) |
| 197 |
((columns :init-keyword :columns :init-value '()) ;; sequence of symbols |
| 198 |
(rows :init-keyword :rows :init-value '())) ;; list of sequences |
| 199 |
) |
| 200 |
|
| 201 |
(define-method call-with-iterator ((r <simple-relation>) proc . keys) |
| 202 |
(apply call-with-iterator (ref r 'rows) proc keys)) |
| 203 |
|
| 204 |
(define-method relation-rows ((r <simple-relation>)) |
| 205 |
(slot-ref r 'rows)) |
| 206 |
|
| 207 |
(define-method relation-column-names ((r <simple-relation>)) |
| 208 |
(ref r 'columns)) |
| 209 |
|
| 210 |
(define-method relation-accessor ((r <simple-relation>)) |
| 211 |
(let1 columns (ref r 'columns) |
| 212 |
(lambda (row column . maybe-default) |
| 213 |
(cond |
| 214 |
((find-index (cut eq? <> column) columns) => (cut ref row <>)) |
| 215 |
((pair? maybe-default) (car maybe-default)) |
| 216 |
(else (error "simple-relation: invalid column:" column)))))) |
| 217 |
|
| 218 |
(define-method relation-modifier ((r <simple-relation>)) |
| 219 |
(let1 columns (ref r 'columns) |
| 220 |
(lambda (row column val) |
| 221 |
(cond |
| 222 |
((find-index (cut eq? <> column) columns) |
| 223 |
=> (cut (setter ref) row <> val)) |
| 224 |
(else (error "simple-relation: invalid column:" column)))))) |
| 225 |
|
| 226 |
(define-method relation-column-getter ((r <simple-relation>) column) |
| 227 |
(let1 ind (find-index (cut eq? <> column) (ref r 'columns)) |
| 228 |
(unless ind (error "simple-relation: invalid column:" column)) |
| 229 |
(lambda (row) (ref row ind)))) |
| 230 |
|
| 231 |
(define-method relation-column-setter ((r <simple-relation>) column) |
| 232 |
(let1 ind (find-index (cut eq? <> column) (ref r 'columns)) |
| 233 |
(unless ind |
| 234 |
(error "simple-relation: invalid column:" column)) |
| 235 |
(lambda (row v) (set! (ref row ind) v)))) |
| 236 |
|
| 237 |
(define-method relation-coercer ((r <simple-relation>)) identity) |
| 238 |
|
| 239 |
(define-method relation-insertable? ((r <simple-relation>)) #t) |
| 240 |
(define-method relation-insert! ((r <simple-relation>) (row <sequence>)) |
| 241 |
(unless (= (size-of row) (length (ref r 'columns))) |
| 242 |
(error "simple-relation: attempt to insert a row that doesn't match the relation:" row)) |
| 243 |
(push! (ref r 'rows) row)) |
| 244 |
|
| 245 |
(define-method relation-deletable? ((r <simple-relation>)) #t) |
| 246 |
(define-method relation-delete! ((r <simple-relation>) (row <sequence>)) |
| 247 |
(update! (ref r 'rows) (cut delete! row <> equal?))) |
| 248 |
|
| 249 |
;; |
| 250 |
;; <object-set-relation> |
| 251 |
;; |
| 252 |
|
| 253 |
(define-class <object-set-relation> (<relation> <collection>) |
| 254 |
((class :init-keyword :class :init-value <object>) |
| 255 |
(rows :init-keyword :rows :init-value '()) ;; list of instances of class |
| 256 |
)) |
| 257 |
|
| 258 |
(define-method call-with-iterator ((r <object-set-relation>) proc . keys) |
| 259 |
(apply call-with-iterator (ref r 'rows) proc keys)) |
| 260 |
|
| 261 |
(define-method relation-rows ((r <object-set-relation>)) |
| 262 |
(slot-ref r 'rows)) |
| 263 |
|
| 264 |
(define-method relation-column-names ((r <object-set-relation>)) |
| 265 |
(map slot-definition-name (class-slots (ref r 'class)))) |
| 266 |
|
| 267 |
(define-method relation-column-name? ((r <object-set-relation>) column) |
| 268 |
(find (lambda (slot) (eq? column (slot-definition-name slot))) |
| 269 |
(class-slots (ref r 'class)))) |
| 270 |
|
| 271 |
(define-method relation-column-getter ((r <object-set-relation>) column) |
| 272 |
(unless (relation-column-name? r column) |
| 273 |
(error "object-set-relation: invalid column name:" column)) |
| 274 |
(lambda (row) (slot-ref row column))) |
| 275 |
|
| 276 |
(define-method relation-column-setter ((r <object-set-relation>) column) |
| 277 |
(unless (relation-column-name? r column) |
| 278 |
(error "object-set-relation: invalid column name:" column)) |
| 279 |
(lambda (row v) (slot-set! row column v))) |
| 280 |
|
| 281 |
(define-method relation-accessor ((r <object-set-relation>)) |
| 282 |
slot-ref) |
| 283 |
|
| 284 |
(define-method relation-modifier ((r <object-set-relation>)) |
| 285 |
slot-set!) |
| 286 |
|
| 287 |
(define-method relation-coercer ((r <object-set-relation>)) |
| 288 |
(lambda (row) |
| 289 |
(map (^s (slot-ref row s)) (relation-column-names r)))) |
| 290 |
|
| 291 |
(define-method relation-insertable? ((r <object-set-relation>)) #t) |
| 292 |
(define-method relation-insert! ((r <object-set-relation>) row) |
| 293 |
(unless (is-a? row (ref r 'class)) |
| 294 |
(error "object-set-relation: attempt to insert an object of mismatched class:" row)) |
| 295 |
(push! (ref r 'rows) row)) |
| 296 |
|
| 297 |
(define-method relation-deletable? ((r <object-set-relation>)) #t) |
| 298 |
(define-method relation-delete! ((r <object-set-relation>) row) |
| 299 |
(update! (ref r 'rows) (cut delete! row <> equal?))) |