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.