HOOFDSTUK IV Toepassingen in Informatica

HOOFDSTUK IV Toepassingen in Informatica §1. DATABANKEN BEVRAGEN Deze slides zijn grotendeels een vertaling uit het Engels van cursusmateriaal van Levesque en Reiter.

Relationele databanken • Een relationele databank is een systeem om informatie op te slaan en op te vragen. Dit is meest gebruikte methode hiervoor, bv: SQL, Access. • De informatie wordt opgeslagen in tabellen. Een tabel is eigenlijk een relatie, inderdaad: – Een rij in een tabel met 2 kolommen is een koppel. – De verzameling van die koppels is een relatie op D, waarbij: – D = de verzameling van al de items in de rijen van de tabellen.

• Deze relaties vormen een structuur D met universum D, en met constanten al de verschillende items.

Voorbeeld: StudentenDatabank Namen van de verschillende tabellen (relaties): • • • • •

Instructor: … is docent voor … Enrolled: … is ingeschreven voor … Prerequ: … is (directe) nodige voorkennis voor … Grade: … behaalde voor … (ooit) de score … PassingGrade: … is een slaag-score

We laten toe dat een student meer dan één score heeft voor een zelfde vak.

Instructor Ray Hec Sue Sue Pat

CS230 CS230 M100 M200 CS238

Prerequ CS148

CS230

CS230

CS238

M100

M200

Enrolled Jill Jack Sam Bill May Ann Tom Ann Jill Sam Flo

CS230 CS230 CS230 CS230 CS238 CS238 M100 M100 M200 M200 M200

Grade Sam Bill Jill Jack Flo May Bill Ann Jill Sam Flo Flo

CS148 CS148 CS148 CS148 CS230 CS230 CS230 CS230 M100 M100 M100 M100

AAA D A C AA AA F C B AA D B

PassingGrade AAA AA A B C

Ter herinnering: Instructor(docent, vak) Enrolled(student, vak) Prerequ( voorkennis, opvolgvak) Grade(student, vak, score) PassingGrade(score)

Queries met antwoord ja of nee • Behaalde Sam (ooit) een AAA in CS148 ? Yes Grade(Sam, CS148, AAA) • Is Sue docent van zowel M100 als M200 ? Yes Instructor(Sue, M100) ∧ Instructor(Sue, M200) • Is precies één van CS148 of M100 (directe) nodige voorkennis voor CS230 ? Yes {Prerequ(CS148,CS230)∨Prerequ(M100,CS230)} ∧ ¬{Prerequ(CS148,CS230)∧Prerequ(M100,CS230)}

Alternatief:

{Prerequ(CS148,CS230)∧¬Prerequ(M100,CS230)} ∨ {¬Prerequ(CS148,CS230)∧Prerequ(M100,CS230)}

Queries, vervolg (1) • Vereist CS238 nodige voorkennis? Yes (∃x)Prerequ(x,CS238) • Is May geslaagd voor CS230 ? Yes (∃x){ Grade(May,CS230,x) ∧ PassingGrade(x) } • Heeft Ray minstens één student? Yes (∃x){ Instructor(Ray, x) ∧ (∃y)Enrolled(y,x) } Instructor(docent, vak)

Enrolled(student, vak)

Prerequ( voorkennisvak, opvolgvak) Grade(student, vak, score) PassingGrade(score)

Queries, vervolg (2) • Heeft Flo al een examen van een vak afgelegd? Yes (∃x)(∃y)Grade(Flo,x,y) • Doceert Ray al de vakken die (‘directe’) nodige voorkennis zijn voor CS238 ? Yes. (∀x){ Prerequ(x,CS238) → Instructor(Ray,x) } • Is er iemand die ingeschreven is voor CS230 en die steeds geslaagd is voor alle vakken die hij/zij tot hiertoe aflegde? Yes (∃x){ Enrolled(x,CS230) ∧ (∀y)(∀z)[Grade(x,y,z) → PassingGrade(z)] } Instructor(docent, vak)



Queries, vervolg (3) • Is iedereen die ingeschreven is voor CS230, geslaagd voor minstens één vak gedoceerd door Sue? No! (∀x){ Enrolled(x,CS230) → (∃w)[ Instructor(Sue,w) ∧ (∃s)(Grade(x,w,s) ∧ PassingGrade(s)) ] } • Heeft John examen voor CS230 afgelegd? No! (∃s)Grade(John,CS230,s) Instructor(docent, vak)



Queries, vervolg (4) • Zijn er studenten die bij elke docent les volgen? No! (∃x)(∀y){ (∃w)Instructor(y,w) → (∃u)[ Instructor(y,u) ∧ Enrolled(x,u) ] } • Is er een student die precies één vak volgt? Yes (∃x)(∃w){Enrolled(x,w) ∧ (∀u)[Enrolled(x,u) → u = w]} Instructor(docent, vak)



Queries met antwoord een tabel • Gevraagd: alle koppels (x,y) zodat student x geslaagd is voor vak y. Query: (∃z){Grade(x,y,z) ∧ PassingGrade(z)} Deze query heeft vrije variabelen x en y.

• Gevraagd: alle studenten x die precies één vak volgen. Query: (∃w){Enrolled(x,w)∧(∀u)[Enrolled(x,u) → u = w]} Deze query heeft vrije variabele x.

Correctheid Een predikatenlogica-formulering van een query (geformuleerd in het Nederlands) is correct indien de predicatenlogica-formule dezelfde betekenis heeft als de Nederlandse zin, voor eender welke ‘zinvolle’ waarden in de rijen en kolommen van de tabellen van de databank. Disclaimer: De definitie is eerder vaag, maar voldoende voor ons gebruik.

Specificaties en constraints • Ontwerp van informatiesystemen vergt formulering van preciese specificaties, waaraan de programmeurs zich dienen te houden. • Voor databanken bestaat een deel van die specificaties meestal uit integrity constraints. • Integrity constraints zijn voorwaarden waaraan de data in de databank steeds moeten voldoen. Anders kan de software die de databank manipuleert verkeerd werken. • Daar Engels en Nederlands soms niet erg precies (of dubbelzinnig) zijn is het beter de constraints in een formele taal te formuleren (bijvoorbeeld predikatenlogica-taal!).

Constraints, voorbeelden (1) • Geen enkel vak is (directe) nodige voorkennis voor zichzelf. ¬(∃w)Prerequ(w,w) • Niemand kan meer dan één score hebben voor éénzelfde vak.

Opgepast: die constraint is niet voldaan voor onze StudentenDatabank.

¬(∃x)(∃w)(∃s)(∃t){Grade(x,w,s) ∧ Grade(x,w,t) ∧ s ≠ t}

Instructor(docent, vak)



Constraints, voorbeelden (2) • Geen enkele (huidige) student kan een docent zijn. ¬(∃x){(∃w)Instructor(x,w) ∧ (∃w)Enrolled(x,w)} • Iedereen die ingeschreven is voor een vak moet geslaagd zijn voor alle vakken die (directe) nodige voorkennis zijn voor dat vak. (∀x)(∀w){Enrolled(x,w) → (∀t)[Prerequ(t,w) → (∃s)(Grade(x,t,s) ∧ PassingGrade(s))]} Instructor(docent, vak)



Test jezelf!!! Los al de vorige voorbeelden zelf op: • Schrijf jouw oplossing met LogicPalet. Hint: Vul de tekstvakken S met de gebruikte relatiesymbolen: bijvoorbeeld: Enrolled(*,*) Grade(*,*,*). • Vergelijk jouw oplossing met die van de docent, via AskSpass. Die oplossingen moeten logisch equivalent zijn (tenzij je het te ver gezocht hebt) • Je kan de oplossingen in het huidige document met copy-paste overbrengen naar LogicPalet. (Slechts deels met Linux. Dan is het beter het bestand Toepassingen.utxt te importeren.)

• Voor AskSpass moet je de declaraties toevoegen die op de volgende slide staan:

Declaraties voor AskSpass voor StudentenDatabank • Toevoegen aan declaraties van de relatie-identifiers: ,(Instructor,2),(Enrolled,2),(Prerequ,2),(Grade,3),(PassingGrade,1)

• Toevoegen aan declaraties van functies en constanten:

,(Ray,0),(Hec,0),(Sue,0),(Pat,0),(Jill,0),(Jack,0),(Sam,0),(Bill,0),(May,0),(Ann,0),(Tom,0) ,(Flo,0),(CS148,0),(CS230,0),(CS238,0),(M100,0),(M200,0),(AAA,0),(AA,0),(A,0),(B,0), (C,0),(John,0)

• Voeg dit toe achter de gebruikelijke declaraties voor Tarski en de oefeningenzittingen. Opgepast: de letters a,b,c,…,q zijn voorbehouden voor constanten!!!

Disclaimer Twee correcte predikatenlogica-formuleringen van een zelfde query (geformuleerd in het Nederlands) hoeven niet noodzakelijk logisch equivalent te zijn. Maar de queries in de opgaven zijn zodanig opgesteld dat dit wel het geval is, tenzij jouw formulering te ver gezocht is. Voorbeeld: Behaalden Sam en Jill (ooit) een AAA in CS148 ? Grade(Sam, CS148, AAA) ∧ Grade(Jill, CS148, AAA) Grade(Sam, CS148, AAA) ∧ Grade(Jill, CS148, AAA) ∧ Sam ≠ Jill

Oefeningen Formuleer volgende queries of constraints in predikatenlogica: 1. 2. 3. 4. 5. 6. 7.

Zijn alle studenten die ingeschreven zijn voor CS230 geslaagd voor dat vak? (Opgepast: student kan meerdere scores voor een vak hebben!) Is er een student die ingeschreven is voor alle vakken die Sue doceert? Is er een student die ingeschreven is voor meer dan twee vakken? Zijn Ray en Hec docenten voor CS230 en tevens de enigen hiervoor? Is er een student die (uiteindelijk) geslaagd is voor alle door hem afgelegde vakken? (Opgepast: een student kan meerdere scores voor een vak hebben!) Constraint: Niemand mag ingeschreven zijn voor een vak waarvoor hij/zij al geslaagd is. Constraint: Iedereen die ingeschreven is voor een vak moet geslaagd zijn voor alle vakken die (directe) nodige voorkennis zijn voor dat vak.

Toepassingen in Informatica §2. Formele Methoden in Software Engineering Deze slides zijn voor een groot deel gebaseerd op Engelstalig cursusmateriaal van Levesque en Reiter.

Informatiesystemen specificiëren • Meestal werken meerdere groepen mensen aan een groot software systeem. Elke groep werkt aan een onderdeel (component, klasse). • Duidelijke en precieze communicatie tussen die groepen is essentiëel. • Engelse taal is soms niet precies genoeg. Code is te gedetailleerd. Ondubbelzinnige specificatie van wat elke component doet is noodzakelijk. Oplossing: formele taal voor specificaties. Meestal gebaseerd op predikatenlogica!

Systeemeigenschappen garanderen Systemen met grote veiligheidsvereisten: – – – –

Controlesystemen voor de luchtvaart. Lanceren van ruimtetuigen. Medische toepassingen. Kerncentrales.

Kritische systeemeigenschappen moeten met absolute zekerheid gegarandeerd worden.

Vb: Twee vliegtuigen mogen nooit opstijgen vanop de zelfde startbaan binnen een interval van 1 minuut.

Ideaal: met automated reasoning bewijzen dat die kritische systeemeigenschappen een logisch gevolg zijn van de specificaties v.d. componenten.

De specificaties moeten dan geformuleerd in logicataal.

Voorbeeld: bibliotheek BibSys Als voorbeeld behandelen we een zeer eenvoudig informatiesysteem BibSys voor beheer van een bibliotheek. BibSys bestaat uit: • Een databank met tabellen:

– InHoldings: tabel met één kolom: boeken in bezit v.d. bib. – OnLoan: tabel met twee kolommen: geeft volgende relatie: boek … is uitgeleend aan persoon … – Available: tabel met één kolom: boeken aanwezig in bib.

• Software om bewerkingen (transacties) op de databank uit te voeren.

Transacties, pre- en postcondities • De meeste informatiesystemen zijn dynamisch: hun toestand verandert voortdurend. • Bewerkingen die de toestand van een informatiesysteem veranderen heten transacties. • Transacties hebben precondities: Een transactie mag alleen maar worden uitgevoerd indien de toestand v.h. systeem voldoet aan de precondities. • Transacties hebben postcondities: dat zijn de eigenschappen waaraan de toestand van het systeem voldoet na uitvoering van de transactie.

De transacties van BibSys • Borrow(u,x): persoon u leent boek x uit. Precondities: x is aanwezig in de bib. • Return(u,x): persoon u geeft boek x terug aan bib. Precondities: x is uitgeleend aan u. • Remove(x): boek x wordt uit bezit van bib. verwijderd. Precondities: x is aanwezig in de bib. • Add(x): boek x wordt aangekocht door bib. Precondities: x is niet in bezit van de bib. Notatie: variabelen x, y, z voor boeken, u, w, v voor personen.

Toestandsvariabelen • Een dynamisch informatiesysteem verandert van toestand telkens er een transactie wordt uitgevoerd. Het is in toestand 0 in het begin, in toestand 1 na eerste transactie, in toestand 2 na tweede transactie, … , in toestand s na sde transactie. • We gebruiken variabelen s, t, r, … om (namen van) toestanden van het systeem aan te duiden. Dit zijn toestandsvariabelen. • De systeemeigenchappen blijven dezelfde tijdens toestand s, voor eender welke s. We kunnen de systeemeigenschappen beschouwen als functies van s. • Men kan gewoonlijk een aantal systeemeigenschappen opsommen die de toestand van het systeem volledig beschrijven. Dit noemt men dan de toestandseigenschappen.

Toestandseigenschappen van BibSys De volgende eigenschappen (relaties) geven een volledige beschrijving van BibSys tijdens toestand s. • InHoldings(x,s): boek x is in bezit v.d. bib. tijdens toestand s. • OnLoan(x,u,s): boek x is uitgeleend aan persoon u tijdens s. • Available(x,s): boek x is aanwezig in bib. tijdens toestand s.

Pre & postcondities voor Borrow(u,x) Transactie: persoon u leent boek x. s=toestand vóór, t=toestand na. • Precondities gegeven door volgende formule BorrowPrecond(u,x,s): Available(x,s) • Postcondities informeel:

– Een boek y is Inholdings na transactie asa y is Inholdings vóór transactie. – Een boek y is uitgeleend aan persoon w na transactie asa (y=x en w=u) of y is uitgeleend aan w vóór transactie. – Een boek y is Available na transactie asa y ≠x en y is available vóór transactie.

• Postcondities formeel: gegeven door formule BorrowPostcond(u,x,s,t): (∀y)[ InHoldings(y,t) ↔ InHoldings(y,s) ] ∧ (∀y)(∀w)[ OnLoan(y,w,t) ↔ y = x ∧ w = u ∨ OnLoan(y,w,s) ] ∧ (∀y)[ Available(y,t) ↔ y ≠ x ∧ Available(y,s) ]

boeken x, y s= toestand vóór

personen u, w t= toestand na

Pre & postcondities voor Return(u,x) Transactie: persoon u geeft boek x terug. s=toestand vóór, t=toestand na. • Precondities gegeven door volgende formule ReturnPrecond(u,x,s): OnLoan(x,u,s) •

Postcondities informeel:

– Een boek y is Inholdings na transactie asa y is Inholdings vóór transactie. – Een boek y is uitgeleend aan persoon w na transactie asa ¬(y=x en w=u) en y is uitgeleend aan w vóór transactie. – Een boek y is Available na transactie asa y=x of y is available vóór transactie.

• Postcondities formeel: gegeven door formule ReturnPostcond(u,x,s,t): (∀y)[ InHoldings(y,t) ↔ InHoldings(y,s) ] ∧ (∀y)(∀w)[ OnLoan(y,w,t) ↔ ¬(y = x ∧ w = u) ∧ OnLoan(y,w,s) ] ∧ (∀y)[ Available(y,t) ↔ y = x ∨ Available(y,s) ]



Pre & postcondities voor Remove(x) Transactie: boek x wordt verwijderd. s=toestand vóór, t=toestand na. • Precondities gegeven door volgende formule RemovePrecond(u,x,s): Available(x,s) •


– Een boek y is Inholdings na transactie asa y ≠x en y is Inholdings vóór transactie. – Een boek y is uitgeleend aan persoon w na transactie asa y is uitgeleend aan w vóór transactie. – Een boek y is Available na transactie asa y ≠x en y is available vóór transactie.

• Postcondities formeel: gegeven door formule RemovePostcond(u,x,s,t): (∀y)[ InHoldings(y,t) ↔ y ≠x ∧ InHoldings(y,s) ] ∧ (∀y)(∀w)[ OnLoan(y,w,t) ↔ OnLoan(y,w,s) ] ∧ (∀y)[ Available(y,t) ↔ y ≠ x ∧ Available(y,s) ]



Pre & postcondities voor Add(x) Transactie: boek x wordt aangekocht. s=toestand vóór, t=toestand na. • Precondities gegeven door volgende formule AddPrecond(u,x,s): ¬InHoldings(x,s) •


– Een boek y is Inholdings na transactie asa y=x of y is Inholdings vóór transactie. – Een boek y is uitgeleend aan persoon w na transactie asa y is uitgeleend aan w vóór transactie. – Een boek y is Available na transactie asa y=x of y is available vóór transactie.

• Postcondities formeel: gegeven door formule AddPostcond(u,x,s,t): (∀y)[ InHoldings(y,t) ↔ y=x ∨ InHoldings(y,s) ] ∧ (∀y)(∀w)[ OnLoan(y,w,t) ↔ OnLoan(y,w,s) ] ∧ (∀y)[ Available(y,t) ↔ y=x ∨ Available(y,s) ]



Pre & postcondities: algemeen • Zij Trans(x1,…,xn) een transactie, met parameters x1,…,xn. • Met TransPrecond(x1,…,xn,s) duiden we de formule aan die de conjunctie is van al de precondities voor Trans, in functie van de toestand s vóór de transactie. • Met TransPostcond(x1,…,xn,s,t) duiden we de formule aan die de conjunctie is van al de postcon-dities voor Trans, in functie van de toestand s vóór de transactie en de toestand t na de transactie. • De postcondities drukken de toestandseigenschappen na de transactie uit in termen van de toestandseigenschappen vóór de transactie.

Software-ontwikkelingscyclus • Programmeurs schrijven code voor elke transactie. • Beschouw de pre- en postcondities van een transactie als een contract dat de programmeurs moeten tekenen. • Correctheid van de code voor een transactie betekent: wanneer de code uitgevoerd wordt in toestand die aan de precondities voldoet dan stopt het programma na eindig stappen in toestand die voldoet aan de postcondities. • Verificatie van correctheid v.d. code voor een transactie: dit is program verification: daar gaan we niet verder op in. • Onder de veronderstelling dat elke programmeur aan zijn contract voldoet, moeten we toch nog verifiëren dat het geheel werkt zoals het moet. Kritische systeemeigenschappen moeten met absolute zekerheid gegarandeerd worden. (bv. Geen twee vliegtuigen op zelfde startbaan … )

Invarianten • Kritische systeemeigenschappen zijn dikwijls invariante systeemeigenschappen. • Een systeemeigenschap P(s) heet invariant onder een transactie Trans indien het volgende geldt:

Indien eigenschap P(s) geldt in toestand s, en indien de transactie Trans het systeem wijzigt van toestand s naar toestand t, dan geldt P(t), zelfs indien toestand s het resultaat is van een systeemfout.

• Een systeemeigenschap P(s) is invariant indien ze invariant is onder alle voorziene transacties. Indien bovendien de eigenschap P geldt in de initiële toestand van het systeem, dan geldt P(s) in alle toestanden s.

Formele bewijzen van invarianten Om aan te tonen dat systeemeigenschap P(s) invariant is onder transactie Trans volstaat het te bewijzen dat volgende formule logisch waar is: (∀x1)(∀x2)…(∀xn)(∀s)(∀t) { P(s) ∧ TransPrecond(x1,…,xn,s) ∧ TransPostcond(x1,…,xn,s,t) → P(t) }

Systeemeigenschappen bewijzen Om te bewijzen dat systeemeigenschap P(s) geldt in elke toestand s volstaat het te bewijzen dat P geldt in de initiële toestand van het systeem en dat voor elke transactie Trans de volgende pred-taal-formule logisch waar is: (∀x1)(∀x2)…(∀xn)(∀s)(∀t) { P(s) ∧ TransPrecond(x1,…,xn,s) ∧ TransPostcond(x1,…,xn,s,t) → P(t) } We gaan er wel van uit dat de code voor elke transactie correct is.

BibSys: Systeemeigenschappen E1: Een boek is in het bezit van de bib als en slechts als het aanwezig is of uitgeleend is. Formeel: voor elke toestand s geldt volgende formule E1(s): (∀x)[ InHoldings(x,s) ↔ Available(x,s) ∨ (∃u)OnLoan(x,u,s) ]

E2: Geen enkel boek in bezit van de bib, is tegelijkertijd uitgeleend en aanwezig. Formeel: voor elke toestand s geldt volgende formule E2(s): (∀x)[ InHoldings(x,s) → ¬(∃u)OnLoan(x,u,s) ∨ ¬Available(x,s) ]

E3: Geen enkel boek in bezit van de bib, is uitgeleend aan meer dan één persoon. Formeel: voor elke toestand s geldt volgende formule E3(s): (∀x)[ InHoldings(x,s) → ¬(∃u)(∃w)(u ≠ w ∧ OnLoan(x,u,s) ∧ OnLoan(x,w,s)) ]

Formeel bewijs van E1(s)∧E2(s)∧E3(s) • Zeker waar als s de initiële toestand is. Het volstaat dus invariantie te bewijzen. • Het is voldoende te bewijzen dat E1(s)∧E2(s)∧E3(s) invariant is onder elk van de vier transacties. • Bv. voor transactie Borrow(u,x) moeten we bewijzen dat volgende formule logisch waar is: (∀u)(∀x)(∀s)(∀t) { P(s) ∧ BorrowPrecond(u,x,s) ∧ BorowPostcond(u,x,s,t) → P(t) }

met P(s) de formule E1(s)∧E2(s)∧E3(s). • Hiervoor kunnen we de theorem prover SPASS gebruiken!!!

Declaraties voor SPASS • Toevoegen aan declaraties van relatieidentifiers: ,(InHoldings,2),(OnLoan,3),(Available,2) • Voeg dit toe achter de gebruikelijke declaraties voor Tarski en de oefeningenzittingen. Opgepast: de letters a,b,c,…,q zijn voorbehouden voor constanten!!!

Invariantie onder Borrow Te bewijzen: volgende formule is logisch waar:

(∀u)(∀x)(∀s)(∀t) { (∀x)[ InHoldings(x,s) ↔ Available(x,s) ∨ (∃u)OnLoan(x,u,s) ] ∧ (∀x)[ InHoldings(x,s) → ¬(∃u)OnLoan(x,u,s) ∨ ¬Available(x,s) ] ∧ (∀x)[ InHoldings(x,s) → ¬(∃u)(∃w)(u ≠ w ∧ OnLoan(x,u,s) ∧ OnLoan(x,w,s)) ] ∧ Available(x,s) ∧ (∀y)[ InHoldings(y,t) ↔ InHoldings(y,s) ] ∧ (∀y)(∀w)[ OnLoan(y,w,t) ↔ y = x ∧ w = u ∨ OnLoan(y,w,s) ] ∧ (∀y)[ Available(y,t) ↔ y ≠ x ∧ Available(y,s) ] → (∀x)[ InHoldings(x,t) ↔ Available(x,t) ∨ (∃u)OnLoan(x,u,t) ] ∧ (∀x)[ InHoldings(x,t) → ¬(∃u)OnLoan(x,u,t) ∨ ¬Available(x,t) ] ∧ (∀x)[ InHoldings(x,t) → ¬(∃u)(∃w)(u≠w ∧ OnLoan(x,u,t) ∧ OnLoan(x,w,t)) ] }

SPASS bewijst dit op minder dan 0,1 seconde!!!

Invariantie onder Return Te bewijzen: volgende formule is logisch waar:

(∀u)(∀x)(∀s)(∀t) { (∀x)[ InHoldings(x,s) ↔ Available(x,s) ∨ (∃u)OnLoan(x,u,s) ] ∧ (∀x)[ InHoldings(x,s) → ¬(∃u)OnLoan(x,u,s) ∨ ¬Available(x,s) ] ∧ (∀x)[ InHoldings(x,s) → ¬(∃u)(∃w)(u ≠ w ∧ OnLoan(x,u,s) ∧ OnLoan(x,w,s)) ] ∧ OnLoan(x,u,s) ∧ (∀y)[ InHoldings(y,t) ↔ InHoldings(y,s) ] ∧ (∀y)(∀w)[ OnLoan(y,w,t) ↔ ¬(y = x ∧ w = u) ∧ OnLoan(y,w,s) ] ∧ (∀y)[ Available(y,t) ↔ y = x ∨ Available(y,s) ] → (∀x)[ InHoldings(x,t) ↔ Available(x,t) ∨ (∃u)OnLoan(x,u,t) ] ∧ (∀x)[ InHoldings(x,t) → ¬(∃u)OnLoan(x,u,t) ∨ ¬Available(x,t) ] ∧ (∀x)[ InHoldings(x,t) → ¬(∃u)(∃w)(u≠w ∧ OnLoan(x,u,t) ∧ OnLoan(x,w,t)) ] }


Invariantie onder Remove Te bewijzen: volgende formule is logisch waar:

(∀u)(∀x)(∀s)(∀t) { (∀x)[ InHoldings(x,s) ↔ Available(x,s) ∨ (∃u)OnLoan(x,u,s) ] ∧ (∀x)[ InHoldings(x,s) → ¬(∃u)OnLoan(x,u,s) ∨ ¬Available(x,s) ] ∧ (∀x)[ InHoldings(x,s) → ¬(∃u)(∃w)(u ≠ w ∧ OnLoan(x,u,s) ∧ OnLoan(x,w,s)) ] ∧ Available(x,s) ∧ (∀y)[ InHoldings(y,t) ↔ y ≠x ∧ InHoldings(y,s) ] ∧ (∀y)(∀w)[ OnLoan(y,w,t) ↔ OnLoan(y,w,s) ] ∧ (∀y)[ Available(y,t) ↔ y ≠ x ∧ Available(y,s) ] → (∀x)[ InHoldings(x,t) ↔ Available(x,t) ∨ (∃u)OnLoan(x,u,t) ] ∧ (∀x)[ InHoldings(x,t) → ¬(∃u)OnLoan(x,u,t) ∨ ¬Available(x,t) ] ∧ (∀x)[ InHoldings(x,t) → ¬(∃u)(∃w)(u≠w ∧ OnLoan(x,u,t) ∧ OnLoan(x,w,t)) ] }


Invariantie onder Add Te bewijzen: volgende formule is logisch waar:

(∀u)(∀x)(∀s)(∀t) { (∀x)[ InHoldings(x,s) ↔ Available(x,s) ∨ (∃u)OnLoan(x,u,s) ] ∧ (∀x)[ InHoldings(x,s) → ¬(∃u)OnLoan(x,u,s) ∨ ¬Available(x,s) ] ∧ (∀x)[ InHoldings(x,s) → ¬(∃u)(∃w)(u ≠ w ∧ OnLoan(x,u,s) ∧ OnLoan(x,w,s)) ] ∧ ¬InHoldings(x,s) ∧ (∀y)[ InHoldings(y,t) ↔ y=x ∨ InHoldings(y,s) ] ∧ (∀y)(∀w)[ OnLoan(y,w,t) ↔ OnLoan(y,w,s) ] ∧ (∀y)[ Available(y,t) ↔ y=x ∨ Available(y,s) ] → (∀x)[ InHoldings(x,t) ↔ Available(x,t) ∨ (∃u)OnLoan(x,u,t) ] ∧ (∀x)[ InHoldings(x,t) → ¬(∃u)OnLoan(x,u,t) ∨ ¬Available(x,t) ] ∧ (∀x)[ InHoldings(x,t) → ¬(∃u)(∃w)(u≠w ∧ OnLoan(x,u,t) ∧ OnLoan(x,w,t)) ] }


So what ? • Kritiek: veel werk om een evidentie te bewijzen? Fysisch bekeken kan een boek niet aan twee verschillende personen tegelijkertijd uitgeleend zijn…

• Wat we bewezen gaat niet over de fysische werkelijkheid maar over inhoud van de databank. We bewezen dit onafhankelijk van de details van de software, onder voorwaarde dat de code van elke transactie voldoet aan het contract van de pre- en postcondities. (Dit is niet zo evident…)

• We bewezen zelfs meer: invariantie!

Als de eigenschap geldt in een toestand die bekomen is door een systeemfout dan blijft ze toch nog gelden na eender welke (correct uitgevoerde) transactie!

Een subtiliteit… De eigenschap E3(s) zelf, is niet invariant onder Borrow. Inderdaad de volgende formule is niet logisch waar:

(∀u)(∀x)(∀s)(∀t) { (∀x)[ InHoldings(x,s) → ¬(∃u)(∃w)(u ≠ w ∧ OnLoan(x,u,s) ∧ OnLoan(x,w,s)) ] ∧ Available(x,s) ∧ (∀y)[ InHoldings(y,t) ↔ InHoldings(y,s) ] ∧ (∀y)(∀w)[ OnLoan(y,w,t) ↔ y = x ∧ w = u ∨ OnLoan(y,w,s) ] ∧ (∀y)[ Available(y,t) ↔ y ≠ x ∧ Available(y,s) ] → (∀x)[ InHoldings(x,t) → ¬(∃u)(∃w)(u≠w ∧ OnLoan(x,u,t) ∧ OnLoan(x,w,t)) ] } SPASS verifieert dit in 0,11 seconden. Door een systeemfout zou het kunnen dat in toestand s, volgens de databank, het boek x is uitgeleend aan een persoon w≠u, maar toch genoteerd als available. Na de transactie is x dan uitgeleend aan w en u (althans volgens de databank…). Dus E3(s) is niet invariant, alhoewel E1(s)∧E2(s)∧E3(s) wel invariant is!!!

Oefening • Beschouw volgende transacties op StudentenDatabank van §1: – AddGrade(student,vak,score): toevoegen aan tabel Grade. – EnrollStudent(student,vak): toevoegen aan tabel Enrolled.

• Formuleer in predikatenlogica-taal de voor de hand liggende pre- en postcondities voor deze transacties, zodanig dat het volgende gegarandeerd is:

– Een student die een score voor een vak verkrijgt moet daar voor ingeschreven zijn. – Een student die een score voor een vak verkrijgt moet automatisch voor dat vak uit de tabel Enrolled verdwijnen. Hij mag zich eventueel later terug inschrijven. – Iedereen die ingeschreven is voor een vak moet geslaagd zijn voor alle vakken die nodige voorkennis zijn voor dat vak. – Iemand die ingeschreven is of reeds geslaagd is voor een vak mag zich niet inschrijven voor dat vak.

• Variabelen:

studenten s1,s2,…; vakken v1,v2,…; score g1, g2,…

HOOFDSTUK IV Toepassingen in Informatica

Recommend Documents