Dotazovací jazyky II

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

• http://www.ksi.mff.cuni.cz/~pokorny/vyuka.html#NDBI006
• http://www.ksi.mff.cuni.cz/~vojtas/vyuka/NDBI006DotazovaciJazykyII/DJII.html
• neoficální sbírka příkladů
• http://dl.acm.org/citation.cfm?id=1567278
  • example 2.4

Starší

• http://www.ksi.mff.cuni.cz/~vojtas/vyuka/NDBI006DotazovaciJazykyII/1112/DJII.html
• http://www.ksi.mff.cuni.cz/~vojtas/vyuka/NDBI006DotazovaciJazykyII/1011/DJII.html
• http://www.ksi.mff.cuni.cz/~vojtas/vyuka/DBI006_Dotazovaci_jazykyII/0910/DJII.html

Osnova

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

Příklad na produkční operátor T_P

• 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

T_P$ \uparrow $0 = {}

T_P$ \uparrow $k = T_P(T_P$ \uparrow $k-1)

T_P$ \uparrow $α = $ \bigcup ${ T_P$ \uparrow $β: β<α } .. α limitní

T_P$ \downarrow $0 = B_P

T_P$ \downarrow $k = T_P(T_P$ \downarrow $k-1)

T_P$ \downarrow $α = $ \bigcap ${ T_P$ \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(f^k-1(b)) }

..

T$ \uparrow $ω = { q(b), q(f(b)), .., q(fⁿ(b)), .. } = lfp .. dál se již nemění

• Spočtěte gfp

Herbrandovská báze B_P = { p(X), p(fⁿ(X)), q(X), q(fⁿ(X)), r(X), r(fⁿ(X)); X$ \in ${a,b,c}, n>=1 }

T$ \downarrow $0 = B_P

T$ \downarrow $1 = { p(a), p(f^m(a)), p(fⁿ(b)), p(fⁿ(c)), q(b), q(f^m(b)) q(fⁿ(a)), q(fⁿ(c)), r(c), r(f^m(c)), r(fⁿ(a)), r(fⁿ(b)); n>=2, m>=1 } .. odstraníme prvky, co nejsou důsledkem předchozího kroku

..

T$ \downarrow $k = { p(a), p(f^m(a)), p(fⁿ(b)), p(fⁿ(c)), q(b), q(f^m(b)) q(fⁿ(a)), q(fⁿ(c)), r(c), r(f^m(c)), r(fⁿ(a)), r(fⁿ(b)); n>=k+1, m>=1 }

..

T$ \downarrow $ω = { p(a), p(f^m(a)), q(b), q(f^m(b)), r(c), r(f^m(c)); m>=1 } .. není to ještě fix-point

T$ \downarrow $ω+1 = { p(a), p(f^m(a)), q(b), q(f^m(b)), r(f^m(c)); m>=1 }

..

T$ \downarrow $ω*2 = { q(b), q(f^m(b)), p(a), p(f^m(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!!!