Nella teoria dei database , il teorema di Codd afferma l'equivalenza tra algebra relazionale e calcolo relazionale (limitato a query indipendenti dal dominio). Questo teorema è importante per i database relazionali , perché assicura che qualsiasi query "naturale" (cioè calcolo relazionale) possa essere tradotta in algebra relazionale, e quindi in un linguaggio di query intelligibile da un computer (in particolare SQL ). Questo teorema è stato dimostrato da Edgar Frank Codd nel 1971.
Nel modello di database relazionale , una tabella (o relazione) contiene più attributi o campi (colonne) e più righe, chiamate tuple . Una tabella è vista come un insieme (o multinsieme nella maggior parte delle implementazioni) di tuple . Ad esempio, una tabella con due campi (Titolo e Direttore) e tre tuple.
Titolo | Direttore |
---|---|
Colpo di frusta | Damien Chazelle |
Lalaland | Damien Chazelle |
Didier | Alain Chabat |
Esistono due modelli matematici di query.
Il calcolo relazionale corrisponde alla logica del primo ordine senza un simbolo di funzione , ma con adattamenti specifici per i database relazionali. Secondo Serge Abiteboul et al., La sua introduzione risale a una relazione tecnica di JL Kuhns del 1969 in cui utilizzava formule logiche per effettuare query. Ma l'importanza del calcolo relazionale è cresciuta con Codd.
Alcune query dipendono dal dominio. Ad esempio, "dai tutti i titoli dei film che non sono nella relazione Film" è una richiesta per la quale è necessario specificare il dominio. Ad esempio, con il dominio {Whiplash, Lalaland, Didier, Damien Chazelle, Alain, Chabat}, la risposta è vuota. Ma, con il dominio {Whiplash, Lalaland, Didier, Damien Chazelle, Alain, Chabat, Star Wars}, la risposta è {Star Wars}. Estendiamo la semantica di una formula spiegando precisamente il dominio in cui stiamo lavorando. Parliamo di interpretazione relativizzata: una query viene valutata in un database provvisto di dominio.
Il dominio attivo di un database è l'insieme di elementi che appaiono nel database. Nell'esempio sopra, è {Whiplash, Lalaland, Didier, Damien Chazelle, Alain, Chabat}.
Una query è indipendente dal dominio se la sua soluzione è indipendente dal dominio e dipende solo dal database. Ad esempio, "Dai tutti i titoli dei film diretti da Damien Chazelle" è indipendente dal dominio. D'altra parte, "dare tutti i titoli dei film che non sono nella relazione Film", dipende dal dominio.
Per le query indipendenti dal dominio, è quindi sufficiente eseguire la query su un database utilizzando il dominio attivo.
L'algebra relazionale descrive le operazioni sulle relazioni. In questo articolo, siamo interessati alle seguenti operazioni:
Una prima versione del teorema di Codd afferma l'equivalenza tra calcolo connettivo (solo le congiunzioni sono usate nelle query di calcolo relazionale) e l'algebra SPC (prendi una relazione R, prendi m tuple, selezioni, proiezioni, prodotti cartesiani) soddisfacente.
Una seconda versione del teorema di Codd afferma l'equivalenza tra algebra relazionale (intera) e calcolo relazionale limitato a query indipendenti dal dominio.
La tabella seguente mostra come trasformare una query di algebra relazionale senza nome in una query di calcolo relazionale equivalente, indipendente dal dominio. La costruzione avviene per induzione su richiesta dell'algebra relazionale. Ricordiamo che il simbolo ∨ designa la disgiunzione (o), il simbolo ∧ designa la congiunzione (e), il simbolo ¬ designa la negazione (no).
Query di algebra relazionale | Query corrispondente nel calcolo relazionale, indipendente dal dominio |
---|---|
Una relazione R | R (x 1 , ... x arità (R) )
|
{u 1 , ..., u m } dove u i sono tuple con la stessa arità α | (x 1 = u 1 (1) ∧ ... ∧ x α = u 1 (α)) ∨ .... (x 1 = u m (1) ∧ ... ∧ x α = u m (α) )
|
Una selezione di E con una formula F: σ F (E) | φ E ∧ F 'dove F' è la formula ottenuta sostituendo l'identificatore della coordinata i con x i
|
Proiezione di E su {i 1 , ... i n }: π i1, ... in (E) | ∃y i1 ... ∃y in (x 1 = y i1 ∧ ... x n = y in ) ∧ ∃y j1 ... ∃y jl φ E (y 1 , ... y arity (E) ) dove j 1 , ..., j l = [1, arity (E)] \ {i 1 , ... i n }
|
Prodotto cartesiano: E 1 × E 2 | φ E1 ∧ φ E2 (x arità (E1) +1 , ... x arità (E1) + arità (E2) )
|
Unione: E 1 ∪ E 2 | φ E1 ∨ φ E2
|
Differenza: E 1 - E 2 | φ E1 ∧ ¬φ E2
|
Qualsiasi query nel calcolo relazionale, c'è una query in algebra relazionale che è equivalente ad essa sotto dominio attivo (e quindi in particolare qualsiasi query di calcolo relazionale che è indipendente dal dominio è scritta in algebra relazionale).