Skip to main content
3 of 5
adding a clarifying remark regarding the meaning of "captures"
Raphael
  • 72.9k
  • 30
  • 181
  • 393

Extension of SQL capturing $\mathsf{P}$

According to Immerman, the complexity class associated with SQL queries is exactly the class of safe queries in $\mathsf{Q(FO(COUNT))}$ (first-order queries plus counting operator).

Is there an extension of SQL (implemented and used in the industry) which captures polynomial time computable queries (and no others)? If there isn't, is there a reason? Are the queries that are needed in practice usually simple enough that there is no need for a stronger language?

Kaveh
  • 22.5k
  • 4
  • 52
  • 112