==========================================================================
 COSC3380 - HW1Programming EXAMPLE
 Five tables, the queries that check them, and why each one
 passes or fails.
==========================================================================


 INPUT FILE
 ----------
 T1(a(pk),b,c,d,e)
 T2(a(pk),b,c,d,e)
 T3(a(pk),b,c,d(fk:T4.a),e)
 T4(a(pk),b,c,d,e)
 T5(a(pk),b,c,d,e(fk:T4.a))

 NOTE: the FKs exist only in this text file. The database does NOT
 enforce them. That is why you have to check.


 THE TABLES
 ----------

 T1                     T2                     T3
 a  b  c  d  e          a  b  c  d  e          a  b  c  d  e
 1  1  3  4  5          1  5  3  1  7          1  9  8  1  5
 2  1  8  9  1          2  8  9  1  7          2  8  7  2  4
 3  2  4  2  6          3  2  4  2  6          3  7  6  2  3
 4  2  3  7  2          4  6  1  2  6

 T4                     T5
 a  b  c  d  e          a  b  c  d  e
 1  2  3  4  5          1  1  4  7  1
 2  2  7  5  6          2  1  4  8  2
 3  4  3  6  8          3  2  6  9  3
                        4  2  6  5  9


 EXPECTED ANSWERS
 ----------------
            ref.integrity   normalized
     T1           Y              Y
     T2           Y              N
     T3           Y              Y
     T4           Y              Y
     T5           N              N

     DB referential integrity: N
     DB normalized: N


==========================================================================
 THE TWO TESTS
==========================================================================

 REFERENTIAL INTEGRITY
     holds if    |R|  =  |R JOIN S ON R.fk = S.pk|
     The join drops rows with no match, so a smaller count = orphans.
     No FK declared  ->  trivially Y, no query needed.

 3NF VIOLATION  (for a pair x -> y, where x is not the PK)
     needs BOTH:
         |PROJ_x|  =  |PROJ_xy|     the dependency holds
         |PROJ_x|  <  |T|           the pattern repeats

     One condition alone is not enough.
     Test every non-PK column as x, against every other column as y.
     x -> y and y -> x are DIFFERENT tests. Do both.


==========================================================================
 T1   ref.integrity = Y     normalized = Y
==========================================================================

 REFERENTIAL INTEGRITY
     No FK declared. Trivially Y. No query.

 NORMALIZATION

-- row count and distinct count of each non-PK column

SELECT COUNT(*)           AS n_rows,
       COUNT(DISTINCT b)  AS n_b,
       COUNT(DISTINCT c)  AS n_c,
       COUNT(DISTINCT d)  AS n_d,
       COUNT(DISTINCT e)  AS n_e
FROM t1;

--   n_rows=4   n_b=2   n_c=3   n_d=4   n_e=4
--
--   d and e have 4 distinct values in 4 rows -> unique -> nothing
--   repeats -> they cannot be the left side of a violation. Skip.
--   b and c DO repeat, so they must be tested.

-- test b -> c

SELECT COUNT(*) AS n_bc
FROM (
    SELECT DISTINCT b, c
    FROM t1
) AS proj_bc;

--   n_bc = 4,  n_b = 2.   4 != 2  ->  b -> c does NOT hold.

-- test c -> b

SELECT COUNT(*) AS n_cb
FROM (
    SELECT DISTINCT c, b
    FROM t1
) AS proj_cb;

--   n_cb = 4,  n_c = 3.   4 != 3  ->  c -> b does NOT hold.

--   b -> d, b -> e, c -> d, c -> e all fail the same way.
--   No violation.  T1 is NORMALIZED.

--   THIS IS THE USEFUL CASE: the pattern repeats, but no dependency
--   holds. A program that checks only the first condition gets
--   this wrong.


==========================================================================
 T2   ref.integrity = Y     normalized = N
==========================================================================

 REFERENTIAL INTEGRITY
     No FK declared. Trivially Y.

 NORMALIZATION

SELECT COUNT(*)           AS n_rows,
       COUNT(DISTINCT b)  AS n_b,
       COUNT(DISTINCT c)  AS n_c,
       COUNT(DISTINCT d)  AS n_d,
       COUNT(DISTINCT e)  AS n_e
FROM t2;

--   n_rows=4   n_b=4   n_c=4   n_d=2   n_e=2
--
--   b and c are unique -> skip.
--   d and e repeat -> test them.

-- test d -> e

SELECT COUNT(*) AS n_de
FROM (
    SELECT DISTINCT d, e
    FROM t2
) AS proj_de;

--   n_de = 2,  n_d = 2,  n_rows = 4
--   2 = 2  AND  2 < 4   ->   VIOLATION
--
--   Every d value appears with exactly one e value:
--       d=1 always with e=7
--       d=2 always with e=6
--   and d is not a key.  T2 is NOT NORMALIZED.

--   Now test the reverse, e -> d. What do you get?
--   (Run it. Both directions matter.)


==========================================================================
 T3   ref.integrity = Y     normalized = Y
==========================================================================

 REFERENTIAL INTEGRITY
     FK is d, referencing T4.a.

SELECT COUNT(*) AS n_rows
FROM t3;

SELECT COUNT(*) AS n_joined
FROM t3
JOIN t4
  ON t3.d = t4.a;

--   n_rows = 3,  n_joined = 3.   Equal  ->  Y
--   d values are 1,2,2 and T4.a values are 1,2,3. All present.

-- useful while debugging: shows WHICH rows are orphaned

SELECT t3.a,
       t3.d
FROM t3
LEFT JOIN t4
  ON t3.d = t4.a
WHERE t4.a IS NULL;

--   Empty. No orphans.

 NORMALIZATION

SELECT COUNT(*)           AS n_rows,
       COUNT(DISTINCT b)  AS n_b,
       COUNT(DISTINCT c)  AS n_c,
       COUNT(DISTINCT d)  AS n_d,
       COUNT(DISTINCT e)  AS n_e
FROM t3;

--   n_rows=3   n_b=3   n_c=3   n_d=2   n_e=3
--
--   Only d repeats. Test d against the others.

SELECT COUNT(*) AS n_db
FROM (
    SELECT DISTINCT d, b
    FROM t3
) AS proj_db;

--   n_db = 3,  n_d = 2.   3 != 2  ->  d -> b does NOT hold.
--   Same for d -> c and d -> e.  T3 is NORMALIZED.


==========================================================================
 T4   ref.integrity = Y     normalized = Y
==========================================================================

 REFERENTIAL INTEGRITY
     No FK declared. Trivially Y.
     (T4 is the table OTHERS reference. That does not make it fail.)

 NORMALIZATION

SELECT COUNT(*)           AS n_rows,
       COUNT(DISTINCT b)  AS n_b,
       COUNT(DISTINCT c)  AS n_c,
       COUNT(DISTINCT d)  AS n_d,
       COUNT(DISTINCT e)  AS n_e
FROM t4;

--   n_rows=3   n_b=2   n_c=2   n_d=3   n_e=3
--
--   b and c repeat. Test them.

SELECT COUNT(*) AS n_bc
FROM (
    SELECT DISTINCT b, c
    FROM t4
) AS proj_bc;

--   n_bc = 3,  n_b = 2.   3 != 2  ->  b -> c does NOT hold.
--   b = 2 appears with c = 3 AND c = 7, so b does not determine c.
--   All other pairs fail too.  T4 is NORMALIZED.


==========================================================================
 T5   ref.integrity = N     normalized = N
==========================================================================

 REFERENTIAL INTEGRITY
     FK is e, referencing T4.a.

SELECT COUNT(*) AS n_rows
FROM t5;

SELECT COUNT(*) AS n_joined
FROM t5
JOIN t4
  ON t5.e = t4.a;

--   n_rows = 4,  n_joined = 3.   NOT equal  ->  N
--   e values are 1,2,3,9. T4.a values are 1,2,3.
--   The value 9 does not exist in T4, so that row was dropped
--   by the join.

-- which row is the orphan?

SELECT t5.a,
       t5.e
FROM t5
LEFT JOIN t4
  ON t5.e = t4.a
WHERE t4.a IS NULL;

--   Returns row a=4, e=9.

 NORMALIZATION

SELECT COUNT(*)           AS n_rows,
       COUNT(DISTINCT b)  AS n_b,
       COUNT(DISTINCT c)  AS n_c,
       COUNT(DISTINCT d)  AS n_d,
       COUNT(DISTINCT e)  AS n_e
FROM t5;

--   n_rows=4   n_b=2   n_c=2   n_d=4   n_e=4
--
--   b and c repeat. Test them.

SELECT COUNT(*) AS n_bc
FROM (
    SELECT DISTINCT b, c
    FROM t5
) AS proj_bc;

--   n_bc = 2,  n_b = 2,  n_rows = 4
--   2 = 2  AND  2 < 4   ->   VIOLATION
--
--       b=1 always with c=4
--       b=2 always with c=6
--
--   T5 is NOT NORMALIZED. It fails BOTH checks.


==========================================================================
 WARNING
==========================================================================

 Your program is graded on a DIFFERENT database, with different
 table and column names, and the violation will be in a different
 pair of columns.

 Notice the violations above are in d -> e (T2) and b -> c (T5).
 They move. Generate the column pairs from the input file - do not
 hardcode them.

 Build your own test tables too. Put a violation in c -> e and see
 whether your program still finds it.

==========================================================================