a linear order, first-order logic with a commutative, transitive closure operator added yields L, problems solvable in logarithmic space. In the presence of a linear order, first-order logic with a transitive closure operator yields NL, the problems solvable in nondeterministic logarithmic space. In the presence of a linear order, first-order logic with a least fixed point operator gives P, the problems solvable in deterministic polynomial time. On all finite structures (regardless of whether they are ordered), Existential second-order logic gives NP (Fagin's theorem). Applications Database theory A substantial fragment of SQL (namely that which is effectively relational algebra) is based on first-order logic (more precisely can be translated in domain relational calculus by means of Codd's theorem), as the following example illustrates: Think of a database table "GIRLS" with the columns "FIRST_NAME" and "LAST_NAME". This corresponds to a binary relation, say G(f, l) on FIRST_NAME X LAST_NAME. The FO query {l : G('Judy', l)}, which returns all the last names where the first name is 'Judy', would look in SQL like this: select LAST_NAME from GIRLS where FIRST_NAME = 'Judy' Notice, we assume here, that all last names appear only once (or we should use SELECT DISTINCT since we assume that relations and answers are sets, not bags). Next we want to make a more complex statement. Therefore, in addition to the "GIRLS" table we have a table "BOYS" also with the columns "FIRST_NAME" and "LAST_NAME". Now we want to query the last names of all the girls that have the same last name as at least one of the boys. The FO query is {(f,l) : ∃h ( G(f, l) ∧ B(h, l) )}, and the corresponding SQL statement is: select FIRST_NAME, LAST_NAME from GIRLS where LAST_NAME IN ( select LAST_NAME from BOYS ); Notice that in order to express the "∧" we introduced the new language element "IN" with a subsequent select statement. This makes the language more expressive for the price of higher difficulty to learn and implement. This is a common trade-off in formal language design. The way shown above ("IN") is by far not the only one to extend the language. An alternative way is e.g. to introduce a "JOIN" operator, that is: select distinct g.FIRST_NAME, g.LAST_NAME from GIRLS g, BOYS b where g.LAST_NAME=b.LAST_NAME; First-order logic is too restrictive for some database applications, for instance because of its inability to express transitive closure. This has