The Relational Model

Wikipedia · Relational model · CC BY-SA 4.0

A relation is a set of tuples that all share the same attributes. In everyday terms: a table where every row has the same columns. Edgar Codd proposed this model in 1970, replacing navigational databases with pure set theory. Everything in relational databases follows from this one idea.

Relations, tuples, and attributes

A relation is a named set of tuples. Each tuple is an ordered collection of attribute values. Each attribute has a name and a domain (the set of allowed values). The schema defines the attribute names and domains. The instance is the current set of tuples.

Scheme

; A relation is a set of tuples.
; Each tuple maps attribute names to values.
; We represent a relation as a list of association lists.

(define users
  (list
    (list (cons "id" 1) (cons "name" "Alice") (cons "email" "alice@db.io"))
    (list (cons "id" 2) (cons "name" "Bob")   (cons "email" "bob@db.io"))
    (list (cons "id" 3) (cons "name" "Carol") (cons "email" "carol@db.io"))))

; Get an attribute from a tuple
(define (get-attr tuple attr)
  (cdr (assoc attr tuple)))

; Display all names
(for-each
  (lambda (tuple)
    (display (get-attr tuple "name"))
    (display " ")
    (display (get-attr tuple "email"))
    (newline))
  users)

Keys

A superkey is any set of attributes that uniquely identifies a tuple. A candidate key is a minimal superkey (remove any attribute and it stops being unique). The primary key is the candidate key chosen to identify rows. A foreign key references the primary key of another relation, creating links between tables.

Scheme

; Primary key: uniquely identifies each tuple.
; Foreign key: references another relation's primary key.

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

(define orders
  (list
    (list (cons "oid" 101) (cons "user_id" 1) (cons "item" "book"))
    (list (cons "oid" 102) (cons "user_id" 2) (cons "item" "pen"))
    (list (cons "oid" 103) (cons "user_id" 1) (cons "item" "lamp"))))

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

; Look up a user by primary key
(define (find-user uid)
  (let loop ((rows users))
    (cond
      ((null? rows) #f)
      ((= (get-attr (car rows) "id") uid) (car rows))
      (else (loop (cdr rows))))))

; For each order, resolve the foreign key
(for-each
  (lambda (order)
    (let ((user (find-user (get-attr order "user_id"))))
      (display (get-attr user "name"))
      (display " ordered ")
      (display (get-attr order "item"))
      (newline)))
  orders)

Codd's rules

In 1985, Codd published twelve rules (numbered 0 through 12) that a database must satisfy to be considered fully relational. The key ones: all data is represented as values in tables (Rule 1). Null values represent missing data uniformly (Rule 3). The database description is stored in the same relational structure as ordinary data (Rule 4). There is a comprehensive data sublanguage (Rule 5, fulfilled by SQL).

Scheme

; Codd's Rule 1: Information Rule
; All information is represented as values in tables.
; Even metadata (table names, column names) is a table.

(define metadata
  (list
    (list (cons "table" "users")  (cons "column" "id")    (cons "type" "integer"))
    (list (cons "table" "users")  (cons "column" "name")  (cons "type" "text"))
    (list (cons "table" "users")  (cons "column" "email") (cons "type" "text"))
    (list (cons "table" "orders") (cons "column" "oid")   (cons "type" "integer"))
    (list (cons "table" "orders") (cons "column" "user_id") (cons "type" "integer"))))

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

; Query the metadata: what columns does 'users' have?
(display "Columns in 'users':") (newline)
(for-each
  (lambda (row)
    (if (string=? (get-attr row "table") "users")
      (begin
        (display "  ")
        (display (get-attr row "column"))
        (display " : ")
        (display (get-attr row "type"))
        (newline))))
  metadata)

Neighbors

Cross-references

🔗 Abstract Algebra Ch.1 — sets and operations: relations are sets of tuples, keys are set-theoretic constraints

Foundations (Wikipedia)

by june.kim Relational Algebra →