Relační algebra a DATALOG

• Tv.: Nerekurzivní programy DATALOGu vyjadřují právě ty dotazy, které jsou vyjádřitelné v AR.

• Důkaz:  indukcí dle počtu operátorů v E

• 1.  operátorů: E  R R je z EDB, tj. nic do IDB

• E  konst. relace

• pak pro každou n-tici přidej p(a1,…,an) do EDB

• 2. E  E1  E2

• dle indukční hypotézy existují programy pro E1 a E2 (odpovídající predikáty e1 a e2 )

• e(x1,…,xn) :- e1(x1,…,xn)

• e(x1,…,xn) :- e2(x1,…,xn)