Špecifikácia

Meno:	Slavomír Takáč
Názov:	prekladač inštrukcií z datalógu do SQL
Jazyk:	Java
Prostredie:	konzola (vstupný a výstupný súbor)
Funkčnosť:	Užívateľ štandardne zadáva dva parametre: cestu k vstupnému a k výstupnému súboru (ak nezadá cestu k výstupnému súboru, tak výpis pôjde na štandardný výstup. ak nedá cestu k vstupnému, tak sa zobrazí info o programe). Vstupným súborom sú definície predikátov v jazyku datalog. Avšak každý predikát (s výnimkou "subtotal", keďže už je súčasťou datalogu) prv než bude použitý, tak musí byť naprv špecifikovaný v komentári (za znakom "%"), kde budú uvedené názvy jednotlivých jeho atribútov, pričom sa to týka všetkých predikátov zo súboru, teda nie len tých, ktoré budú definované, ale aj tých, o ktorých už predpokladáme, že sú uložené v databáze. Program bude najprv kontroľovať koreknosť vstupu a ak nebude korektný, tak uvedie súradnicu prvého nekorektného miesta a aj popis, prečo je nekorektné a ako to má byť správne. Okrem klasických požiadaviek korektného vstupu ešte pripúda požiadavka, aby každá premenná vyskytujúca sa v hlavičke definície, alebo v porovnávacom výraze (napr. X>5), sa nachádzala aj ako argument nejakého ne-negovaného predikátu v tele definície. Výstupným súborom bude preklad vstupného kódu do jazyka SQL, ktorý bude predstavovať definície "WITH", ktorých názov a mená atribútov budú totožné s tým, čo bolo zadané vo vstupnom súbore. Jednotlivé predikáty vo výstupnom súbore budú usporiadané do topologického poradia, t.j. každá definícia závisí len od predikátov, ktoré už boli definované pred ňou. V prípade, že niektorý predikát nie je možné uviesť v takomto poradí, t.j. že ide o rekurziu, tak ten predikát bude mať uvedené "WITH RECURSIVE", avšak ostané predikáty, ktorých graf závislostí netvorí cyklus, budú uvedené klasicky.
Zdrojový kód:	stiahnuť

Časový plán:

do 15.12.2007:	prostredie
do 31.01.2007:	kontrola syntaxe a bezpečnosti predikátov
do 31.03.2008:	preklad elementárnych požiadaviek do SQL
do 30.06.2008:	preklad rekurzií, agregácií, porovnávania výrazov

spôsob riešenia:

Najprv bude program po jednotlivých znakoch čítať vstup a kontroľovať jeho korektnosť. Táto časť je implementovaná pomocou deterministického automatu, kde v premennej q mám uložené číslo stavu, a pri každom novom písmene automat zmení (alebo nezmení) stav, podľa toho, ako to je definované v prechodovej funkcii. Tak v každom stave je jednoznačné, v akej časti definície sa nachádzame, a aké písmená môžu nasledovať, pričom akonáhle príde nejaké iné písmeno, tak automat vypíše chybovú hlášku špecifickú pre konkrétny typ chyby. Automat používa zásobník, v ktorom si pamätá počet zátvoriek, zoznam premenných z hlavičky a porovnávacích výrazov a tiež, ktoré z nich sa už nachádzali aj v nejakom pozitívnom kontexte. Tak napr. ak príde znak "." oznamujúci koniec definície, tak program upozorní na prvú z tých premenných, od akých sa požaduje výskyt v pozitívnom kontexte, a ktoré to nesplnili.

vstup	výstup
% objednavky(klient, vyrobok) % objednava_od_hp(klient, vyrobok) objednava_od_hp(K, V):-objednavky(K, _), V>1.	Error in (3:45): Here cannot be '.', because variable 'V' is not used in positive predicate yet.

Podobne keby nejaký predikát mal viac alebo menej atribúdov než bolo uvedené v definícii.

vstup	výstup
% objednava_od_hp(klient, vyrobok) objednava_od_hp(K, V, X):-objednavky(K, _), V>1.	Error in (2:21): here must be ')', compare with definition of predicate 'objednava_od_hp' on line 1

Vstup je takto postupne ukladaný do objektovej štruktúry, ktorá pozostáva zo zoznmau predikátov, kde pre každý predikát si pamätáme jeho meno, názov svojich atribútov a riadok, v ktorom bol špecifikovaný (v poznámke), a zoznam definícií, ktorými je popísaný, pričom každá definícia má svoju hlavičku a zoznam telových častí, kde každá z takýchto častí má svoj názov a argumenty, pričom argumentami môžu byť textové reťazce, premenné, číselné konštanty, alebo matematické výrazy zložené z číselných konštánt a premenných. Pri telách definície si tiež pamätáme, či boli negované alebo nie. Taktiež rozlišujeme bežné predikáty od porovnávaní. Rozlišujeme tiež, či argumentom v predikáte je holá premenná, alebo matematický výraz, atď. Osobitným predikátom je "subtotal", ktorý nie je (ani nemá byť) špecifikový v komentári. Ten je aj špeciálnym spôsobom uložený. Podobne aj výrazy porovnávania sú špeciálne ošetrené.

Po prečítaní celého vstupu sa každému predikátu priradí zoznam ukazovateľov na predikáty, od ktorých je závislý. A aj naopak, ktoré od neho závisia. Tým získame graf, kde predikáty sú vrcholy a jednotlivé ukazovatele sú orientované hrany. Vytvoríme si zoznam listov grafu, t.j. zoznam, do ktorého si zaznamenáme všetky predikáty, ktoré od nikoho nezávisia. Postupne budem vyberať predikáty z tohto zoznamu a prekladať ich do jazyka SQL a vypisovať na výstup. Pričom zakaždým, keď zo zoznamu odstránim list, tak zruším aj hrany vchádzajúce do tohto vrcholu. To znamená, že hrany vždy ukazujú aktuálne len na zatiaľ nespracované vrcholy (predikáty). Pri každom odstraňovaní hrany si stačí skontroľovať, či to nebola posledná hrana vychádzajúca z dotyčného vrchola, lebo ak áno, tak to znamená, že aj ten vrchol sa stal práve listom a teda v takom prípade ho pridám do zoznamu listov. Takýmto algoritmom zrejme budem spracovávať predikáty v ich topologickom usporiadaní, teda vždy každý závisí len od tých, čo sú už spracované. Problém nastane v prípade, že po skončení ešte ostanú nejaké nespracované predikáty. To totiž znamená, že tieto predikáty sú už v takých vzájomných vzťahoch, že žiaden z nich nemožno vyriešiť bez použitia rekurzie. Vtedy si zaznačíme, že ide o rekurzívne premenné a postupujeme podobne, ibaže už budeme dávať "WITH RECURSIVE", napr.:

vstup	výstup
%child(kto,koho) %parent(kto,koho) %ancestor(kto,koho) parent(X,Y) :- child(Y,X). ancestor(X,Y) :- parent(X,Y). ancestor(X,Y) :- ancestor(X,Z),ancestor(Z,Y).	WITH parent(kto, koho) AS   SELECT DISTINCT c.koho as kto, c.kto as koho FROM child c; WITH RECURSIVE ancestor(kto, koho) AS   SELECT DISTINCT p.kto as kto, p.koho as koho FROM parent p  UNION   SELECT DISTINCT a.kto as kto, a2.koho as koho FROM ancestor a, ancestor a2 WHERE a2.kto=a.koho;

Ostáva už len najdôležitejšia principiálna otázka: ako robiť samotné preklady. Keď už spracovávam konkrétny predikát, t.j. jednotlivé jeho definície, najprv vytvorím nové predikáty pre jednotlivé subtotaly, ktoré budem číslovať: subtotal, subtotal2, subtotal3, ..., vždy ako názov priraďujem prvé zatiaľ nepoužité meno z uvedenej postupnosti. Argumenty subtotalu sú najprv tie, podľa ktorých sme grupovali (ich názvy poznáme), a ostatné sú tie, ktoré sú vysledkami jednotlivých agregačných funkcií, teda prideľujem im názvy: agg, agg2, agg3, ... Tieto nové predikáty klasickým spôsobom preložím a vypíšem a tak v pôvodných definíciách predikátov už nemám žiadne subtotaly, ale postupujem už len ako s klasickými predikátmi a porovnávacími výrazmi.
A pri takých postupujem nasledovne:
- textovým reťazcom (t.j. tie, čo začínajú malým písmenom) pridám z oboch strán úvodzovky.
- každému predikátu v tele definície priradím alternatívny názov, ktorým je prvé písmeno jeho názvu, a ak je treba, tak aj číslo: 2, 3, 4... (to uvedieme do časti FROM, kde vymenujeme všetky predikáty vyskytujúce sa v kladnom kontexte a za nich uvedieme ich alternatívny názov, pod ktorým ich budeme označovať vo WHERE podmienke a v SELECTE)
- ku každej premennej (t.j. reťazec začínajúci veľkým písmenom) nájdem prvý výskyt, kde sa v tele definície nachádza v nejakom pozitívnom predikáte. Nech je to predikát P s alternatívnym názvom A, a je to jeho i-ty argument, pričom z definície P vieme, že i-ty argument ma nazov N. Tak uvedenú premennú nahradím výrazom "A.N" (bez úvodzoviek). Jedinou výnimkou je prípad, že prvé také miesto bola samotná tá premenná. Ako o chvíľku uvidíme, takúto situáciu môžme ignorovať, pretože by to znamenalo rovnosť P.N=P.N, čo je tautológia, teda ju možno z konjunkcie odstrániť (zákon idempotentnosti). Keď už totiž vo všetkých výrazoch mám preložené premenné, tak ak predikát s alternatívnym názovm B, v j-tom argumente (ktorý má podľa definície názov M) má výraz R, tak do WHERE podmienky pridáme: "B.M=R" (bez úvodzoviek). Samozrejme, okrem prípadu, že R je prázdne (t.j. "_"), vtedy to tiež môžem ignorovať.
Podobne aj výrazy porovnávania ak sú už oba termy zasubstituované vyššie uvedeným spôsobom, tak možno priamo pridať do where podmienky.
Napokon ostávajú predikáty v negatívnom kontexte, tam uvediem do WHERE podmienky "NOT EXISTS (SELECT * FROM nazov alternazov WHERE...)", kde "WHERE..." zostavím takým istým algoritmom ako v klasickom WHERE, t.j. ak j-ty argument (pozn. meno j-teho atribútu vieme z definície, napr. nech je to M) po aplikovaní horeuvedeného postupu je R, tak do príslušnej WHERE... podmienky dáme "alternazov.M=R".
napr.:

vstup	výstup
%zena(kto) %dieta(kto,koho) %otec(kto,koho) otec(X,Y) :- dieta(Y,X), \+zena(X).	WITH otec(kto, koho) AS   SELECT DISTINCT d.koho as kto, d.kto as koho FROM dieta d WHERE NOT EXISTS (SELECT * FROM zena as z WHERE z.kto=d.koho);

A samozrejme, ak je viacero definícií, tak sa spájajú pomocou "UNION", ako si možno všimnúť v pred-predošlom príklade. Ešte uvediem jeden jednoduchý príklad na subtotal a porovnávanie:

vstup

výstup

%firmy(firma, mesto), %dodava(firma, vyrobok, cena, lehota), %objednavky(klient, vyrobok) %objednava_od_hp(klient, vyrobok) %vela_od_hp(klient, pocet) objednava_od_hp(K, V) :- objednavky(K, V), dodava(hp, V, _, _). vela_od_hp(K, P) :- objednavky(K, _), \+((P < 1000)),      subtotal(objednava_od_hp(K, V), [K], [count(V, P)]).

WITH objednava_od_hp(klient, vyrobok) AS   SELECT DISTINCT o.klient as klient, o.vyrobok as vyrobok FROM objednavky o, dodava d WHERE d.firma="hp" AND d.vyrobok=o.vyrobok; WITH subtotal(klient, agg) AS SELECT DISTINCT klient, count(vyrobok) as agg FROM objednava_od_hp GROUP BY klient; WITH vela_od_hp(klient, pocet) AS   SELECT DISTINCT o.klient as klient, s.agg as pocet FROM objednavky o, subtotal s WHERE s.klient=o.klient AND s.agg>=1000;

Samozrejme, ešte som dorobil drobné zjednodušenia matematických výrazov, ako si možno všimnúť aj v poslednom príklade, kde výraz \+((P < 1000)) bol po dosadení premennej aj zjednodušený na s.agg>=1000, ale to sú už len detaily. Podstata algoritmu spočíva vo vyššie uvedenom.

stiahnuť zdrojový kód