Database - schedule serial & conflict serializable

[Black27]

Buondì! Fra qualche giorno devo fare l'esame di basi di dati. Sto studiando gli esercizi per scoprire se uno schedule è conflict serializable. E fin qui ci sono (basta vedere se il grafo delle transazioni è aciclico: in quel caso è conflict serializable, nel caso ci siano dei cicli non è conflict serializable). Poi viene richiesto di trovare una schedule seriale equivalente a quella di partenza, nel caso fosse conflict serializable. Come si fa?

[hamming_burst]

Ma cosa intendi con "equivalente" view-equivalence, conflict equivalence... o si parla proprio di equivalenza in generale...
se mostri un esercizio che non hai risolto, forse è più facile aiutarti

[Black27]

Comunque un testo di un esame a caso è questo:

Indicare se il programma è conflict-serialzable. In caso affermativo, scrivere una corretta esecuzione seriale equivalente
r2(E) r2(C) r1(D) w1(B) r3(E) w3(A) w2(C) w4(D) r4(A) w3(B)

Non penso che intenda view-equivalence...Che intenda 'raggruppare' tutte le transazioni, in un ordine secondo il quale l'ordine di esecuzione conflict-serializable non venga sconvolta?

[Black27]

Guarda alla fine ci sono arrivato da solo...Scrivo qui come ho fatto nel caso qualcuno cercasse la soluzione!

Guardando il grafo della schedule conflict-serializable, basta creare un'altra schedule ordinata per
numero transazione (ordinati per) -> attributo transazione (ordinati per) -> read e poi write
partendo da un nodo da cui partono dei cammini, scegliendo ogni volta un nodo seguente. Se c'è un bivio si sceglie uno dei due. Una volta creata la schedule seriale, basta provare a ricreare il grafo da quest'ultima: dev'essere identico a quello della schedule conflict-serializable, altrimenti non è equivalente!
Ad esempio prendendo le transazioni in quest'ordine T1 – T2 – T3 – T4 si ha una schedule seriale che è la seguente
R1(D) W1(B) R2(C) W2(C) R2(E) W3(A) W3(B) R3(E) R4(A) W4(D)

è corretto, infatti ricreando il grafo si ha un grafo equivalente a quello iniziale! Si può controllare il grafo con questa applet http://www-stud.uni-due.de/~selastoe/?m ... ence#graph

Il procedimento è un po' empirico, ma non ho trovato di meglio! XD

Comunque quest'anno è diverso dagli anni scorsi, ha aggiunto anche ottimizzazione di query e euristiche, quindi ha reso la cosa più incasinata XD inoltre ha rimosso la parte delle dipendenze funzionali (si, avevo fatto una domanda in merito, prima di scoprire che in realtà non le chiede >.<). In generale la materia però mi piace, e mi son preso per tempo a studiarla, quindi non ci saranno grandi problemi (spero XD)

[Black27]

Anzi visto che ci sono ne approfitto e faccio una domanda: Come posso portare un'istruzione ALL in algebra relazionale? (tipo attributo >= ALL( ))

[hamming_burst]

Come posso portare un'istruzione ALL in algebra relazionale? (tipo attributo >= ALL( ))

questo non credo si possa proprio fare. Essendo ALL un operatore aggregato, riveste la caratterista di essere qualcosa che va oltre una semplice algebra, composta da operatori "semplici" che si basano su selezione, ecc...

[Black27]

Ma se facessi tipo val = (SELECT MAX(attributo) FROM ) si potrebbe fare? Annidando una sottoquery nella FROM? Tecnicamente è un >=ALL

[hamming_burst]

"Black27":Ma se facessi tipo val = (SELECT MAX(attributo) FROM ) si potrebbe fare? Annidando una sottoquery nella FROM? Tecnicamente è un >=ALL

questo di cui parli ora è un altro discorso, qua utilizzi solo linguaggio più ad alto livello.

Per l'algebra relazionale, ho guardato su di un libro e in effetti, tra delle note, si dice che ci sono delle possibilità di estensione del linguaggio con degli operatori derivati. Non lo sapevo fino ad ora
Cercando ho trovato un interessante articolo, ce ne sono altri prova con google-shoolar:
Extending Relational Algebra and Relational Calculus with set-valued attributes and aggregate functions

A mio parere avere un linguaggio così ricco di operatori non ha una grande utilità se non quella di complicare. L'algebra relazionale è utile nel momento in cui bisogna astrarre una query con qualche ottimizzazione algebra e le equivalenze semantiche, dove sono visibili in modo maggiore rispetto all'SQL. Ed avere operatori base rende questa algebra potente (fino ad un certo punto).

Per il costrutto ALL (definito in SQL) a ripensarci potrebbe essere ridotto alla condizione che una tupla sia con valori NULL o meno ed in caso non considerarli, si potrebbe fare una condizione sul costrutto di theta-join; dovrei pensarci meglio

[Black27]

Grazie mille fra un'oretta ho l'esame, ma poi approfondisco comunque per curiosità!