/*************************************************************************
 * Division
 *************************************************************************/

--
-- Frage: Welche Händler liefern alle Waren?
--
-- Die Beantwortung der Frage erfolgt ausschließlich mit Hilfe 
-- der Tabelle "liefert". Es wird dabei vorausgesetzt, dass
-- in dieser Tabelle alle Waren enthalten sind, die geliefert
-- werden können. Sollte es Waren geben können, die von überhaupt
-- keinen Händler geliefert werden, so müsste man zusätzlich
-- auf die Tabelle "ware" zugreifen. Das würde die Anfrage 
-- aufblähen und vom Prinzip der Lösung von Für-Alle-Anfragen 
-- ablenken.
--
-- Um das Prinzip zu demonstrieren, wird außerdem nur die 
-- ID der jeweiligen Händler ausgegeben. Ansonsten müsste ₐ
-- man auf jeden Fall die Tabelle "haendler" verwenden, 
-- um dessen Namen und Adresse zu ermitteln. Das würde die 
-- Anfrage weiter aufblähen.
--

-- Mengen-Disision ist die Umkrehrung des 
-- kartesischen Produktes: (r ✕ s) ÷ s = r

-- Die Division kann mittels des kartesischen Produktes
-- und doppelter Verneinung definiert werden:
-- r ÷ s := πₐ(r) \ πₐ((πₐ(r)✕s)\r)
-- wobei a = r-Attribute ohne s-Attribute



-- Ausgangslage

-- Tabelle r:
SELECT DISTINCT h_id, w_id
FROM   liefert
;

-- Tabelle s:
SELECT wid
FROM   ware
;

-- a = {hid, wid}\{w_id} = {h_id}

-- Alle Händler, die Waren liefern: 
-- πₐ(r)
SELECT DISTINCT h_id
FROM   liefert
;

-- Was wäre, wenn jeder Händler alles liefern würde?
-- πₐ(r)✕s
SELECT h_id, w_id
FROM   (SELECT DISTINCT h_id
        FROM   liefert
       ) AS alle_haendler
       CROSS JOIN
       ware
;

-- Welche Händler liefern welche Waren NICHT (EXCEPT)?
-- (πₐ(r)✕s)\r
SELECT h_id, w_id
FROM   (SELECT DISTINCT h_id
        FROM liefert
       ) AS alle_haendler
       CROSS JOIN
       ware
EXCEPT
SELECT h_id, w_id
FROM   liefert
;

-- Welche Händler liefern nicht alle Waren? 
-- πₐ((πₐ(r)✕s)\r)
SELECT DISTINCT h_id
FROM   (SELECT h_id, w_id
        FROM   (SELECT DISTINCT h_id
                FROM liefert
               ) AS alle_haendler
               CROSS JOIN
               ware
       EXCEPT
       SELECT h_id, w_id
       FROM   liefert
      ) AS wer_liefert_was_nicht
;

-- Welche Händler liefern alle Waren? 
-- r ÷ s = πₐ(r) \ πₐ((πₐ(r)✕s)\r)
SELECT DISTINCT h_id
FROM   liefert
EXCEPT
SELECT DISTINCT h_id
FROM   (SELECT h_id, w_id
        FROM   (SELECT DISTINCT h_id
                FROM   liefert
               ) AS alle_haendler
               CROSS JOIN
               ware
        EXCEPT
        SELECT h_id, w_id
        FROM   liefert
       ) AS wer_liefert_was_nicht
;

-- Oder (effizienter) mit zusätzlicher Benutzung der Händler-Tabelle.
-- Aber immer noch ineffizient wegen CROSS JOIN.
SELECT h_id
FROM   haendler
EXCEPT
SELECT h_id
FROM   (SELECT h_id, w_id
        FROM   (SELECT h_id
                FROM   haendler
               ) AS alle_haendler
               CROSS JOIN
               ware
       EXCEPT
       SELECT h_id, w_id
       FROM   liefert
      ) AS wer_liefert_was_nicht
;

-- Die obige Lösung basiert auf dem Cross Join und ist damit sehr
-- ineffizient. Effizienter geht es mit dem Exists-Operator 
-- und doppelter Verneinung. 
SELECT DISTINCT l1.h_id
FROM   liefert l1
WHERE  NOT EXISTS
       (SELECT w_id 
        FROM   ware
        EXCEPT
        SELECT l2.w_id 
        FROM   liefert l2
        WHERE  l2.h_id = l1.h_id
       )
;

-- Oder noch performanter (da keine Duplikate entfernt werden müssen) .
SELECT h.h_id
FROM   haendler h
WHERE  NOT EXISTS
       (SELECT w_id
        FROM   ware
        EXCEPT
        SELECT l.w_id
        FROM   liefert l
        WHERE  l.h_id = h.h_id
       )
;

-- Alternative mit zweimal NOT EXISTS (doppelte Korrelation: sehr schlecht!) .
SELECT h.h_id
FROM   haendler h
WHERE  NOT EXISTS
       (SELECT *
        FROM   ware w
        WHERE  NOT EXISTS
               (SELECT *
                FROM   liefert l
                WHERE  l.h_id = h.h_id 
                   AND l.w_id = w.w_id
               )
       )
;


-- Alternativen mit Zählen (auch sehr effizient)
-- Hier muss nicht vorausgesetzt werden, dass jede Ware 
-- auch geliefert wird.
SELECT    l.h_id, COUNT(DISTINCT w_id) AS anzahl -- anzahl war nicht gefragt
FROM      liefert l
GROUP  BY l.h_id
HAVING    COUNT(DISTINCT w_id) 
        = (SELECT COUNT(*) FROM ware)
;

SELECT h_id
FROM   (SELECT   h_id, COUNT(DISTINCT w_id) AS l_anzahl_waren
        FROM     liefert l
        GROUP BY h_id
       ) l
WHERE  (SELECT COUNT(*) FROM ware) = l_anzahl_waren
;

SELECT h_id
FROM   (SELECT   h_id, COUNT(DISTINCT w_id) AS l_anzahl_waren
        FROM     liefert l
        GROUP BY h_id
       ) l,
       (SELECT COUNT(*) AS w_anzahl_alle_waren 
        FROM   ware
       ) w
WHERE l_anzahl_waren = w_anzahl_alle_waren
;

-- Mit Ausgabe von Name und Ortschaft des Händlers.
SELECT h.h_id, h_name, h_ortschaft
FROM   haendler h
WHERE    (SELECT COUNT(*) FROM ware)
       = (SELECT COUNT(DISTINCT w_id)
          FROM   liefert l
          WHERE  l.h_id = h.h_id
         )
;

SELECT h.h_id, h_name, h_ortschaft
FROM   haendler h,
       LATERAL
       (SELECT COUNT(DISTINCT w_id) AS l_anzahl_waren
        FROM   liefert l
        WHERE  l.h_id = h.h_id
       ) l
WHERE  (SELECT COUNT(*) FROM ware) = l_anzahl_waren
;

SELECT h.h_id, h_name, h_ortschaft
FROM        haendler h
       JOIN LATERAL 
            (SELECT COUNT(DISTINCT w_id) AS l_anzahl_waren
             FROM   liefert l
             WHERE  l.h_id = h.h_id
            ) l
         ON (SELECT COUNT(*) FROM ware) = l_anzahl_waren
;

SELECT h.h_id, h_name, h_ortschaft
FROM   haendler h,
       LATERAL 
       (SELECT COUNT(DISTINCT w_id) AS l_anzahl_waren
        FROM   liefert l
        WHERE  l.h_id = h.h_id
       ) l,
       (SELECT COUNT(*) AS w_anzahl_alle_waren 
        FROM   ware
       ) w
WHERE l_anzahl_waren = w_anzahl_alle_waren
;

SELECT h.h_id, h_name, h_ortschaft
FROM        haendler h,
            LATERAL 
            (SELECT COUNT(DISTINCT w_id) AS l_anzahl_waren
             FROM   liefert l
             WHERE  l.h_id = h.h_id
            ) l
       JOIN (SELECT COUNT(*) AS w_anzahl_alle_waren 
             FROM   ware
            ) w
         ON l_anzahl_waren = w_anzahl_alle_waren
;

/* *********** Alternative mit Mengenvergleich ***********
  (kein Standard-SQL; funktioniert nicht in PostgreSQL, 
   funktioniert in Transbase)
*/

/*
SELECT   h.h_id
FROM     haendler h
WHERE    (SELECT l.w_id FROM liefert l WHERE l.h_id = h.h_id)
         =
         (SELECT w.w_id FROM ware w)
;
*/

/* Mengen-Vergelich in Standard-SQL:
   A Teilmenge von B und B Teilmenge von A
   <=>
   NOT EXISTS
   (SELECT * FROM A EXCEPT SELECT * FROM B)
   AND
   NOT EXISTS
   (SELECT * FROM B EXCEPT SELECT * FROM A)

Da (SELECT l.w_id FROM liefert l) stets eine Teilmenge
von (SELECT w.w_id FROM ware w) ist, kann man hier
auf diesen Teilmengentest verzichten.
*/

SELECT   h.h_id
FROM     haendler h
WHERE    NOT EXISTS
         ((SELECT w.w_id FROM ware w)
          EXCEPT
          (SELECT l.w_id FROM liefert l WHERE l.h_id = h.h_id)
         );
-- Diese Lösung wurde schon weiter oben aufgeführt. Hier wurde
-- sie nur anders begründet.