Ha la 'differenza' operazione di aggiunta espressività ad un linguaggio di query che già comprende 'registrati'?

Question

L'operatore differenza di set (ad esempio, in alcuni EXCEPT SQL varianti) è uno dei molti operatori fondamentali di algebra relazionale. Tuttavia, ci sono alcuni database che non supportano l'operatore differenza impostato direttamente, ma che supporto LEFT JOIN (una sorta di join esterno), e in pratica questo può essere usato al posto di un'operazione di differenza di set per ottenere lo stesso effetto.

Questo significa che la potenza espressiva di un linguaggio di query è lo stesso, anche senza che l'operatore differenza set, fino a quando l'operatore LEFT JOIN viene mantenuta? Come si potrebbe dimostrare questo fatto?

Answer 1

In algebra relazionale, si deve prima fornire una definizione informale di sinistra (esterno) join, e procedere a dimostrare che, rinomina, selezione, join e proiezione può costruire differenza, così come tale differenza, la selezione e l'unione può essere utilizzate per costruire sinistra (esterno) aderire. In realtà, finiremo per farlo in ordine inverso:. Vi mostreremo come costruire sinistra si unisce con le differenze, e quindi vi mostreremo come costruire le differenze utilizzando sinistra si unisce

Let $ R $ e $ S $ hanno $ schemi (R 'T) $ e $ (T, S ') $ rispettivamente, dove $ R' $ e $ S' $ sono i set di attributi in una schema ma non l'altro, e $ T $ è l'insieme di attributi comuni.

Sia $ w = (\ epsilon, \ epsilon, ..., \ epsilon) $ essere la tupla nullo per $ schema $ S '. Cioè, è la tupla consistente di tutti i valori nulli per ogni attributo di $ $ S '. Poi, si definisce lasciato outer join come segue: R LEFT JOIN S è l'insieme di tutte le tuple $ (R, T, S) $ appartenenti allo schema $ (R 'T, S') $ dove ...

1. $ (r, t) $ è una tupla in $ R $;
2. (a) $ (t, s) $ è una tupla di $ S $ o (b) $ s = w $;
3. Se $ (r, t, s) $ è nel set per $ s \ neq w $, quindi $ (r, t, w) $ non è nel set.

Esempio: $ R $ 'schema s è di $ (A_ {1}, A_ {2}, A_ {3}) $, $ S $' schema s è $ (A_ {2}, A_ {3}, A_ {4}) $, e si ha che $ R = \ {(1, 2, 3), (4, 5, 6) \} $ e $ S = \ {(2, 3, 4), (2 , 3, 6) \} $. Con (1) e (2) si ottiene l'intermedio risultato $ \ {(1, 2, 3, 4), (1, 2, 3, 6), (1, 2, 3, \ epsilon), (4, 5, 6, \ epsilon) \} $. Con (3) dobbiamo rimuovere $ (1, 2, 3, \ epsilon) $, dal momento che abbiamo (per esempio) $ (1, 2, 3, 4) $ e $ s = 4 \ neq \ epsilon = w $ . Siamo quindi partiti con $ \ {(1, 2, 3, 4), (1, 2, 3, 6), (4, 5, 6, \ epsilon) \} $, il risultato atteso per un LEFT JOIN.

Teorema:. R LEFT JOIN S è equivalente a (R EQUIJOIN S) UNION ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w)

Prova: (R EQUIJOIN S) ci dà tutto il necessario per (1) e (2 bis). Noi affermiamo che ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w) ci dà tutto della forma (r, t, w) richiesto dalla (2b) e (3).

Per vedere questo, primo avviso che (((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) è l'insieme di tutte le tuple in $ R $ per i quali non v'è alcuna tupla corrispondente a $ S $. Per vedere che, è sufficiente ricordare che proiettando comune attributi su $ R $ e $ S $ (l'attributo set $ T $) e prendendo la differenza, si rimane con tutte e sole le tuple (con schema $ T $) che sono rappresentati in $ R $, ma non $ S $. Con la EQUIJOIN con $ R $, recuperiamo tutti e solo quei tuple in $ R $ che hanno valori per gli attributi in $ T $ che sono presenti in $ R $, ma non in $ S $; cioè, precisamente l'insieme di tuple finora abbiamo rivendicato.

Avanti, notare che lo schema di (((PROJECT_T R) DIFFERENCE (PROJECT_T S)) è la stessa di quella di $ R $ (vale a dire, $ (R 'T) $), mentre lo schema di $ w $ è $ S' $. L'operazione JOIN è quindi un prodotto cartesiano, che si ottengono tutti tuple nella forma $ (r, t, w) $ dove non c'è $ (t, s) $ in $ S $ corrispondenti a $ (r, t) $ in $ R $.

Per vedere che questo è proprio l'insieme di tuple avevamo bisogno di aggiungere alla R EQUIJOIN S per costruire R LEFT JOIN S, considerare quanto segue: per costruzione, (3) è soddisfatta, dal momento R EQUIJOIN S non può contenere $ (r, t, s) $ se ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w) contiene $ (r, t, w) $ (se lo ha fatto, poi la seconda del contenente parte $ (r, t, w) $ sarebbe un controsenso); se dovessimo aggiungere un altro $ (r, t, w) $ non in ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w), allora ci sarebbe un $ (t, s) $ in $ S $ corrispondente a $ (r, t) $ in $ R $, e dalla definizione di EQUIJOIN, $ (r, t, s) $ sarebbe anche in R LEFT JOIN S, una contraddizione di (3). Questo completa la dimostrazione.

Ora dimostriamo che LEFT JOIN può essere utilizzato per differenza costrutto:

Teorema: R DIFFERENCE S è equivalente a PROJECT_T(SELECT_{t'=w}(R LEFT JOIN (SELECT_{s=s'}(((S JOIN RENAME_{T->T'}(S)))))))

La prova: Si noti che qui, $ R '$ e $ S' $ sono vuoti, dal momento che tutti gli attributi sono condivisi per DIFFERENCE di dare un senso. In primo luogo, creiamo un nuovo rapporto da $ S $ per duplicCORTEGGIAMENTO set di attributi in $ S $ (gestita dal RENAME e JOIN) in modo che esso consiste di tuple $ (t, t ') $ sull'attributo set $ (T, T') $ dove $ t = t '$ (gestita dal la SELECT). La sinistra si uniscono ci lascia con tuple nella forma $ (t, t ') $ dove $ t = t' $ o $ t '= w $. Ora, per sbarazzarsi di voci che non compaiono anche in $ S $, dobbiamo mantenere solo le tuple nella forma $ (t, w) $, che è gestita dal SELECT più esterno. L'ultima PROJECT si sbarazza del set attributo temporaneo $ T '$ e ci lascia con la differenza in termini di schema originale.

Esempio: Sia $ R = \ {(1, 2), (3, 4), (5, 6) \} $ e $ S = \ {(3, 4), (5, 6), ( 7, 8) \} $. In primo luogo abbiamo get $ S $ con l'attributo RENAMEd Set $ ??T '$: $ \ {(3, 4), (5, 6), (7, 8) \} $. L'operazione JOIN ci dà il prodotto cartesiano con tutti i nove possibili accoppiamenti; questo set non è scritto qui per motivi di formattazione. Il SELECT poi pares questo fino a $ \ {(3, 4, 3, 4), (5, 6, 5, 6), (7, 8, 7, 8) \} $. Il LEFT JOIN con $ R $ dà $ \ {(1, 2, \ epsilon, \ epsilon), (3, 4, 3, 4), (5, 6, 5, 6) \} $. Il SELECT dà $ \ {(1, 2, \ epsilon, \ epsilon) \} $. Il PROJECT dà $ \ {(1, 2) \} $, la risposta desiderata.

Answer 2

LEFT JOIN come attuato da SQL, non produce relazioni come il suo risultato (perché alcuni attributi del risultato non avrà un valore).

Ergo, LEFT JOIN come attuato da SQL, non è una controparte diretta di qualsiasi operatore algebra relazionale.

Ergo, il relazionale operatore differenza non può essere espressa in termini di unione a sinistra (perché LEFT JOIN non può assolutamente essere parte della algebra relazionale, questo essere perché LEFT JOIN produce qualcosa che non è una relazione, violando così la chiusura del algebra).

Ogni insieme di operatori primitivi di un relazionale algebra che soddisfa la chiusura , che io sappia, include sempre la differenza sia relazionale o semidifferenza relazionale altro.