Complementi di basi di datiProgetti ModelGen - MIDST

P. Atzeni, P. Cappellari, G. Gianforme

15 marzo 2007

P. Atzeni 15 marzo 2007 2

Datalog

• Un linguaggio di programmazione logica per basi di dati derivato dal Prolog

• Utilizza predicati di due tipi:– estensionali: relazioni della base di dati– intensionali: corrispondono alle viste

• Il linguaggio è basato su regole utilizzate per "definire" i predicati estensionali

P. Atzeni 15 marzo 2007 3

Datalog in ModelGen-MIDST

• In ModelGen-MIDST usiamo Datalog per materializzare i risultati delle traduzioni:– le regole generano i costrutti tradotti– La distinzione fra predicati intensionali e estensionali è

leggermente diversa dal normale• Utilizziamo un’estensione importante: generazione di OID con

funzioni di Skolem

P. Atzeni 15 marzo 2007 4

Datalog, sintassi

• Regole:testa corpo

– testa è un predicato atomico (intensionale)– corpo è una lista (congiunzione) di predicati atomici

• Le interrogazioni sono specificate per mezzo di predicati atomici (convenzionalmente preceduti da "?")

• Vediamo ora anche le interrogazioni, anche se per i progetti ci interessano poco (ci interessa definire dati derivati)

P. Atzeni 15 marzo 2007 5

Esempi

Impiegati Nome Età StipendioMatricola

Bianchi 37 385998Rossi 34 457309

Bruni 43 425698Neri 42 359553

Mori 45 504076Lupi 46 608123

Supervisione Impiegato Capo

59987309

56989553

4076

56985698

40764076

8123

P. Atzeni 15 marzo 2007 6

Esempio -1

• Trovare matricola, nome, età e stipendio degli impiegati che hanno 30 anni

SELEtà=30(Impiegati)

{ Matricola: m, Nome: n, Età: e, Stipendio: s | Impiegati(Matricola: m, Nome: n, Età: e, Stipendio: s) s = 30 }

? Impiegati(Matricola: m, Nome: n, Età: 30, Stipendio: s)

P. Atzeni 15 marzo 2007 7

Esempio 0a

• Trovare matricola, nome, età e stipendio degli impiegati che guadagnano più di 40

SELStipendio>40(Impiegati)

{ Matricola: m, Nome: n, Età: e, Stipendio: s | Impiegati(Matricola: m, Nome: n, Età: e, Stipendio: s) s > 40 }

• Serve un predicato intensionale

ImpRicchi(Matricola: m, Nome: n, Età: e, Stipendio: s) Impiegati(Matricola: m, Nome: n, Età: e, Stipendio: s) , s >40

? ImpRicchi(Matricola: m, Nome: n, Età: e, Stipendio: s)

P. Atzeni 15 marzo 2007 8

Esempio 0b

• Trovare matricola, nome ed età di tutti gli impiegati

PROJMatricola, Nome, Età(Impiegati)

{ Matricola: m, Nome: n, Età: e | Impiegati(Matricola: m, Nome: n, Età: e, Stipendio: s)}

InfoPubbliche(Matricola: m, Nome: n, Età: e) Impiegati(Matricola: m, Nome: n, Età: e, Stipendio: s)

? InfoPubbliche(Matricola: m, Nome: n, Età: e)

P. Atzeni 15 marzo 2007 9

Esempio 2

• Trovare le matricole dei capi degli impiegati che guadagnano più di 40

PROJCapo (Supervisione JOIN Impiegato=Matricola (SELStipendio>40(Impiegati)))

{ Capo: c | Supervisione(Capo:c,Impiegato:m) Impiegati(Matricola: m, Nome: n, Età: e, Stipendio: s) s > 40 }

CapiDeiRicchi (Capo:c) ImpRicchi(Matricola: m, Nome: n, Età: e, Stipendio: s),

Supervisione (Capo:c,Impiegato:m)

? CapiDeiRicchi (Capo:c)

P. Atzeni 15 marzo 2007 10

Esempio 5

• Trovare matricola e nome dei capi i cui impiegati guadagnano tutti più di 40

PROJCapo (Supervisione) - PROJCapo (Supervisione JOIN Impiegato=Matricola (SELStipendio 40(Impiegati)))

• serve la negazioneCapiDiNonRicchi (Capo:c) Supervisione (Capo:c,Impiegato:m),

Impiegati (Matricola: m, Nome: n, Età: e, Stipendio: s) , s 40

CapiSoloDiRicchi (Matricola: c, Nome: n) Impiegati (Matricola: c, Nome: n, Età: e, Stipendio: s) ,

Supervisione (Capo:c,Impiegato:m), not CapiDiNonRicchi (Capo:c)

? CapiSoloDiRicchi (Matricola: c, Nome: n)

P. Atzeni 15 marzo 2007 11

Esempio 6

• Per ogni impiegato, trovare tutti i superiori.

• Serve la ricorsione

Superiore (Impiegato: i, SuperCapo: c) Supervisione (Impiegato: i, Capo: c)

Superiore (Impiegato: i, SuperCapo: c) Supervisione (Impiegato: i, Capo: c'),Superiore (Impiegato: c', SuperCapo: c)

P. Atzeni 15 marzo 2007 12

Datalog, semantica

• La definizione della semantica delle regole ricorsive è delicata (in particolare con la negazione)

• Potere espressivo:– Datalog non ricorsivo senza negazione è equivalente al

calcolo senza negazione e senza quantificatore universale– Datalog non ricorsivo con negazione è equivalente al calcolo

e all'algebra– Datalog ricorsivo senza negazione e calcolo sono

incomparabili– Datalog ricorsivo con negazione è più espressivo di calcolo

e algebra

P. Atzeni 15 marzo 2007 13

Datalog with OID invention

• Datalog (informally):– a logic programming language with no function symbols and

predicates that correspond to relations in a database– we use a non-positional notation

• Datalog with OID invention:– an extension of Datalog that uses Skolem functions to

generate new identifiers when needed• Skolem functions:

– injective functions that generate "new" values (value that do not appear anywhere else); so different Skolem functions have disjoint ranges

P. Atzeni 15 marzo 2007 14

Esercizio

• Traduzione da ER a relazionale, completando quanto accennato nei lucidi seguenti

• Per questa volta ancora sulla carta, per ragionare sui concetti

P. Atzeni 15 marzo 2007 15

A basic translation

• From (a simple) binary ER model to the relational model– a table for each entity– a column (in the table for E) for each attribute of an entity E– for each M:N relationship

• a table for the relationship• columns …

– for each 1:N and 1:1 relationship:• a column for each attribute of the identifier …

P. Atzeni 15 marzo 2007 16

A basic translation application

Departments

Name Address

EmployeesEmpNo

Name

Affiliation

Departments

1,1

0,N

Name

Address

Employees

EmpNo Name Affiliation

P. Atzeni 15 marzo 2007 17

A basic translation (in supermodel terms)

• From (a simple) binary ER model to the relational model– an aggregation of lexicals for each abstract– a component of the aggregation for each attribute of abstract– for each M:N aggregation of abstracts …

• …

• From (a simple) binary ER model to the relational model– a table for each entity– a column (in the table for E) for each attribute of an entity E– for each M:N relationship

• a table for the relationship• columns …

– for each 1:N and 1:1 relationship:• a column for each attribute of the identifier …

P. Atzeni 15 marzo 2007 18

Schemas in our dictionary

SM-AbstractOID Schema Name301 1 Employees

302 1 Departments

201 3 Clerks

202 3 Offices

SM-AttributeOfAbstractOID Schema Name isIdent isNullable Type AbstrOID401 1 EmpNo T F Int 301

402 1 Name F F Text 301

404 1 Name T F Char 302

405 1 Address F F Text 302

501 3 Code T F Int 201

… … … … … … …

Employees

Departments

EmpNo

Name

Name

Address

P. Atzeni 15 marzo 2007 19

"An aggregation of lexicals for each abstract"

SM_AggregationOfLexicals(OID: #aggregationOID_1(OID), Name: n)

SM_Abstract (

OID: OID, Name: n ) ;

• the value for the attribute Name is copied (by using variable n)

• the value for OID is "invented": a new value for the function #aggregationOID_1(OID) for each different value of OID, so a different value for each value of SM_Abstract.OID

• the materialization of the Skolem function describes the mapping

P. Atzeni 15 marzo 2007 20

"A component of the aggregation for each attribute of abstract"

SM_ComponentOfAggregation… ( OID: #componentOID_1(attOID),Name: name, AggrOID: #aggregationOID_1(absOID),IsNullable: isNullable, IsKey: isIdent, Type : type )

←SM_AttributeOfAbstract(

OID: attOID,Name: name,AbstractOID: absOID, IsIdent: isIdent, IsNullable: isNullable , Type : type ) ;

• Skolem functions– are functions– are injective– have disjoint ranges

• the first function "generates" a new value

• the second "reuses" the value generated by the first rule

P. Atzeni 15 marzo 2007 21

"An aggregation of lexicals for each abstract"

SM_AggregationOfLexicals(OID: #aggregationOID_1(OID), Name: name)

SM_Abstract (

OID: OID, Name: name ) ;

P. Atzeni 15 marzo 2007 22

"An aggregation of lexicals for each abstract"

SM_AggregationOfLexicals(OID: #aggregationOID_1(OID), Name: n)

SM_Abstract (

OID: OID, Name: n ) ;

• the value for the attribute Name is copied (by using variable n)

• the value for OID is "invented": a new value for the function #aggregationOID_1(OID) for each different value of OID, so a different value for each value of SM_Abstract.OID

P. Atzeni 15 marzo 2007 23

"An aggregation of lexicals for each abstract"

SM-AbstractOID Schema Name301 1 Employees

302 1 Departments

… … …

SM-AttributeOfAbstractOID Schema Name isIdent isNullable Type AbstrOID401 1 EmpNo T F Int 301

402 1 Name F F Text 301

… … … … … … …

EmployeesEmpNoName

11

11

Departments1002

Employees1001

SM_AggregationOfLexicals(OID: #aggregationOID_1(OID), Name: n)

SM_Abstract (

OID: OID, Name: n ) ;

…

3021002

……

1001

SM-AggregationOfLexicalsSchema NameOID

SM-aggregationOID_1_SKabsOIDOID

301

Employees

P. Atzeni 15 marzo 2007 24

"A component of the aggregation for each attribute of abstract"

SM_ComponentOfAggregation… ( OID: #componentOID_1(attOID),Name: name, AggrOID: #aggregationOID_1(absOID),IsNullable: isNullable, IsKey: isIdent, Type : type )

←SM_AttributeOfAbstract(

OID: attOID,Name: name,AbstractOID: absOID, IsIdent: isIdent, IsNullable: isNullable , Type : type ) ;

• Skolem functions– are functions– are injective– have disjoint ranges

• the first function "generates" a new value

• the second "reuses" the value generated by the first rule

P. Atzeni 15 marzo 2007 25

A component of the aggregation for each attribute of abstract"

SM-AbstractOID Schema Name301 1 Employees

302 1 Departments

… … …

EmployeesEmpNoName

11

11

Departments1002

Employees1001

…

3021002

……

1001

SM-AggregationOfLexicalsSchema NameOID

SM-aggregationOID_1_SKabsOIDOID

301

SM_ComponentOfAggregation… ( OID: #componentOID_1(attOID),Name: name, AggrOID: #aggregationOID_1(absOID),IsNullable: isNullable, IsKey: isIdent, Type : type )

←SM_AttributeOfAbstract(

OID: attOID,Name: name,AbstractOID: absOID, IsIdent: isIdent, IsNullable: isNullable , Type : type ) ;

SM-componentOID_1_SKabsOIDOID

Employees

EmpNo Name

SM-AttributeOfAbstractOID Schema Name isIdent isNullable Type AbstrOID401 1 EmpNo T F Int 301

402 1 Name F F Text 301

… … … … … … …

SM-ComponentOfAggregationOfLexicalsSchema Type AggrOIDisNullableisIdentNameOID

Text 1001FFName111004

1001IntFTEmpNo11

1003 401

1004 402

1003