-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathrelational-algebra-talk.html
607 lines (584 loc) · 24.2 KB
/
relational-algebra-talk.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
<!doctype html>
<html lang="ru">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no">
<title>Relational algebra in Scala3</title>
<meta name="description" content="An experiment on implementing relational algebra in Scala3">
<meta name="author" content="Arseniy Zhizhelev">
<link rel="stylesheet" href="reveal-js/dist/reset.css">
<link rel="stylesheet" href="reveal-js/dist/reveal.css">
<link rel="stylesheet" href="reveal-js/dist/theme/white.css">
<!-- <link rel="stylesheet" href="reveal-js/dist/theme/black.css">-->
<!-- Theme used for syntax highlighting of code -->
<!-- <link rel="stylesheet" href="reveal-js/plugin/highlight/monokai.css">-->
<link rel="stylesheet" href="reveal-js/plugin/highlight/zenburn.css">
<script src="reveal-js/plugin/highlight/highlight.js"></script>
</head>
<body>
<div class="reveal">
<div class="slides">
<section>
<h1>Relational Algebra</h1>
<h3>Scala3</h3>
<p>
<small><a href="https://primetalk.github.io/">Arseniy Zhizhelev, Primetalk</a> / <a href="mailto:[email protected]">[email protected]</a></small>
</p>
<aside class="notes">
<p>In this talk we present an experiment on Relational Algebra implementation in Scala3</p>
</aside>
</section>
<!--
Plan:
1. Introduction:
- Thanks to Martin Oderski for Scala3, DOT calculus,
the advanced type system and macros
- Remind about typed ontology
-
1.1. Type programming hints
- type functions
- type match
- recursive type definition
- inline functions actually driven by types!
1.2. Typed ontology intro
- represent columns/fields/properties using typed objects.
- infer name
- to have singleton type - create object
2. Main part. Relational algebra
2.1. Relational algebra reminder
- what's relation
- operations - projection, selection, cross product, rename, ...
2.2. Basic concept of schema
2.3. Implementation details
- projection
- cross-product
2.4. Stream-based operations.
3. Applications
3.1. Multilayered database applications.
3.2. Schema conversion
- TODO: Good business case
4. Library design
4.1. data -> ontology/schema -> meta ontology -> meta tools
5. Performance
5.1. Compilation (a lot happens at compile time).
5.2. Runtime
6. Conclusion
6.1. Why it's important
6.2. Further plans
-->
<section>
<section style="text-align: left">
<b>Introduction</b>
<ul>
<li>Appreciate Martin Oderski's work for DOT, Scala3 language design</li>
<li class="fragment">Plan:
<ul>
<li class="fragment">Type-level programming</li>
<li class="fragment">Typed ontology</li>
<li class="fragment">Type safe relational algebra
<ul>
<li class="fragment">Compile-time reduction to ordinary tuples/maps/...</li>
<li class="fragment">Compatible with `cats`, `fs2`</li>
</ul>
</li>
</ul>
</li>
</ul>
<aside class="notes">
<ul>
<li>Praise to Martin Oderski for DOT, Scala3 language design</li>
<li class="fragment">Typed ontology was presented previously</li>
<li class="fragment">Type safe relational algebra is possible in Scala3. It's amazing</li>
</ul>
</aside>
</section>
</section>
<section>
<section style="text-align: left">
<b>Reminder: type-level programming</b>
<ul>
<li class="fragment">pattern matching on types</li>
<li class="fragment">recursive types</li>
<li class="fragment">inline (compile time ops)</li>
<li class="fragment">constValue and constValueTuple, erasedValue, ValueOf</li>
<li class="fragment">some limitations (general type projections)</li>
</ul>
</section>
<section style="text-align: left">
<b>type-level pattern matching</b>
<pre><code class="scala" data-trim>
type Element[T] = T match
case List[x] => x
case Option[x] => x
case String => Char
case _ => Nothing
</code></pre>
</section>
<section style="text-align: left">
<b>recursive types</b>
<pre><code class="scala" data-trim>
type Fibonacci[a<:Int, b<:Int, n <:Int] <:Int = n match
case 0 => b
case S[x] => Fibonacci[b, a + b, x]
</code></pre>
</section>
<section style="text-align: left">
<b>transparent inline</b>
<pre><code class="scala" data-trim>
transparent inline def fibonacci[n<:Int](inline a: Int, inline b: Int): Int =
inline erasedValue[n] match
case _: 0 => b
case _: S[x] =>
fibonacci[x](b, a + b)
</code></pre>
</section>
<section style="text-align: left">
<b>constValue</b>
<pre><code class="scala" data-trim>
val F3: Fibonacci[1,1,3] = constValue
F3 should equal(5)
</code></pre>
<pre class="fragment"><code class="scala" data-trim>
constValueTuple[(1, "hello")] should equal((1, "hello"))
</code></pre>
</section>
<section style="text-align: left">
<b>generic type projection (missing)</b>
<pre><code class="scala" data-trim>
trait Collection:
type Element
type CollectionElement[C<:Collection] = C#Element
</code></pre>
<pre class="fragment"><code class="scala" data-trim>
// type C: C
// C is not a legal path
// since it is not a concrete type
</code></pre>
<pre class="fragment"><code class="scala" data-trim>
def collectionElement[C<:Collection](c: C): c.Element = ???
</code></pre>
</section>
</section>
<section>
<section style="text-align: left">
<b>Typed ontology</b>
<ul>
<li>represent columns/fields/properties using typed objects</li>
</ul>
<pre><code class="scala" data-trim>
object Product extends TableBuilder:
object id extends column[Int]
object name extends column[String]
object price extends column[BigInt]
</code></pre>
<ul class="fragment">
<li>object has self type + <code>PropertyId[R, A]</code></li>
<li class="fragment"><code>R = this.type</code> for simplicity</li>
</ul>
</section>
<section style="text-align: left">
<p><b>Schema</b></p>
<ul>
<li>Similar to <code>HList</code> and <code>TupleXXL</code></li>
</ul>
<pre><code class="scala" data-trim>
object Product extends TableBuilder:
type TableSchema =
id.type #: name.type #: price.type #: EmptySchema
val tableSchema: TableSchema =
id #: name #: price #: EmptySchema
</code></pre>
<pre class="fragment"><code class="scala" data-trim>
infix type #:[P <: RecordProperty0, S <: RecordSchema] =
SchemaCons[P, S]
</code></pre>
<aside class="notes">
<p>We construct schema as a tuple</p>
</aside>
</section>
<section style="text-align: left">
<p><b>Instances</b></p>
<ul>
<li>Parallel to schema we construct Values</li>
</ul>
<pre><code class="scala" data-trim>
trait RecordSchema:
type Values = Tuple.Map[Properties, PropertyValue]
</code></pre>
<ul class="fragment">
<li>Tuple of property values</li>
</ul>
<pre class="fragment"><code class="scala" data-trim>
val product1: Product.tableSchema.Values =
(1, "product1", BigInt(5))
//type TableSchema =
// id.type #: name.type #: price.type #: EmptySchema
</code></pre>
<aside class="notes">
<p>We construct schema values as a tuple of property values</p>
</aside>
</section>
<section style="text-align: left">
<p><b>Instances (2)</b></p>
<ul>
<li>Typed maps</li>
</ul>
<pre><code class="scala" data-trim>
trait TypedMap[M[_]]:
def apply[R, P <: RecordProperty[R]](m: M[R])(p: P):
Option[PropertyValueType[p.type]]
def updated[R, P <: RecordProperty[R]](m: M[R])(p: P,
v: Option[PropertyValueType[p.type]]): M[R]
</code></pre>
<pre><code class="scala" data-trim>
opaque type SimpleTypedMap[R] = SortedMap[String, Any]
</code></pre>
<ul class="fragment">
<li>Tuple of options
<pre><code class="scala" data-trim>
type ValuesMap[H[_]] = Tuple.Map[Values, H]
type OptionValues = ValuesMap[Option]
</code></pre></li>
<li class="fragment">Tuple of eithers
<pre><code class="scala" data-trim>
type EitherValues[E] = ValuesMap[[V] =>> Either[E, V]]
</code></pre></li>
</ul>
<aside class="notes">
<p>We construct schema values as a tuple of property values</p>
</aside>
</section>
</section>
<section>
<section style="text-align: left">
<b>Relational algebra</b>
<p></p>
<ul>
<li>relation</li>
<li class="fragment">projection</li>
<li class="fragment">cross product</li>
<li class="fragment">selection</li>
<li class="fragment">join on a foreign key</li>
<li class="fragment">replace, rename</li>
<li class="fragment">calculate column</li>
</ul>
</section>
<section style="text-align: left">
<b>Relational algebra: relation</b>
<p></p>
<ul>
<li>relation = schema + data</li>
</ul>
<pre class="fragment"><code class="scala" data-trim>
abstract class Relation[V[_]]:
type Schema <: RecordSchema
val schema: Schema
type Row = schema.Values
val rows: V[schema.Values]
</code></pre>
</section>
<section style="text-align: left">
<b>Relational algebra: projection</b>
<p></p>
<ul>
<li>One schema S1 and another one S2 that contains some of the same properties</li>
<li class="fragment">Projection is removing some data from each instance and rearranging the other values</li>
<li class="fragment">We do it from side of schema S2 and select proper elements from S1</li>
</ul>
</section>
<section style="text-align: left">
<b>Relational algebra: projection (2)</b>
<p></p>
<pre class="fragment"><code class="scala" data-trim>
transparent inline def projectorFrom
[S1 <: RecordSchema]
(inline s1: S1): s1.Values => Values =
</code></pre>
<pre class="fragment"><code class="scala" data-trim>
val fp = s1.propertyGetter(p)
val fschema: s1.Values => schema.Values =
schema.projectorFrom(s1)
(v: s1.Values) => fp(v) *: fschema(v)
</code></pre>
<ul>
<li class="fragment">for each property of the target schema
construct a getter from a tuple of values. Then combine into a single tuple.</li>
</ul>
</section>
<section style="text-align: left">
<b>Relational algebra: cross product (1)</b>
<ul>
<li>concatenate schemas</li>
</ul>
<pre class="fragment"><code class="scala" data-trim>
type AppendOtherSchema[S2 <: RecordSchema] <: RecordSchema
transparent inline def appendOtherSchema[S2 <: RecordSchema]
(inline s2: S2): AppendOtherSchema[S2]
</code></pre>
<pre class="fragment"><code class="scala" data-trim>
type AppendOtherSchema[S2 <: RecordSchema] =
SchemaCons[P, schema.AppendOtherSchema[S2]]
transparent inline def appendOtherSchema[S2 <: RecordSchema]
(inline s2: S2): AppendOtherSchema[S2] =
p #: schema.appendOtherSchema(s2)
</code></pre>
<ul>
<li class="fragment">instead of patter matching on types, we use abstract types here</li>
</ul>
</section>
<section style="text-align: left">
<b>Relational algebra: cross product (2)</b>
<ul>
<li>construct a function that will concatenate values</li>
</ul>
<p></p>
<pre class="fragment"><code class="scala" data-trim>
transparent inline def appendValues[S2 <: RecordSchema]
(inline schema2: S2)
(inline schema3: AppendOtherSchema[S2]):
(Values, schema2.Values) => schema3.Values =
</code></pre>
<pre class="fragment"><code class="scala" data-trim>
(v1, v2) => (v1 ++ v2).asInstanceOf[schema3.Values]
</code></pre>
</section>
<section style="text-align: left">
<b>Relational algebra: cross product (3)</b>
<ul>
<li>iterate through all pairwise combinations</li>
</ul>
<pre class="fragment"><code class="scala" data-trim>
transparent inline def crossProductFrom[R1 <: Relation[V]]
(inline r1: R1)(using FlatMap[V]): Relation[V] =
</code></pre>
<pre class="fragment"><code class="scala" data-trim>
import cats.FlatMap.ops.toAllFlatMapOps
val schema3 = r1.schema.appendOtherSchema(schema)
val concatValues: (r1.schema.Values, schema.Values) => schema3.Values =
r1.schema.appendValues(schema)(schema3)
val vals =
for
row1 <- r1.rows
row2 <- this.rows
yield
concatValues(row1, row2)
Relation(schema3)(vals)
</code></pre>
</section>
<section style="text-align: left">
<b>Relational algebra: join on foreign key</b>
<ul>
<li>= cross product + filter</li>
</ul>
<pre class="fragment"><code class="scala" data-trim>
transparent inline def join[FK <: ForeignKeyId0, R2 <: Relation[V]]
(inline fk: FK)(inline r2: R2)(using FlatMap[V])(using FunctorFilter[V]) =
</code></pre>
<pre class="fragment"><code class="scala" data-trim>
import cats.FlatMap.ops.toAllFlatMapOps
import cats.FunctorFilter.ops.toAllFunctorFilterOps
val schema3 = schema.appendOtherSchema(r2.schema)
val concatValues: (schema.Values, r2.schema.Values) => schema3.Values =
schema.appendValues(r2.schema)(schema3)
val pred: schema3.Values => Boolean = schema3.fkPredicate(fk)
val vals =
for
row1 <- this.rows
row2 <- r2.rows
row3 = concatValues(row1, row2)
// if pred(row3)
yield
row3
val filtered = vals.filter(pred)
Relation[schema3.type, V](schema3)(filtered)
</code></pre>
<pre class="fragment"><code class="scala" data-trim>
transparent inline def fkPredicate[FK <: ForeignKeyId0](inline fk: FK): Values => Boolean =
</code></pre>
<pre class="fragment"><code class="scala" data-trim>
val l = propertyGetter(fk.left)
val r = propertyGetter(fk.right)
row => l(row) == r(row)
</code></pre>
</section>
<section style="text-align: left">
<b>Relational algebra: replace, rename</b>
<ul>
<li>match property and replace</li>
</ul>
<pre class="fragment"><code class="scala" data-trim>
transparent inline def replace[P1 <: RecordProperty0, P2 <: RecordProperty0]
(inline p1: P1, inline p2: P2): RecordSchema
</code></pre>
<pre class="fragment"><code class="scala" data-trim>
inline p1 match
case `p` => p2 #: schema
case _ => p #: schema.replace(p1, p2)
</code></pre>
<ul class="fragment">
<li>rename should also maintain
the same type of property value</li>
</ul>
<pre class="fragment"><code class="scala" data-trim>
transparent inline def rename[T, P1 <: RecordProperty[T],
P2 <: RecordProperty[T]]
(inline p1: P1, inline p2: P2): RecordSchema =
replace(p1, p2)
</code></pre>
</section>
<section style="text-align: left">
<b>Relational algebra: calculate column</b>
<ul>
<li>new column</li>
<li class="fragment">formula for it (function)</li>
</ul>
<pre class="fragment"><code class="scala" data-trim>
transparent inline def prependCalcColumn[P <: RecordProperty0]
(inline p: P)(inline f: Row => p.P)(using FlatMap[V]) =
</code></pre>
<pre class="fragment"><code class="scala" data-trim>
val schema3 = p #: schema
val vals = rows.map(row =>
(f(row) *: row)
.asInstanceOf[schema3.Values])
Relation(schema3)(vals)
</code></pre>
</section>
<section style="text-align: left">
<b>Relational algebra: expressions DSL</b>
<ul>
<li>refer to column value just mentioning the name</li>
<li class="fragment">operations</li>
<li class="fragment">convert to a function from `Row =>`</li>
</ul>
<pre class="fragment"><code class="scala" data-trim>
object price extends OrderItem.column[Int]
val p = orderItems.
prependCalcColumn(price)({
import orderItems._
rowFun(
prop(OrderItem.id) * const(10))
})
</code></pre>
<pre class="fragment"><code class="scala" data-trim>
filter(rowFun(
prop(orderId) === const(orderIdValue)))
</code></pre>
</section>
</section>
<section>
<section style="text-align: left">
<b>Applications</b>
<ul>
<li>DB-libraries (Slick-style)</li>
<li class="fragment">big-data frameworks (Spark, Flink)</li>
<li class="fragment">Ontology-driven applications
(DB, App, UI - all driven by schema)</li>
<li class="fragment">CQRS (generic change events for entities)</li>
<li class="fragment">immutable history database (version derived from entity)</li>
</ul>
<aside class="notes">
</aside>
</section>
</section>
<section>
<section style="text-align: left">
<b>Library design (application/library boundary)</b>
<ul>
<li><b>data</b> - application level</li>
<li class="fragment"><b>ontology/schema</b> - application specific schema (entities, attributes, relations,...)</li>
<li class="fragment"><b>meta</b> - application/library instruments to create ontology</li>
<li class="fragment"><b>simple-meta</b> - library where properties just have a string name</li>
<li class="fragment"><b>meta-tools</b> - universal part of the library that supports
creation of different meta implementations</li>
</ul>
</section>
</section>
<section>
<section style="text-align: left">
<b>Performance (theoretical)</b>
<ul>
<li>compile time - all relational algebra operations happen at compile time</li>
<li class="fragment">runtime - at runtime it's tuple operations</li>
<li class="fragment">potential runtime optimizations:
<ul>
<li>macros for tuple operations</li>
<li class="fragment">case class mapping to use specialization</li>
</ul>
</li>
</ul>
</section>
</section>
<section>
<section style="text-align: left">
<p><b>Conclusion</b></p>
<ul>
<li>relational algebra at type level</li>
<li class="fragment">why it's important?</li>
<li class="fragment">what's the difference from Slick?</li>
<li class="fragment">further plans</li>
</ul>
<aside class="notes">
why it's important?
<ul>
<li>direct mapping of SQL - both forward and backward.
We can construct SQL queries and automatically map results to typed entities.</li>
<li>mathematically defined algebra</li>
</ul>
what's the difference from Slick?
<ul>
<li>not tied to databases, could be used in any other projects, with REST services, etc.</li>
<li>type-level properties (not just property types)</li>
<li>projections are producing flat tuples</li>
</ul>
plans
<ul>
<li>json mapping</li>
<li>case class mapping (probably autogeneration?)</li>
</ul>
</aside>
</section>
</section>
<section>
<section>
<b>References</b>
<ul>
<li><a href="https://github.com/Primetalk/typed-ontology">https://github.com/Primetalk/typed-ontology</a></li>
</ul>
</section>
<section style="text-align: left">
<p><b>Thank you for watching</b></p>
<div class="fragment">
<p></p>
<b>Questions?</b>
<p>
<small>Arseniy Zhizhelev, <a href="https://primetalk.github.io/">Primetalk</a> / <a href="mailto:[email protected]">[email protected]</a></small>
</p>
</div>
</section>
</section>
</div>
</div>
<script src="reveal-js/dist/reveal.js"></script>
<script src="reveal-js/plugin/zoom/zoom.js"></script>
<script src="reveal-js/plugin/notes/notes.js"></script>
<script src="reveal-js/plugin/search/search.js"></script>
<script src="reveal-js/plugin/markdown/markdown.js"></script>
<script src="reveal-js/plugin/highlight/highlight.js"></script>
<script>
// Also available as an ES module, see:
// https://revealjs.com/initialization/
Reveal.initialize({
history: true,
controls: true,
progress: true,
center: true,
hash: true,
slideNumber: true,
// showNotes: true,
// Learn about plugins: https://revealjs.com/plugins/
plugins: [ RevealZoom, RevealNotes, RevealSearch, RevealMarkdown, RevealHighlight ]
});
</script>
</body>
</html>