What kind of language is SQL?

Question

Is SQL a context free language or some other type of language?

Ilse

Do you mean is SQL also regular? CFG's encompass regular languages. So, they aren't mutually exclusive. To answer your question though, SQL is not a regular language. – Tesstessa

Does SQL uses both regular and context free grammar contexts ? In that case, being an intersection of both, it is still context free. – Ilse

Just to clarify, a language is context-free when it is generated by a context-free grammar. There're SQL context-free grammar definitions online. Just google around and you'll find some. Here's one, for example. – Zimmermann

Does the DELIMITER command throw a wrench in that at all? – Apgar

Answer 1

According to https://stackoverflow.com/a/31265136 SQL is not a regular language. The short explanation is that each select query looks like

 SELECT x FROM y WHERE z

and y can be another select query itself, so it cannot be simulated with finite-state machine. As mentioned before, there are some CFGs for SQL standarts in Backus–Naur Form, thereby SQL is nonregular context free language.

Verified

Answer 2

Any CFG for SQL will do most of the work, but will always be slightly too permissive.

A good example of an SQL CFG comes from antlr: https://github.com/antlr/grammars-v4/blob/master/sql/plsql/PlSqlParser.g4#L1982

But at that line (1982), you see that in a values_clause, column values are recursively added regardless of how many columns might be specified, or how many values are in another row, which is invalid sql:

insert into xyz values
  (1, 'hello'),
  (2, 'bye'),
  (3, 'hi', 'uhm...'); -- invalid!

Try running it here: https://www.db-fiddle.com/f/6gwgcg6qBLKpFbCEPtB6dy/0

This syntax can never be fully encapsulated by a CFG, as it is equivalent to the { (a^n)(b^n)(c^n) : n ≥ 1 } language, which is famously not allowed in CFGs (but allowed in CSGs)

You could argue this is a runtime error instead of a parsing error. But you can use the same argument for every language that is interpreted, so it's a bit of a grey area.

Triumphal

Answer 3

@aquinas wrote:

Do you mean is SQL also regular? CFG's encompass regular languages. So, they aren't mutually exclusive. To answer your question though, SQL is not a regular language.

@MSX wrote:

Just to clarify, a language is context-free when it is generated by a context-free grammar. There're SQL context-free grammar definitions online. Just google around and you'll find some. Here's one, for example.

Indian

(Answered in the comments and converted to a community wiki.) – Fenner

Answer 4

Similar in PL/SQL context can be exactly what code it is SQL or PL/SQL because if we define function keywords as concrete, then if we want to control which functions can be used, this context must be known

Loeb

By me it's when some syntax nonterminal resoult depends on some state (or context), that can be determinated early in parsing process – Loeb