Basi Di Dati : algoritmo conservazione dipendenze
Ragazzi,potreste illustrarmi per favore l'algoritmo per VERIFICARE se una relazione conserva le dipendenze , dopo la decomposizione ?
Risposte
Ciao,
vedi qua. Sono le slide che ho utilizzato per studiare questi bei argomeni di Basi di Dati. Sono molto completi, troverai tutto quello che cerchi, mi sembra che c'è anche lo pseudo-codice con una descrizione dei vari algoritmi.
per il tuo problema: dipende da che decomposizione si tratta, se te sei nel caso 3NF hai già implicata la preservazione delle dipendenze perciò parlare di verifica è inutile. Invece se usi la BCNF non sempre sei fortunato, solo in questo caso penso tu possa parlare di "verifica" con un algoritmo apposito, dovrebbero esserecene alcuni (vedi le slide, vado un po' a memoria).
Se devi implementare qualcosa attento che la verifica o la decomposizione sono problemi esponenziali, solo alcuni algoritmi o implementazioni hanno tempo polinomiale, se ti interessano approfondimenti su questi algoritmi, ti posso dare un link di alcuni articoli
vedi qua. Sono le slide che ho utilizzato per studiare questi bei argomeni di Basi di Dati. Sono molto completi, troverai tutto quello che cerchi, mi sembra che c'è anche lo pseudo-codice con una descrizione dei vari algoritmi.
per il tuo problema: dipende da che decomposizione si tratta, se te sei nel caso 3NF hai già implicata la preservazione delle dipendenze perciò parlare di verifica è inutile. Invece se usi la BCNF non sempre sei fortunato, solo in questo caso penso tu possa parlare di "verifica" con un algoritmo apposito, dovrebbero esserecene alcuni (vedi le slide, vado un po' a memoria).
Se devi implementare qualcosa attento che la verifica o la decomposizione sono problemi esponenziali, solo alcuni algoritmi o implementazioni hanno tempo polinomiale, se ti interessano approfondimenti su questi algoritmi, ti posso dare un link di alcuni articoli
Ti ringrazio per i link ..=)
no , comunque non devo implementare niente , ma effettuare solo esercizi...Ora dò un'occhiata ai link =)
no , comunque non devo implementare niente , ma effettuare solo esercizi...Ora dò un'occhiata ai link =)
se hai avrai problemi, postali pure qua sul forum
A proposito di problemi XD ...sto ripetendo per l'esame di basi di dati e ho qualche dubbio sull'algebra relazionale .
Se ho due relazioni R(ABC ) e S(ABC) :
1) il loro join coincide con l'intersezione ..
2) l'equiJoin con cosa coincide??? e soprattutto il Full join
Se ho due relazioni R(ABC ) e S(ABC) :
1) il loro join coincide con l'intersezione ..
2) l'equiJoin con cosa coincide??? e soprattutto il Full join
L'esercizio è questo ..Date le relazioni R( A B C ) e S ( ABC )
R A B C
a1 b1 c1
a1 b2 c1
a2 b1 c2
S A B C
a1 b2 c1
a2 b2 c1
a2 b2 c2
determinare : R |X| R.A = S.A S
R fullJoin S ;
R A B C
a1 b1 c1
a1 b2 c1
a2 b1 c2
S A B C
a1 b2 c1
a2 b2 c1
a2 b2 c2
determinare : R |X| R.A = S.A S
R fullJoin S ;
Vediamo un po'...
mettiamo \(r \in R \Join s \in S =\ r \in R \cap \ s \in S \Longleftrightarrow r=s\) perciò se $S=R$.
L'equi-join è un theta-join con uguaglianza (selezione di due attributi con relazione di uguaglianza).
il full-join a quanto ricordo è l'unione del left-join e il right-join. Praticamente un mega join dove ci cerca di riunire gli attribuiti uguali, ma anche quelli tipo con valori non inizializzati (a destra dell'operatore e sinistra).
In pratica prendi tutti i valori di left e li combini con tutti i valori di right (se non c'è corrispondenza metti NULL).
questo è un equi-join. Facendo il join, produci solo gli elementi che selezionati secondo la regola sono uguali.
a1 b1 c1 _______
a1 b2 c1 a1 b2 c1
a2 b1 c2 _______
_______ a2 b2 c1
_______ a2 b2 c2
dovrebbe essere così
Se ho due relazioni R(ABC ) e S(ABC) :
1) il loro join coincide con l'intersezione ..
mettiamo \(r \in R \Join s \in S =\ r \in R \cap \ s \in S \Longleftrightarrow r=s\) perciò se $S=R$.
2) l'equiJoin con cosa coincide???
L'equi-join è un theta-join con uguaglianza (selezione di due attributi con relazione di uguaglianza).
e soprattutto il Full join
il full-join a quanto ricordo è l'unione del left-join e il right-join. Praticamente un mega join dove ci cerca di riunire gli attribuiti uguali, ma anche quelli tipo con valori non inizializzati (a destra dell'operatore e sinistra).
In pratica prendi tutti i valori di left e li combini con tutti i valori di right (se non c'è corrispondenza metti NULL).
"slevyn":
R |X| R.A = S.A S
questo è un equi-join. Facendo il join, produci solo gli elementi che selezionati secondo la regola sono uguali.
R fullJoin S ;
a1 b1 c1 _______
a1 b2 c1 a1 b2 c1
a2 b1 c2 _______
_______ a2 b2 c1
_______ a2 b2 c2
dovrebbe essere così
allora per effettuare un equijoin o tetaJoin dovrei effettuare PRIMA il prodotto cartesiano, ovvero la combinazione di tutte le tuple e POI selezionare quelle che mi richiede la selezione ?
Inoltre per il full Join io non riesco a vedere le tuple che hanno valori nulli...T_T
Inoltre per il full Join io non riesco a vedere le tuple che hanno valori nulli...T_T
Scusami XD il Full Join l'ho capito.. riprovato l'esercizio =)
Ora l'ultimo dubbio è quello riguardante il teta Join : nel teta join si effettua PRIMA il prodotto cartesiano di tutte le tuple delle relazioni e poi si selezionano quelle in cui è soddisfatta la condizione giusto ?
Ora l'ultimo dubbio è quello riguardante il teta Join : nel teta join si effettua PRIMA il prodotto cartesiano di tutte le tuple delle relazioni e poi si selezionano quelle in cui è soddisfatta la condizione giusto ?
"slevyn":
Inoltre per il full Join io non riesco a vedere le tuple che hanno valori nulli...T_T
"slevyn":
Scusami XD il Full Join l'ho capito.. riprovato l'esercizio =)
ok.
I valori nulli li avevo sritti con ___ per allineare il tutto
Però a rivederlo ora mi fai venire un dubbio. Di solito in qualsiasi linguaggio relazione si considerano gli attributi di ogni relazione indipendenti, cioè scritti come S.A R.A ecc... in questo esercizio non vorrei che si chiedesse un qualcosa di diverso. hai la soluzione?
allora per effettuare un equijoin o tetaJoin dovrei effettuare PRIMA il prodotto cartesiano, ovvero la combinazione di tutte le tuple e POI selezionare quelle che mi richiede la selezione ?
Ora l'ultimo dubbio è quello riguardante il teta Join : nel teta join si effettua PRIMA il prodotto cartesiano di tutte le tuple delle relazioni e poi si selezionano quelle in cui è soddisfatta la condizione giusto ?
Il prodotto cartesiano è un caso speciale di Join, cioè quando non ci sono attributi uguali es. S(A,B) e R(C,D) e messe in join risulterà un prodotto cartesiano.
Puoi partire come vuoi, non sei un computer...
Se sei comodo a scriverti prima le tuble uguali e poi combinarle o fatti un join naturale e poi schiumi i risultati
Il punto è questo : quando effettuo il join tra due relazioni con SCHEMI UGUALI , il join coincide con l'intersezione . E fin qui ci siamo . Quando invece ho il TETA JOIN su SCHEMI UGUALI ,come devo procedere ? Non abbiamo detto che il join tra schemi uguali coincide con l'interesezione ?
"slevyn":
Il punto è questo : quando effettuo il join tra due relazioni con SCHEMI UGUALI , il join coincide con l'intersezione .
ok.
Quando invece ho il THETA JOIN SCHEMI UGUALI ,come devo procedere ? Non abbiamo detto che il join tra schemi uguali coincide con l'interesezione ?
ridimmi la definizione di theta join e natural join, che differenza c'è?
ah per il full-join in questo particolare caso (dove non siamo in un linguaggio reale e non ci sono alias di attributi) il risultato è una semplice unione.
a1 b1 c1
a1 b2 c1
a2 b1 c2
a2 b2 c1
a2 b2 c2
mi ha fatto pensare per un po', scusa per il refuso ieri ho pensato in altro modo
il teta join è un prodotto cartesiano seguito da selezione ...ma se ho due schemi uguali , sbaglio o il prodotto cartesiano non si può fare? Quindi non si può fare il teta join su schemi uguali ?
Invece il natural join è basato sull'unire le tuple uguali sugli attributi comuni !
Invece il natural join è basato sull'unire le tuple uguali sugli attributi comuni !
"slevyn":
il teta join è un prodotto cartesiano seguito da selezione ...ma se ho due schemi uguali , sbaglio o il prodotto cartesiano non si può fare? Quindi non si può fare il teta join su schemi uguali ?
infatti bisogna rinominare gli attribuiti uguali di relazioni diverse e poi selezionare quelli secondo la regola data.
C'è un'uguaglianza che adesso non ricordo, un natural join si può esprimere tramite theta-join con ridenominazione, proiezione e selezione
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo