Debian Codegraph @

lib/util/relation.scm

raw
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?)))