/************************************************************************* * 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-Division ist die Umkehrung 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 w_id 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) 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-Vergleich 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.