Dotazovací jazyky II

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
Dotazovací jazyky II
Kód předmětu: NDBI006
Přednáší: Peter Vojtáš
  • zkouška: písemná – příklady
  • zápočet: referát na semináři (po trojicích, PowerPointová prezentace), jinak psané (Word)

Zdroje[editovat | editovat zdroj]

Starší[editovat | editovat zdroj]

Osnova[editovat | editovat zdroj]

  • Jako DJ2 s Pokorným + něco navíc
    • Herbrandovské modely a operátor TP
    • T-query
    • ..

Příklad na produkční operátor TP[editovat | editovat zdroj]

  • Množí se otázky jak na to, zde je ukázka. Co si ještě vybavím. Na utvoření názoru na řešení určitě postačí. Za správnost neručím.
  • Opáčko
TP$ \uparrow $0 = {}
TP$ \uparrow $k = TP(TP$ \uparrow $k-1)
TP$ \uparrow $α = $ \bigcup ${ TP$ \uparrow $β: β<α } .. α limitní
TP$ \downarrow $0 = BP
TP$ \downarrow $k = TP(TP$ \downarrow $k-1)
TP$ \downarrow $α = $ \bigcap ${ TP$ \downarrow $β: β<α } .. α limitní
  • Příklad
P = {
q(b) <−
q(f(x)) <− q(x)
p(f(x)) <− p(x)
p(a) <− p(x)
r(c) <− r(x), q(x)
r(f(x)) <− r(x)
}
  • Spočtěte lfp
T$ \uparrow $0 = {}
T$ \uparrow $1 = { q(b) } .. přidáme prvky, co jsou důsledkem předchozího kroku
T$ \uparrow $2 = { q(b), q(f(b)) }
..
T$ \uparrow $k = { q(b), q(f(b)), .., q(fk-1(b)) }
..
T$ \uparrow $ω = { q(b), q(f(b)), .., q(fn(b)), .. } = lfp .. dál se již nemění


  • Spočtěte gfp
Herbrandovská báze BP = { p(X), p(fn(X)), q(X), q(fn(X)), r(X), r(fn(X)); X$ \in ${a,b,c}, n>=1 }
T$ \downarrow $0 = BP
T$ \downarrow $1 = { p(a), p(fm(a)), p(fn(b)), p(fn(c)), q(b), q(fm(b)) q(fn(a)), q(fn(c)), r(c), r(fm(c)), r(fn(a)), r(fn(b)); n>=2, m>=1 } .. odstraníme prvky, co nejsou důsledkem předchozího kroku
..
T$ \downarrow $k = { p(a), p(fm(a)), p(fn(b)), p(fn(c)), q(b), q(fm(b)) q(fn(a)), q(fn(c)), r(c), r(fm(c)), r(fn(a)), r(fn(b)); n>=k+1, m>=1 }
..
T$ \downarrow $ω = { p(a), p(fm(a)), q(b), q(fm(b)), r(c), r(fm(c)); m>=1 } .. není to ještě fix-point
T$ \downarrow $ω+1 = { p(a), p(fm(a)), q(b), q(fm(b)), r(fm(c)); m>=1 }
..
T$ \downarrow $ω*2 = { q(b), q(fm(b)), p(a), p(fm(a)); m>=1 } = gfp .. dál se již nemění

Niekto tu pri mne sedi a chce po mne aby som sem pridal link http://www.ksi.mff.cuni.cz/~vojtas/vyuka/DBI006_Dotazovaci_jazykyII/0910/02_TabDot_StatAnal_Opt_0910/NDBI006_02_StatAnalOpt_0910.ppt ma pistol!!!