Tuple relationele calculus - Tuple relational calculus

Tuple-calculus is een calculus die is gemaakt en geïntroduceerd door Edgar F. Codd als onderdeel van het relationele model , om een declaratieve database-querytaal te bieden voor datamanipulatie in dit datamodel . Het vormde de inspiratie voor de databasequerytalen QUEL en SQL , waarvan de laatste, hoewel veel minder trouw aan het oorspronkelijke relationele model en calculus, nu de de facto standaard databasequerytaal is; een dialect van SQL wordt gebruikt door bijna elk relationeel databasebeheersysteem . Michel Lacroix en Alain Pirotte voorgestelde domein calculus , die dichter bij de eerste-orde logica en met Codd bleek dat beide calculi (en relationele algebra ) gelijkwaardig zijn zeggingskracht. Vervolgens werden de zoektalen voor het relationele model relationeel compleet genoemd als ze tenminste al deze vragen konden uitdrukken.

Definitie van de calculus

Relationele database

Omdat de calculus een zoektaal is voor relationele databases, moeten we eerst een relationele database definiëren. De fundamentele relationele bouwsteen is het domein (enigszins vergelijkbaar, maar niet gelijk aan een datatype ). Een tupel is een eindige reeks attributen , die geordende paren domeinen en waarden zijn. Een relatie is een set van (compatibele) tupels. Hoewel deze relationele concepten wiskundig zijn gedefinieerd, komen deze definities losjes overeen met traditionele databaseconcepten. Een tabel is een geaccepteerde visuele weergave van een relatie; een tupel is vergelijkbaar met het concept van een rij .

We gaan eerst uit van het bestaan van een reeks C van kolomnamen, voorbeelden hiervan zijn "naam", "auteur", "adres", enzovoort. We definiëren headers als eindige deelverzamelingen van C . Een relationeel databaseschema wordt gedefinieerd als een tuple S = ( D , R , h ) waarbij D het domein is van atomaire waarden (zie relationeel model voor meer informatie over de begrippen domein en atomaire waarde ), R is een eindige reeks relatienamen , en

h : R → 2 ^C

een functie die een kop met elkaar relatienaam in associeert R . (Merk op dat dit een vereenvoudiging is van het volledige relationele model waarbij er meer dan één domein is en een koptekst niet alleen een reeks kolomnamen is, maar deze kolomnamen ook aan een domein toewijst.) Gegeven een domein D definiëren we een tuple over D als een deelfunctie dat sommige kolomnamen toegewezen aan een atomaire waarde D . Een voorbeeld zou zijn (naam: "Harry", leeftijd: 25).

t : C ⇸ D

De verzameling van alle tupels dan D wordt aangeduid als T _D . De subset van C waarvoor een tupel t is gedefinieerd, wordt het domein van t genoemd (niet te verwarren met het domein in het schema) en aangeduid als dom ( t ).

Ten slotte definiëren we een relationele database met een schema S = ( D , R , h ) als functie

db : R → 2 ^{T _D}

die de relatienamen in R afbeeldt op eindige deelverzamelingen van T _D , zodat voor elke relatienaam r in R en tuple t in db ( r ) geldt dat

dom ( t ) = h ( r ).

De laatste vereiste zegt simpelweg dat alle tupels in een relatie dezelfde kolomnamen moeten bevatten, namelijk de namen die ervoor in het schema zijn gedefinieerd.

Atomen

Voor de constructie van de formules gaan we uit van een oneindige set V van tupelvariabelen. De formules zijn gedefinieerd krijgen een databaseschema S = ( D , R , h ) en een deelfunctie Type : V ⇸ 2 ^C , aangedaan toewijzingstype dat rechtverkrijgenden headers enkele tupel variabelen. Vervolgens definiëren we de set atoomformules A [ S , type ] met de volgende regels:

als v en w in V , a in type ( v ) en b in type ( w ) dan is de formule v . a = w . b is in A [ S , type ],
als v in V , a in type ( v ) en k een waarde in D aangeeft, dan is de formule v . a = k is in A [ S , type ], en
als v in V , r in R en type ( v ) = h ( r ) dan is de formule r ( v ) in A [ S , type ].

Voorbeelden van atomen zijn:

Boek ( t ) - tuple t is aanwezig in relatie Boek.

De formele semantiek van dergelijke atomen wordt gedefinieerd gegeven een database db over S en een tuple-variabele binding val : V → T _D die tuple-variabelen toewijst aan tuples over het domein in S :

v . a = w . b is waar als en slechts als val ( v ) ( a ) = val ( w ) ( b )
v . a = k is waar als en slechts als val ( v ) ( a ) = k
r ( v ) is waar als en slechts als val ( v ) in db ( r ) is

Formules

De atomen kunnen worden gecombineerd tot formules, zoals gebruikelijk in eerste-orde logica, met de logische operatoren ∧ (en), ∨ (of) en ¬ (niet), en we kunnen de existentiële kwantor (∃) en de universele kwantor gebruiken (∀) om de variabelen te binden. We definiëren de set formules F [ S , type ] inductief met de volgende regels:

elk atoom in A [ S , type ] is ook in F [ S , type ]
als f ₁ en f ₂ in F [ S , type ] staan, dan is de formule f ₁ ∧ f ₂ ook in F [ S , type ]
als f ₁ en f ₂ in F [ S , type ] staan, dan is de formule f ₁ ∨ f ₂ ook in F [ S , type ]
als f in F [ S , type ] is, dan is de formule ¬ f ook in F [ S , type ]
als v in V , H een koptekst en f een formule in F [ S , typ _{[ v -> H ]} ] dan is de formule ∃ v : H ( f ) ook in F [ S , type ], waarbij type _{[ v - > H ]} geeft de functie aan die gelijk is aan type, behalve dat v wordt toegewezen aan H ,
als v in V , H een koptekst en f een formule in F [ S , typ _{[ v -> H ]} ] dan is de formule ∀ v : H ( f ) ook in F [ S , type ]

Voorbeelden van formules:

t .name = "CJ Date" ∨ t .name = "H. Darwen"
Boek ( t ) ∨ Tijdschrift ( t )

Merk op dat de laatste formule stelt dat alle boeken die zijn geschreven door CJ Date als onderwerp het relationele model hebben. Zoals gewoonlijk laten we haakjes weg als dit geen onduidelijkheid geeft over de semantiek van de formule.

We zullen aannemen dat de kwantoren kwantificeren over het universum van alle tupels over het domein in het schema. Dit leidt tot de volgende formele semantiek voor formules gegeven een database db over S en een tuple variabele binding val : V -> T _D :

f ₁ ∧ f ₂ is waar als en slechts als f ₁ waar is en f ₂ is waar,
f ₁ ∨ f ₂ is waar als en alleen als f ₁ waar is of f ₂ waar is of beide waar zijn,

Vragen

Ten slotte definiëren we hoe een query-expressie eruitziet gegeven een schema S = ( D , R , h ):

f ( v )}

waarbij v een tuple-variabele is, H een koptekst en f ( v ) een formule in F [ S , type ] waarbij type = {( v , H )} en met v als enige vrije variabele. Het resultaat van een dergelijke zoekopdracht voor een gegeven database db over S is de verzameling van alle tupels t over D met dom ( t ) = H zodat f waar is voor db en val = {( v , t )}.

Voorbeelden van query-expressies zijn:

Semantische en syntactische beperking van de calculus

Domeinonafhankelijke zoekopdrachten

Omdat de semantiek van de kwantoren zodanig is dat ze kwantificeren over alle tupels over het domein in het schema, kan het zijn dat een query een ander resultaat oplevert voor een bepaalde database als een ander schema wordt verondersteld. Beschouw bijvoorbeeld de twee schema's S ₁ = ( D ₁ , R , h ) en S ₂ = ( D ₂ , R , h ) met domeinen D ₁ = {1}, D ₂ = {1, 2}, relatienamen R = {"r ₁ "} en headers h = {("r ₁ ", {"a"})}. Beide schema's hebben een gemeenschappelijk exemplaar:

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

Als we de volgende vraaguitdrukking beschouwen

t .a = t .a}

dan is het resultaat op db ofwel {(a: 1)} onder S ₁ of {(a: 1), (a: 2)} onder S ₂ . Het zal ook duidelijk zijn dat als we het domein als een oneindige set beschouwen, het resultaat van de query ook oneindig zal zijn. Om deze problemen op te lossen zullen we onze aandacht beperken tot die vragen die zijn domein onafhankelijke , dat wil zeggen, de query's die hetzelfde resultaat terug te keren voor een database onder al haar schema.

Een interessante eigenschap van deze queries is dat als we aannemen dat de tuple-variabelen zich uitstrekken over tuples over het zogenaamde actieve domein van de database, dat is de subset van het domein dat voorkomt in ten minste één tuple in de database of in de query expressie, dan verandert de semantiek van de query-expressies niet. In feite is dit in veel definities van de tuple-calculus de manier waarop de semantiek van de kwantoren wordt gedefinieerd, waardoor alle queries per definitie domeinonafhankelijk zijn.

Veilige zoekopdrachten

Om de query-uitdrukkingen te beperken, zodat ze alleen domeinonafhankelijke query's uitdrukken, wordt meestal een syntactisch begrip van veilige query's geïntroduceerd. Om te bepalen of een query-expressie veilig is, zullen we twee soorten informatie uit een query afleiden. De eerste is of een variabel-kolommaar t . a is gebonden aan de kolom van een relatie of een constante, en de tweede is of twee variabele-kolomparen direct of indirect gelijk worden gesteld (aangeduid met t . v == s . w ).

Voor het afleiden van boundedness introduceren we de volgende redeneerregels:

in " v . a = w . b " is geen variabel-kolompaar gebonden,
in " v . a = k " het variabele-kolompaar v . een is gebonden,
in " r ( v )" alle paren v . a zijn gebonden aan a in type ( v ),
in " f ₁ ∧ f ₂ " zijn alle paren gebonden die ofwel in f ₁ of in f ₂ zijn gebonden ,
in " f ₁ ∨ f ₂ " zijn alle paren gebonden die zowel in f ₁ als in f ₂ gebonden zijn ,
in "¬ f " zijn geen paren gebonden,
in "∃ v : H ( f )" een paar w . a is gebonden als het gebonden is in f en w <> v , en
in "∀ v : H ( f )" een paar w . a is gebonden als het gebonden is in f en w <> v .

Voor het afleiden van gelijkwaardigheid introduceren we de volgende redeneerregels (naast de gebruikelijke redeneerregels voor equivalentierelaties: reflexiviteit, symmetrie en transitiviteit):

in " v . a = w . b " geldt dat v . een == w . b ,
in " v . a = k " worden geen paren gelijkgesteld,
in " r ( v )" worden geen paren gelijkgesteld,
in " f ₁ ∧ f ₂ " geldt dat v . een == w . b als het geldt in f ₁ of in f ₂ ,
in " f ₁ ∨ f ₂ " geldt dat v . een == w . b als het zowel in f ₁ als in f _{2 geldt} ,
in "¬ f " worden geen paren gelijkgesteld,
in "∃ v : H ( f )" geldt dat w . een == x . b als het geldt in f en w <> v en x <> v , en
in "∀ v : H ( f )" geldt dat w . een == x . b als het geldt in f en w <> v en x <> v .

We zeggen dan dat een query-expressie {v: H | f (v)} is veilig als

voor elke kolomnaam a in H kunnen we afleiden dat v . a wordt gelijkgesteld met een gebonden paar in f ,
voor elke onderuitdrukking van f van de vorm "∀ w : G ( g )" kunnen we afleiden dat we voor elke kolomnaam a in G kunnen afleiden dat w . a wordt gelijkgesteld aan een gebonden paar in g , en
voor elke onderuitdrukking van f van de vorm "∃ w : G ( g )" kunnen we afleiden dat we voor elke kolomnaam a in G kunnen afleiden dat w . a wordt gelijkgesteld met een gebonden paar in g .

De beperking tot expressies voor veilige query's beperkt de expressiviteit niet, aangezien alle domeinonafhankelijke query's die kunnen worden uitgedrukt, ook kunnen worden uitgedrukt door een expressie voor veilige query's. Dit kan worden bewezen door aan te tonen dat voor een schema S = ( D , R , h ), een gegeven set K constanten in de query-expressie, een tuple-variabele v en een header H we een veilige formule kunnen construeren voor elk paar v . a met een in H die aangeeft dat de waarde ervan in het actieve domein ligt. Stel bijvoorbeeld dat K = {1,2}, R = {"r"} en h = {("r", {"a," b "})} dan is de overeenkomstige veilige formule voor v .b:

v .b = 1 ∨ v .b = 2 ∨ ∃ w (r (w) ∧ ( v .b = w .a ∨ v .b = w .b))

Deze formule kan vervolgens worden gebruikt om elke onveilige query-expressie te herschrijven naar een equivalente veilige query-expressie door een dergelijke formule toe te voegen voor elke variabele v en kolomnaam a in het type waarin deze in de expressie wordt gebruikt. In feite betekent dit dat we alle variabelen over het actieve domein laten reiken, wat, zoals al werd uitgelegd, de semantiek niet verandert als de uitgedrukte vraag domeinonafhankelijk is.

Systemen

Zie ook

Referenties

Edgar F. Codd : een relationeel gegevensmodel voor grote gedeelde databanken . Communications of the ACM , 13 (6): 377-387, 1970.

Languages

In other projects