(kulcs, transzformációsorozat)

Azaz definiáljuk az új módosítófile típusát az alábbi módon:

Legyen és . Ezekkel a típusdefiníciókkal a módosítófile így írható le:

Ezzel a módosítófile-lal tehát eljutottunk a kétváltozós egyértékű (hibafile használata esetén kétértékű) elemenkénti feldolgozáshoz. Az egyetlen különbség csak az, hogy az adott transzformáció-sorozat végrehajtását meg kell valósítanunk az eredeti állapottéren. Ehhez szükségünk lesz az szibólumra, amely értéket hozzávesszük az adatrész típusához: . Az, hogy egy törzsrekord adatrésze azt jelenti, hogy a rekordot nem kell kiírni az eredményfile-ba.

Az elemenként feldolgozható függvényünk:

A transzformációsorozat elvégzése csak a transzformációk megfelelő sorrendje esetén lehetséges. Ha egy transzformációsorozat egy tagját nem lehet elvégezni, akkor azt a sorozatból ki kell hagyni (esetleg hibát kell jelezni). Ezzel az függvény egyértelműen definiált.

Írjuk fel tehát a fenti megfontolások alapján a kétváltozós elemenkénti feldolgozás programját a megfelelő behelyettesítésekkel:

Definiálnunk kell még, hogy mit jelent a fenti struktogramban a transzformációsorozat elvégzése. Ehhez bevezetjük az rekurzívan definiált függvényt:

ahol

A fenti definícióban szereplő művelet elvégzésén az alábbi függvényértékeket értjük: Legyen , ekkor:

Az függvényt kiszámító – a módosítássorozatot elvégző – program:

Mivel az aktuális adat értéke lehet is, a művelet helyett az alábbi programot használjuk:

Térjünk most vissza az eredeti állapottérre. Ekkor a főprogram:

Az a már korábban definiált rekurzív függvényt kiszámító program megvalósítása az eredeti állapottéren:

A gyakorlatban sokszor találkozhatunk olyan file-okkal, amelyek rekordjaiban van valamilyen kulcsmező ami szerint a file rendezett, ám de a file mégsem egyértelmű kulcs szerint, és így a file a kulcsmezőre vonatkoztatva nem elemenként feldolgozható. A következőkben egy olyan technikát fogunk bemutatni, amelyben egy új kulcsot definiálunk a file-ra, és ezen új kulcs szerint a file már egyértelmű.

Tegyük fel, hogy a file típusú rekordokból áll. Az új kulcsot úgy kapjuk, hogy az egymás után levő azonos kulcsokat megsorszámozzuk. Legyen tehát , ahol . Legyen továbbá :

Ekkor tetszőleges esetén – feltéve, hogy a kulcs szerint rendezett – a kulcs szerint rendezett és egyértelmű.

Természetesen a fenti megszámozást általában csak az absztrakció leírására használjuk, és csak ritkán fordul elő, hogy a függvény által definiált absztrakciót meg is valósítjuk.

Egy adott feladat megoldását mindig elkerülhetetlenül befolyásolja a specifikáció módja. A függvényabsztrakció lényege abban rejlik, hogy a megoldást egy alkalmasan választott függvény helyettesítési értékének kiszámítására vezetjük vissza.

Induljunk ki egy olyan absztrakt file-ból, mint amilyet az egyváltozós elemenkénti feldolgozásra való visszavezetésben használtunk. Természetesen, mivel most a módosítófile nem egyértelmű kulcs szerint, az absztrakt file definíciója kissé módosul: ha egy kulcs mindkét file-ban szerepel, akkor a törzsrekordot az első rá vonatkozó módosítórekorddal vonjuk össze, és az esetlegesen előforduló további azonos kulcsú módosítórekordokból pedig egy-egy olyan absztrakt rekordot képezünk, amelynek adatrésze .

Ez az absztrakció az imént bemutatott egyértelműsítő leképezésen keresztül implicit módon írható le: legyen , és . Ekkor

és :

Megoldás függvénykompozícióval

Először egy olyan megoldást adunk a feladatra, amelynek specifikációjában az utófeltétel egy kompozícióval adott függvény kiszámítása, ahol a kompozíció egy rekurzív módon megadott függvényből és egy esetszétválasztással definiált függvényből áll.

ahol ,

és ,

Az függvény kezdőértékének definíciójában szereplő kulcsérték egy tetszőleges olyan kulcsérték lehet, amely egyik file-ban sem fordul elő.

Mivel az utófeltétel függvénykompozícióval adott, a megoldás egy szekvencia lesz, amelynek első része az , második része pedig a függvényt számítja ki. Az függvény egyes komponenseinek rendre a változók felelnek meg.

Az absztrakt file műveleteinek megvalósítása:

Hátra van még a transzformáció elvégzésének megvalósítása:

Megoldás extremális elemmel

Az előző megodás szépséghibája, hogy a feladatot nem egy függvény helyettesítési értékének kiszámításaként specifikáltuk. Ezért adunk most egy másik megoldást is, amely egy a gyakorlatban sokszor hasznos eszközt használ. Ez az utolsó utáni elem bevezetése ( extremális elemmel).

Egészítsük ki az előző megoldásban szereplő file-t – ha nem üres – egy olyan elemmel, amelynek kulcsa minden lehetséges kulcsértéktől eltér. Jelöljük ezt a típust -sal. Ekkor a két típus közötti megfeleltetés: ,

A kiszámolandó rekurzív függvény majdnem teljesen megegyezik az előzővel. A jobb áttekinthetőség érdekében a függvényt most komponensenként fogjuk felírni. Ahhoz, hogy a függvényt egyszerűbben írhassuk fel, tegyük fel, hogy az üres sorozatra alkalmazott függvény nem definiált értéket ad vissza (így a nem csak parciális függvény, hiszen minden sorozatra alkalmazható). Ekkor ,

Ezt a függvényt használva a feladat specifikációja:

Ez a feladat visszavezethető file-ra felírt rekurzívan megadott függvény helyettesítési értékének kiszámítására:

Az absztrakt file műveleteinek megvalósítása:

A transzformáció elvégzésének megvalósítása tulajdonképpen megegyezik az előző esetnél felírttal, csak most az absztrakt file-t használjuk:

A fenti megoldási módokat összehasonlítva látható, hogy minél magasabb absztrakciós szintű fogalmakat használunk, annál egyszerűbben tudjuk kezelni a feladatot.

Nagyon sok esetben az adat- és függvényabsztrakció is alkalmazható egy feladat megoldásakor, sőt mint azt az iménti példa mutatja a kettő kombinációja is egy lehetséges út.