Skip to main content
2 of 5
added 208 characters in body
Kaveh
  • 22.5k
  • 4
  • 52
  • 112

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? 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