First Order Logic, First Order Logic + Recurrence and SQL
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&nbsp;$n$, so a formula of length&nbsp;$\ell$ can take time $n^\ell$, which is an exponential function of&nbsp;$\ell$ when $n$&nbsp;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.