How to reduce a Relational Model to make it more compact.

Armstrong’s Axioms

  • Reflexivity:
  • Augmentation:
  • Transitivity:

Secondary Rules

  • Decomposition:
  • Composition:
  • Union:
  • Pseudo-transitivity:
  • Identity:
  • Extensivity:

Functional Dependency

def. Functional Dependency. If for all tuples in a relation that has the same values for attribute and attribute , then is functionally dependent on .

e.g. an address relation with street, city, state, zip

  • zip(city, state)
    • Zip code determines city and state
  • (zip, state)zip
    • This is a Trivial dependency:=
  • zip(state,zip)
    • This is non-trivial, but not complete,
    • Complete Non-trivial dependency:=

alg. BCNF decomposition procedure. Given a set of dependencies and relation , BCNF decomposition determines a minimally redundant (=row-redundant) Relation.

  1. Choose (non-determinisitcally) a dependency in , let which is non-trivial (= is not a superkey)
  2. Decompose using into two relations
    • has attributes
    • has attributes
  3. Recurse procedure for
  • It’s a non-deterministic process (=there can be multiple ways to decompose a relation). def. Closure. Given dependencies , the closure of set of attributes is all attributes determined by through those dependencies

Finding a Key Using Functional Dependencies

alg. Given set of functional dependencies on relation , find the keys of the schema

  1. For each dependencies , compute the closure of such that .
    1. If doesn’t contain all the attributes of , then augment such that it reaches all the attributes.
      1. i.e., let
      2. then, it must be
    2. Then, is a superkey of . let this be .
    3. Can you reduce this superkey ?
      1. Try taking out one attribute at a time from to create
      2. Is reducible?
      3. → Repeat until we reach something unreducible.
      4. ⇒ The final that is unreducible is a key.
  2. Repeat for all dependencies in .

Multi-value Dependency

def. Multi-value Dependency (MVD). is a multi-value dependency of if…

  • for all tuples with the same values of
  • …if we swapped all the values of them…
  • …those entries also exist in the database. then:

In colloquial terms, we can say that for every determined value of , all tuples with values of “associated” with that must exist too. def. Trivial MVD. Given relation :

  • : Obvious.
  • : Obvious.

def. 4th Normal Form (4NF). if every MVD in relation is such that is always a superkey, then relation is in the 4th Normal Form. Example

Multivalue Dependency Rules

  • Complementation:
  • Augmentation:
  • Transitivity:
    • Automatically means
  • Replication:
  • Coalescence: If 𝑋 ↠ 𝑌 and 𝑍 ⊆ 𝑌 and there is some 𝑊 disjoint from 𝑌 such that 𝑊 → 𝑍, then 𝑋 → 𝑍


Proving theorems about chase. Example: alg. Tuple Generation. To enforce on table

  1. For a determined
    1. Enumerate all availble
    2. Enumerate all available
      1. let
      2. Enumerate all availalbe
    3. Are all combinations available in the table?
      1. If not, add missing ones
  2. For another determined , repeat
  3. Repeat for all

alg. Chase. To prove

  1. Initialization: add two tuples to the initial table
  2. For each MVD (order doesn’t matter):
    1. Tuple Generation: see above
  3. For each FD (order doesn’t matter):
    1. You may infer equalities, e.g.
  4. Does fully available? (= all in table)?
    1. Yes → proven
    2. No → disproven (counterexample)