First Order Logic, First Order Logic + Recurrence and SQL

Question

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.

Answer 1

Yes, FP will be first-order fixed-point logic.

Data complexity is the maximum complexity of the problem of evaluating a fixed formula of the logic on a database, as a function of the size of the database. Expression complexity (also known as formula complexity) is the complexity of evaluating a formula on a fixed database, as a function of the formula size (e.g., its length as a string of characters). Combined complexity, which isn't mentioned in your table, is the complexity of evaluating a formula on a database as a function of the size of those two things.

The expression complexity of first-order logic is high because, for example, a formula $\forall x_1\dots \forall x_k$ requires time $n^k$ to evaluate on a database of size $n$, so a formula of length $\ell$ can take time $n^\ell$, which is an exponential function of $\ell$ when $n$ is treated as a fixed constant. However, we can do this in polynomial space, since all we need to do is loop through potential values of variables and that requires storing just one value per variable.