we know that SQL standard is equivalent to First Order Logic (FOL). I've seen at my lecture that graph connectivity cannot be expressed by FOL, so in SQL as well. But we know that we can easily solve that problem in PTIME. And I've seem the following table:
Query Language Data Comp. Expression Comp.
FOL LOGSPACE PSPACE
FP PTIME EXPTIME
I am not sure what is FP
. But, I suppose that it is FIXPOINT
. I mean, a first order logic with recursion + fixpoint.
I don't understand that table. I understand the Data Comp. But, I cannot what Expression Comp. means and why Expression Comp.
for FP
requires so much time.