[DATALOG] Query Datalog

[franksisca]

Ho Aperto discussione analoga in scuola e lavor, perchè credo che anche lì mi possano rispondere


Avete materiale sul quale studiare le query in datalog, in particolar modo le query che fanno utilizzo di algebra, tipo "contare n"????


anche altre query in generale andrebbero bene.

[k0nt3]

penso che dovresti procurarti quest'oggetto http://portal.acm.org/citation.cfm?id=627357 anche se io non l'ho letto personalmente (la mia conoscenza di datalog si limita alle pagine 81-87 del "BASI DI DATI - modelli e linguaggi di interrogazione" di Atzeni, Ceri, Paraboschi, Torlone)

[franksisca]

Originariamente inviato da k0nt3

penso che dovresti procurarti quest'oggetto http://portal.acm.org/citation.cfm?id=627357 anche se io non l'ho letto personalmente (la mia conoscenza di datalog si limita alle pagine 81-87 del "BASI DI DATI - modelli e linguaggi di interrogazione" di Atzeni, Ceri, Paraboschi, Torlone)

eheheheh.....peccato che l'esame è martedì



mi servirebbe qualcuno che abbia query svolte, il mio problema non è la logica, ma è come se fossi bloccato al momento della scrittura (credo che sia una cosa comune a molti).


Praticamente a voce risolvo la query in 30 secondi, ma a scriverla mi blocca, eppure sto facendo esercizia a dire basta......e non è nemmeno uno degli esami più difficili che abbia mai fatto.......

[k0nt3]

ma il datalog è fantastico! non puoi fare fatica!! è tutto così bello!!!
fa un esempio che magari ricordo qualcosa

[franksisca]

una query del tipo
"trovate tutte le locazioni raggiunte da x dopo 25 passi".



odio questa tipologia d'esami, perchè ti fanno fare query che nella realtà non farai mai, e non ti fanno vedere mai nemmeno come si crea un database realmente, quanta gente nel mio corso mi chiedeva cosa doveva scaricare per creare un db per fare prove, e io stesso per datalog sto facendo tutto su carta, perchè su pc non ho trovato niente di decente.

[k0nt3]

Originariamente inviato da franksisca

una query del tipo
"trovate tutte le locazioni raggiunte da x dopo 25 passi".

eh si ma dipende da che base di dati hai a disposizione

Originariamente inviato da franksisca

odio questa tipologia d'esami, perchè ti fanno fare query che nella realtà non farai mai, e non ti fanno vedere mai nemmeno come si crea un database realmente, quanta gente nel mio corso mi chiedeva cosa doveva scaricare per creare un db per fare prove, e io stesso per datalog sto facendo tutto su carta, perchè su pc non ho trovato niente di decente.

ah no io questo l'ho fatto in parallelo a un pò di pratica (progetto perditempo sfrutta studente incluso) comunque la teoria sul modello relazionale è molto utile e serve tantissimo nel caso si voglia andare in profondità nello studio delle basi di dati

[rayman2]

Se inuniversità spiegassero solo le tecnologie alla prima variazione della tecnologia la maggior parte degli studenti andrebbero in pappa. Capendo la teoria lo studente èin grado di adattarsi al dinamico mondo dell'informatica secondo me.
Tornando al datalog non l'ho mai approfondito tanto ma ho fatto una tesi su un linguaggio che ne trae ispirazione (Semantic Web Rule Language), quindi ho del materiale che potrebbe interessarti.
Ti consiglio di partire dal sito della professoressa Tanca del Politecnico di Milano, il link al blocco di slides a cui mi riferisco è questo: http://home.dei.polimi.it//tanca/Mat...gi-formali.pdf
Prova anche a dare un occhio alla pagina di wikipedia scritta da me http://it.wikipedia.org/wiki/Datalog , e alla sua versione inglese.
Ad ogni modo il datalog forse non sarà più usato ma le regole si. Le query sono sostanzialmente delle regole, i trigger pure...

[franksisca]

Originariamente inviato da rayman2

Se inuniversità spiegassero solo le tecnologie alla prima variazione della tecnologia la maggior parte degli studenti andrebbero in pappa. Capendo la teoria lo studente èin grado di adattarsi al dinamico mondo dell'informatica secondo me.
Tornando al datalog non l'ho mai approfondito tanto ma ho fatto una tesi su un linguaggio che ne trae ispirazione (Semantic Web Rule Language), quindi ho del materiale che potrebbe interessarti.
Ti consiglio di partire dal sito della professoressa Tanca del Politecnico di Milano, il link al blocco di slides a cui mi riferisco è questo: http://home.dei.polimi.it//tanca/Mat...gi-formali.pdf
Prova anche a dare un occhio alla pagina di wikipedia scritta da me http://it.wikipedia.org/wiki/Datalog , e alla sua versione inglese.
Ad ogni modo il datalog forse non sarà più usato ma le regole si. Le query sono sostanzialmente delle regole, i trigger pure...

quoto al 95% su tutta la linea, soprattutto per noi che siamo di ingegneria, ma con questa riforma si è cercato di fare più "tecnici" (sono contrario alla riforma, quindi preferirei fare 2 mesi in più di teoria ma fatti bene e meno esercizi), ma per come l'hanno presa i prof.....

[k0nt3]

Originariamente inviato da franksisca

quoto al 95% su tutta la linea, soprattutto per noi che siamo di ingegneria, ma con questa riforma si è cercato di fare più "tecnici" (sono contrario alla riforma, quindi preferirei fare 2 mesi in più di teoria ma fatti bene e meno esercizi), ma per come l'hanno presa i prof.....

mah alla fine puoi riformare quanto vuoi ma in sostanza non cambia mai niente

ps. ma per la query di prima non ti hanno dato una base di dati su cui svolgere l'esercizio? è impossibile altrimenti

[franksisca]

Originariamente inviato da k0nt3

mah alla fine puoi riformare quanto vuoi ma in sostanza non cambia mai niente

ps. ma per la query di prima non ti hanno dato una base di dati su cui svolgere l'esercizio? è impossibile altrimenti

si, è normale, ma è quella base.......solite cose, tutte le tabele con chiave come codice e dati non significativi.

[k0nt3]

Originariamente inviato da franksisca

si, è normale, ma è quella base.......solite cose, tutte le tabele con chiave come codice e dati non significativi.

ehm temo che senza tabelle con le chiavi non sia possibile trovare una soluzione al problema

[franksisca]

se trovo le posto, dovrei cercarle.......

[k0nt3]

Originariamente inviato da franksisca

se trovo le posto, dovrei cercarle.......

no perchè se le uniche informazioni disponibili sono i collegamenti tra le locazioni... bisogna pensarci un "pochino"

Qualche idea su come si potrebbe fare questa query in datalog?

Giocatore (codice, cognome, nome, città)
Partita (codice, anno, squadra_in_casa, squadra_fuori_casa, goalSqC,goalSqFC)
Contratto (giocatore,anno,squadra)
Squadra (nome,città)

Query: Per ciascun calciatore, il numero di anni e la squadra per la quale ha giocato più anni consecutivamente

[Jon_Snow]

la prima cosa da fare è leggere attentamente la query cercando di capire la struttura del problema. In questo caso vengono richiesti due parametri: numero di anni e codice squadra. Il primo è apparentemente piuttosto problematico in quanto, a differenza di SQL, non esiste in datalog in vero e proprio meccanismo di somme o contatori. Fortunatamente gli anni da calcolare sono consecutivi, di conseguenza l'inghippo può essere banalmente aggirato tramite la differenza tra l'ultimo anno ed il primo. La seconda parte della query è sostanzialmente un modo diverso di descrivere un classico problema di massimo.
Da questa analisi si evince che il cuore della query è stabilire un criterio per calcolare il numero di anni consecutivi nei quali il giocatore ha militato nella stessa squadra. Non esiste in datalog un meccanismo per "simulare" la iterazione con la ricorsione come avviene in Prolog. Non è, dunque, pensabile di iterare di anno in anno fino a trovare il cambio squadra (o la fine della carriera). Anche in questo caso serve un modo per bypassare il problema tramite qualche "trucco". Non ci sono regole fisse per fare ciò. Serve un po' di intuito ed una discreta componente di fantasia. É possibile farsi aiutare dall'uso della lingua italiana. Può sembrare assurdo detto così, ma in realtà è proprio per questa ragione che esistono linguaggi dichiarativi. Trovata una descrizione "a parole" corretta, la traduzione in Datalog è quasi immediata.

Una possibile idea è quella di stabilile se una qualunque coppia di anni rappresenta un intervallo temporale in cui il giocatore è rimasto sempre nella stessa squadra. Più formalmente si può definire una query di supporto AnniConsecutivi in cui si vuole sapere, per ogni possibile coppia di anni (I,F) con F>=I, se non esite un'ulteriore coppia di anni interni all'interno in cui il giocatore ha avuto contratti in squadre diverse.

AnniConsecutivi(G,I,F) ← Contratto(G,I,S), Contratto(G,F,S), I < F, ¬CambioSquadra(G,I,F).
CambioSquadra(G,I,F) ← Contratto(G,A1,S1), A1 >= I, A1 <= F, Contratto(G,A2,S2), A2 >= I, A2 <= F, S1 <> S2.
NumeroAnni(I,F,N) ← N = F-I+1.

Per come è costruita vengono accettati anche casi "degenere" in cui un calciatore ha giocato un solo anno in una squadra (in questo caso si avrà A1=A2=I=F) con numero anni pari ad 1 (se I=F allora N=I-I+1=1).
E' importante ricordare che ogni variabile in datalog è implicitamente quantificata in modo universale. Questo potrebbe portare a divergenze semantiche "nascoste" da un'apperente corretta logica del programma. Infatti AnniConsecutivi non è un modo per esprimere la carriera del calciatore, come sarebbe intuitivo supporre. Questo perché oltre alle coppie genera anche i sottointervalli di un intervallo consecutivo.
Se, ad esempio, un giocatore ha avuto una carriera dal 1981 fino al 1990 in cui i primi 5 anni è stato nel Milan per poi concludere nell'Inter. La query, infatti, oltre ad accettare per veri i fatti:

AnniConsecutivi(Giocatore,1981,1985).
AnniConsecutivi(Giocatore,1986,1990).

Considererà vere anche:

AnniConsecutivi(Giocatore,1981,1981).
AnniConsecutivi(Giocatore,1981,1982).
AnniConsecutivi(Giocatore,1981,1983).
AnniConsecutivi(Giocatore,1981,1984).
AnniConsecutivi(Giocatore,1981,1985).
AnniConsecutivi(Giocatore,1982,1982).
AnniConsecutivi(Giocatore,1982,1983).
...
AnniConsecutivi(Giocatore,1985,1985).
AnniConsecutivi(Giocatore,1986,1986).
AnniConsecutivi(Giocatore,1986,1987).
AnniConsecutivi(Giocatore,1986,1988).
AnniConsecutivi(Giocatore,1986,1989).
AnniConsecutivi(Giocatore,1987,1987).
AnniConsecutivi(Giocatore,1987,1988).
...
AnniConsecutivi(Giocatore,1990,1990).

Che non hanno valore semantico rispetto a ciò che ci viene richiesto. Anche in questo caso è sufficiente un piccolo accorgimento: basta considerare che un inizio di un intervallo è tale se non è vero che l'anno prima ha giocato nella stessa squadra. Utilizzando la notazione negata si può dire che che un anno I è un primo anno se è falso che non è il primo anno.

AnniConsecutivi(G,I,F) ← Contratto(G,I,S), ¬NoPrimoAnno(G,I,S), Contratto(G,F,S), I<F, ¬CambioSquadra(G,I,F).
NoPrimoAnno(G,I,S) ← Contratto(G,A,S), A = S-1.

La clausola NoPrimoAnno è necessaria per rendere Safe il programma rispetto a problemi di gestione della CWA (Closed World Assumption).
Da notare che nella query non si tiene traccia anche della squadra associata all'intervallo. Questa informazione sarebbe ridondante perché è sufficiente avere l'anno iniziale per risalire alla squadra associata.
Tornando alla query di partenza. Essendo un problema di massimo, è necessario riscriverla in forma negata. Ovvero:

Calcolare per ciascun calciatore la squadra ed il numero di anni per i quali non esiste un numero di anni consecutivi in cui ha giocato maggiore.

Dalla quale viene quasi naturale scrivere la versione in Datalog.

Q(G,N,S) ← Contratto(G,I,S), AnniConsecutivi(G,I,F), NumeroAnni(I,F,N), ¬AnniConsecutiviMaggiori(G,I,F,N).
AnniConsecutiviMaggiori(G,I,F,N) ← AnniConsecutivi(G,I,A), NumeroAnni(I,F,M), M > N.

Il motore Datalog scandirà ogni Anno associato ad ogni calciatore lo considererà come un ipotetico inizio di un intervallo di anni consecutivi.

Riassumendo:

Q(G,N,S) ← Contratto(G,I,S), AnniConsecutivi(G,I,F), NumeroAnni(I,F,N), ¬AnniConsecutiviMaggiori(G,I,F,N).
AnniConsecutiviMaggiori(G,I,F,N) ← AnniConsecutivi(G,I,A), NumeroAnni(I,F,M), M > N.
AnniConsecutivi(G,I,F) ← Contratto(G,I,S), ¬NoPrimoAnno(G,I,S), Contratto(G,F,S), I<F, ¬CambioSquadra(G,I,F).
NoPrimoAnno(G,I,S) ← Contratto(G,A,S), A = S-1.
CambioSquadra(G,I,F) ← Contratto(G,A1,S1), A1 >= I, A1 <= F, Contratto(G,A2,S2), A2 >= I, A2 <= F, S1 <> S2.
NumeroAnni(I,F,N) ← N = F-I+1.

PS: non ho provato la query su un motore quindi non assicuro l'assenza di altri piccoli errori. Ma tanto ad un esame conta l'idea ed in questo caso l'inghippo da superare erano gli anni consecutivi

[Bistick]

Questa è l'unica pagina su internet dove sono riuscito a trovare qualcosa che si avvicini agli esercizi che facciamo all'Università della Calabria, per l'esame di Basi di Dati e Conoscenza!!! Grazie

Se qualcuno ha dell'altro materiale, esempi soprattutto, che riguardano operazioni come conteggio, media etc su database, sarebbe una bellissima cosa.