Càlcul relacional basat en tuplas

El càlcul relacional basat en tuplas és un càlcul introduït per Edgar Frank Codd com a part del càlcul relacional, el qual pertany al model relacional per a bases de senyes. Va ser l'inspiració per a la creació dels llenguages de consulta QUEL i SQL, dels quals este últim, encara que menys fidel a l'original, és ara el llenguage de consulta més usat. El càlcul relacional basat en domini, formulat per Michel Lacroix and Alain Pirotte, s'aproxima més a la llògica de primer orde, no obstant abdós són equivalents en el seu poder expressiu.

Definició

Base de senyes relacional

Degut a que és un llenguage de consulta per a bases de senyes relacionals, primer es deu definir una base de senyes relacional. El bloc de construcció relacional bàsic és el domini o tipo de senyes. Una tupla o registre és un multiconjunto d'atributs, els quals són parells ordenats de domini i valor, o només una fila. Una relació és un conjunt de tuplas. Una taula és una representació visual acceptada d'una relació.

S'assumix l'existència d'un conjunt C de columnes, per eixemple, "nom", "autor" o "direcció"; i de capçaleres com a subconjunts finitos de C. Un esquema de bases de senyes relacional és definit com una tupla S = (D, R, h), a on:

• D és el domini dels valors atòmics (un atribut és atòmic si els elements del domini són simples i indivisibles).
• R és un conjunt finito de noms de relació.
• h és una funció que associa una capçalera en cada nom de relació en R i es definix com: h: R → 2^C

Donat un domini D es definix una tupla sobre D com una funció parcial que mapea alguns noms de columna a un valor atòmic en D; per eixemple, name: "Harry", age : 25.

t : C → D

El conjunt de totes les tuplas sobre D es denota com a T_D. El subconjunt de C per al qual es definix una tupla t es coneix com el domini de t (que no deu confondre's en el domini en l'esquema) i és escrit com dom(t).

Llavors es pot definir una base de senyes relacional donat un esquema S = (D, R, h) com una funció:

db : R → 2^T_D

que mapea els noms de relació en R a subconjunts finitos de T_D, tals que per cada nom de relació r en R i tupla t en db(r) es complix que:

dom(t) = h(r).

És dir, que totes les tuplas d'una relació deuen contindre els mateixos noms de columna que es definixen per a l'esquema.

Àtoms

Per a la construcció de les fòrmules s'assumix un conjunt infinit V de variables de tupla. Les fòrmules es definixen donat un esquema de bases de senyes S = (D, R, h) i una funció parcial tipo : V -> 2^C que definix una assignació de tipo que assigna capçaleres a algunes variables de tupla. Llavors es definixen el conjunt de fòrmules atòmiques A[S,tipo] en les següents regles:

1. Si v i w estan en V, a en tipo(v) i b en tipo(w) llavors la fòrmula "v.a = w.b" està en A[S,tipo].
2. Si v està en V, a en tipo(v) i k denota un valor en D llavors la fòrmula "v.a = k" està en A[S,tipo].
3. Si v està en V, r en R i tipo(v) = h(r) llavors la fòrmula "r(v)" està en A[S,tipo].

Eixemples d'àtoms són:

• (t.edat = s.edat) — la tupla t té un atribut d'edat i s té un atribut d'edat en el mateix valor
• (t.nom = "Codd") — la tupla t té un atribut de nom i el seu valor és "Codd"
• Llibre(t) — la tupla t es troba en la relació Lliure.

La semàntica formal d'aquells àtoms és definida donada una base de senyes db sobre S i una variable de tupla val : V -> T_D que mapea les variables de tupla a tuplas sobre el domini en S:

1. "v.a = w.b" és verdader si i només si val(v)(a) = val(w)(b)

1. "v.a = k" és verdader si i només si val(v)(a) = k
2. "r(v)" és verdader si i només si val(v) is in db(r)

Fòrmules

Els àtoms poden ser combinats en fòrmules, com és comuna en la llògica de primer orde, en els operadors llògics ∧ (and o i), ∨ (or o o) i ¬ (not o no), i pot usar-se el quantificador existencial (∃) i el quantificador universal (∀) per a enllaçar o unir les variables. Es definix el conjunt de fòrmules F[S,tipo] per inducció en les següents regles:

1. Cada àtom en A[S,tipo] està també en F[S,tipo].
2. Si f₁ i f₂ estan en F[S,tipo] llavors la fòrmula "f₁ ∧ f₂" està també en F[S,tipo].
3. Si f₁ i f₂ està en F[S,tipo] llavors la fòrmula "f₁ ∨ f₂" està també en F[S,tipo].
4. Si f està en F[S,tipo] llavors la fòrmula "¬ f" està també en F[S,tipo].
5. Si v està en V, una capçalera H i una fòrmula f en F[S,tipo_[v->H]] llavors la fòrmula "∃ v: H (f)" està també en F[S,tipo], a on tipo_[v->H] denota la funció que és igual a tipo excepto que esta mapea v a H.
6. Si v està en V, una capçalera H i una fòrmula f en F[S,tipo_[v->H]] llavors la fòrmula "∀ v: H (f)" està també en F[S,tipo].

Eixemples de fòrmules són:

• t.autor = "René Descartes" ∨ t.autor = "Óscar Gómez"
• Llibre(t) ∨ Revista(t)
• ∀ t : {autor, títul, matèria} ( ¬ ( Llibre(t) ∧ t.autor = "René Descartes" ∧ ¬ ( t.matèria = "revolució científica")))

Assumim que els quantificadors s'apliquen sobre l'univers de totes les tuplas sobre el domini en l'esquema. Açò du a la formulació de les següents semàntiques per a fòrmules donada una base de senyes db sobreS i una variable de tupla val: V -> T_D:

1. "f₁ ∧ f₂" és verdader si i solament si "f₁" és verdader i "f₂" és verdader.
2. "f₁ ∨ f₂" és verdader si i solament si "f₁" és verdader o "f₂" és verdader o abdós són verdaders.
3. "¬ f" és verdader si i solament si "f" és fals.
4. "∃ v : H ( f )" és verdader si i solament si hi ha una tupla t sobre D tal que dom(t) = H i la fòrmula "f" és verdadera per a val_[v->t].
5. "∀ v : H ( f )" és verdader si i solament si para totes les tuplas t sobre D tals que dom(t) = H la fòrmula "f" és verdadera per a val_[v->t].

Consultes

Donat un esquema S = (D, R, h), s'expressa una consulta com:

{ v : H | f(v) }

A on v és una variable de tupla, H és una capçalera i f(v) una fòrmula en F[S,tipo] a on tipo = { (v, H) } i en v com la seua única variable lliure. El resultat d'una consulta com estes per a una base de senyes db sobre S és el conjunt de totes les tuplas t sobre D en dom(t) = H tals que f és verdader per a db i val = { (v, t) }.

Eixemples de consultes són:

• { t : {nomene} | ∃ s : {nom, salari} ( Empleat(s) ∧ s.salari = 500.000 ∧ t.nomene = s.nom ) }
• { t : {proveïdor, artícul} | ∃ s : {s#, snombre} ( Proveïdor(s) ∧ s.snombre = t.proveïdor ∧ ∃ p : {p#, pnombre} ( Producte(p) ∧ p.pnombre = t.artícul ∧ ∃ a : {s#, p#} ( Suministraments(a) ∧ s.s# = a.s# ∧ a.p# = p.p# ) }

Semàntica i restricció sintàctica

Consultes independent del domini

Degut a que la semàntica dels quantificadors és tal que ells quantifiquen sobre totes les tuplas en el domini de l'esquema, pot ser que una consulta retorne un resultat diferent per a una base de senyes específica si es presumix un atre esquema. Per eixemple, considerant els dos esquemes S₁ = ( D₁, R, h ) i S₂ = ( D₂, R, h ) en dominis D₁ = { 1 }, D₂ = { 1, 2 }, noms de relació R = { "r₁" } i capçaleres h = { ("r₁", {"a"}) }. Abdós esquemes tenen una instància comuna:

db = { ( "r₁", { ("a", 1) } ) }

Si considerem la següent consulta:

{ t : {a} | t.a = t.a }

Llavors el seu resultat en db o és { (a : 1) } baix S₁ o { (a : 1), (a : 2) } baix S₂. És clar també que si prenem el domini com un conjunt infinit, llavors el resultat de la consulta serà infinit. Per a resoldre eixos problemes es consideren les consultes independent del domini, aquelles que retornen el mateix resultat per a una base de senyes baix tots els seus esquemes.

Consultes segures

En la finalitat de llimitar les consultes de manera que expressen únicament consultes independent del domini, una noció sintàctica de consulta segura és introduïda. Per a determinar si una consulta és segura is safe es deriven dos tipos d'informació d'una consulta. La primera és si un parell columna-variablet.a està acotat a la columna d'una relació o una constant, i la segona és si hi ha dos pares columna-variable que són directa o indirectament equivalents (denotat t.v == s.w).

Per derivar el acotamiento s'introduïxen les següents regles:

1. en "v.a = w.b" cap parell columna-variable està acotat,
2. en "v.a = k" el parell columna-variable v.a està acotat,
3. en "r(v)" tots els pares v.a estan acotats per a en tipo(v),
4. en "f₁ ∧ f₂" tots els parells estan acotats de manera que estan acotats o en f₁ o en f₂,
5. en "f₁ ∨ f₂" tots els parells estan acotats de manera que estan acotats abdós en f₁ i en f₂,
6. en "¬ f" cap dels parells està acotat,
7. en "∃ v: H (f)" un parell w.a està acotat si està acotat en f i w <> v,
8. en "∀ v: H (f)" un parell w.a està acotat si està acotat en f i w <> v.

Per derivar l'equivalència s'introduïxen les següents regles:

1. en "v.a = w.b" es manté que v.a == w.b,
2. en "v.a = k" cap dels parells són equivalents,
3. en "r(v)" cap dels parells són equivalents,
4. en "f₁ ∧ f₂" es manté que v.a == w.b si es manté o en f₁ o en f₂,
5. en "f₁ ∨ f₂" es manté que v.a == w.b si es manté en f₁ i en f₂,
6. en "¬ f" cap dels parells són equivalents,
7. en "∃ v : H ( f )" es manté que w.a == x.b si es manté en f i w<>v i x<>v,
8. en "∀ v : H ( f )" es manté que w.a == x.b si es manté en f i w<>v i x<>v.

Llavors es diu que una consulta { v : H | f(v) } és segura si:

• per a cada nom de columna a en H podem derivar que v.a és equivalent a un parell acotat en f,
• per a cada subexpresión de f de la forma "∀ w : G (g)" podem derivar que per a cada nom de columna a en G podem derivar que w.a és equivalent a un parell acotat en g,
• per a cada subexpresión de f de la forma "∃ w : G (g)" podem derivar que per a cada nom de columna a en G podem derivar que w.a és equivalent a un parell acotat en g.

Sistemes

• DES – Una ferramenta educativa en càlcul relacional de tuplas i atres llenguages formals

• WinRDBI - Una ferramenta educativa en càlcul relacional de tuplas i atres llenguages formals

Bibliografia

• Edgar Frank Codd: A Relational Model of Data for Large Shared Data Banks. Communications of the ACM, 13(6):377–387, 1970.