0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ What's the source for the table? Have you asked them? Where did you see the table? What does "Data Comp." and "Expression Comp." mean? Is there any surrounding context? You're asking us to read the mind of the person who wrote that table, and we're more likely to be able to do that effectively if you can give us as much information about context as possible. $\endgroup$ – D.W.♦ Jan 29 '18 at 17:43
  • $\begingroup$ It looks like 'Data Comp.' is the data complexity and 'Expression Comp. ' is the combined complexity. In particular, the data complexity is measured with respect to determining if a fixed formula holds in a given structure A (so the structure is input), where the combined complexity takes both the formula and the structure as input. $\endgroup$ – Sam McGuire Jan 29 '18 at 17:49
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Database is an universum? $\endgroup$ – Carol Jan 29 '18 at 18:06
  • $\begingroup$ "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." I don't understand. Before, you said that it requires exponential time and I agree with that. $\endgroup$ – Carol Jan 29 '18 at 18:07
  • $\begingroup$ "Universum" isn't an English word so I'm not sure what you mean -- sorry! Programs can require exponential time and polynomial space. For example, for i=1 to 2^n do [...] takes time exponential in $n$ but you can store the loop variable using only $n$ bits, which is polynomial space. $\endgroup$ – David Richerby Jan 29 '18 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.