Tvrzení o závislostech (1)

• Tv: Nejlepší procedura řešící problém příslušnosti ke třídě typovaných plných závislostí má exponenciální časovou složitost.

• Pz.: Problém příslušnosti pro plné závislosti je týž pro konečné i nekonečné relace.

• Př.:  = {A  B, A  B }

• : B  A

• Platí:    

• např. na relaci {(i+1,i): i 0}