Relational Algebra

Wikipedia · Relational algebra · CC BY-SA 4.0

Relational algebra is a set of operations on relations that produce new relations. Six fundamental operations: select (filter rows), project (pick columns), union, difference, Cartesian product, and rename. Join is derived from these. Every SQL query compiles down to a relational algebra expression.

Select (sigma) — filter rows

Selection picks tuples that satisfy a predicate. It does not change the schema, only the cardinality. In SQL this is the WHERE clause.

Scheme

; Select: filter tuples by a predicate
; sigma_{age > 25}(people)

(define people
  (list
    (list (cons "name" "Alice") (cons "age" 30))
    (list (cons "name" "Bob")   (cons "age" 22))
    (list (cons "name" "Carol") (cons "age" 28))))

(define (get-attr tuple attr) (cdr (assoc attr tuple)))

(define (rel-select predicate relation)
  (filter predicate relation))

(define over-25
  (rel-select
    (lambda (t) (> (get-attr t "age") 25))
    people))

(for-each
  (lambda (t)
    (display (get-attr t "name"))
    (display " age ")
    (display (get-attr t "age"))
    (newline))
  over-25)

Project (pi) — pick columns

Projection picks a subset of attributes from each tuple. Duplicates are removed (relations are sets). In SQL this is the SELECT column list.

Scheme

; Project: keep only specified attributes
; pi_{name}(people)

(define people
  (list
    (list (cons "name" "Alice") (cons "age" 30))
    (list (cons "name" "Bob")   (cons "age" 22))
    (list (cons "name" "Carol") (cons "age" 28))))

(define (project attrs tuple)
  (filter (lambda (pair) (member (car pair) attrs)) tuple))

(define (rel-project attrs relation)
  (map (lambda (t) (project attrs t)) relation))

(define names-only (rel-project (list "name") people))

(for-each
  (lambda (t)
    (display (cdar t))
    (newline))
  names-only)

Join — combine on matching values

A natural join pairs tuples from two relations that agree on shared attribute names. An equi-join matches on a specified condition. The join is the workhorse of relational queries: it reconstructs information that normalization split across tables.

Scheme

; Join: combine tuples where keys match

(define users
  (list
    (list (cons "id" 1) (cons "name" "Alice"))
    (list (cons "id" 2) (cons "name" "Bob"))))

(define orders
  (list
    (list (cons "uid" 1) (cons "item" "book"))
    (list (cons "uid" 2) (cons "item" "pen"))
    (list (cons "uid" 1) (cons "item" "lamp"))))

(define (get-attr tuple attr) (cdr (assoc attr tuple)))

(define (join r1 key1 r2 key2)
  (apply append
    (map (lambda (t1)
      (filter (lambda (x) x)
        (map (lambda (t2)
          (if (equal? (get-attr t1 key1) (get-attr t2 key2))
            (append t1 t2)
            #f))
          r2)))
      r1)))

(define result (join users "id" orders "uid"))

(for-each
  (lambda (t)
    (display (get-attr t "name"))
    (display " -> ")
    (display (get-attr t "item"))
    (newline))
  result)

Union and difference — set operations

Union combines tuples from two union-compatible relations (same schema). Difference returns tuples in the first relation but not the second. Both require matching attribute names and domains.

Scheme

; Union and difference on relations

(define r1
  (list (list (cons "x" 1)) (list (cons "x" 2)) (list (cons "x" 3))))
(define r2
  (list (list (cons "x" 2)) (list (cons "x" 3)) (list (cons "x" 4))))

(define (rel-union a b)
  (let loop ((result a) (remaining b))
    (if (null? remaining) result
      (if (member (car remaining) result)
        (loop result (cdr remaining))
        (loop (append result (list (car remaining))) (cdr remaining))))))

(define (rel-difference a b)
  (filter (lambda (t) (not (member t b))) a))

(define (show label rel)
  (display label)
  (for-each (lambda (t) (display " ") (display (cdar t))) rel)
  (newline))

(show "R1:        " r1)
(show "R2:        " r2)
(show "Union:     " (rel-union r1 r2))
(show "Difference:" (rel-difference r1 r2))

Neighbors

Cross-references

🔑 Logic Ch.6 — predicate logic: queries are predicates over tuples

Foundations (Wikipedia)

← The Relational Model by june.kim SQL Basics →