# Is it possible to encode logical expression and interpret it with SQL?

Is it possible without any forms of eval or stored procedures to execute a query, which interprets logical expression, encoded in some way in a table (or two tables) of relational database?

For example, one table can contain a mapping for variable names into their truth values (V1), and another table or two (L1 and L2) - encode logical expressions, eg, in a conjunctive normal form.

Then some clever SQL query will interpret the logical expression from L1-L2, and apply values for variables from V1. (And of course same can also be done for multiple different expressions in the same query).

At first, this seems non-trivial to construct, but SQL has aggregating functions, so theoretically should be possible?

• Modern SQL is Turing-complete, so you probably want to be clearer about what you mean (maybe restrict to relational algebra rather than SQL), or the answer is "yes". That said, evaluating a logical expression doesn't require Turing-completeness. Feb 13 '19 at 21:27
• I mean less advanced SQL, without RECURSIVE. But I think "SQL without tricks" is still quite intuitive. Limiting to relational algebra may be a bit too restrictive and lead to even more complex constructs. Feb 14 '19 at 4:15

Using disjunctive normal form (DNF) representation. The following 3 tables arrangement seems to solve the problem (NB: using better names for tables, not same as in the question):

> select * from F;
+------+------+
| f1   | f2   |
+------+------+
|    1 |    1 |
|    1 |    2 |
+------+------+

> select * from C;
+------+------+
| c1   | c2   |
+------+------+
|    1 | A    |
|    1 | B    |
|    2 | C    |
+------+------+

> select * from V;
+------+------+
| v1   | v2   |
+------+------+
| A    |    0 |
| B    |    0 |
| C    |    1 |
+------+------+


Where F is a table for formulae, mapping from formula number to a table of conjuncts (C), which has a pointers into table of variables (V). The formula encoded here is (A AND B) OR C.

Doing conjunction is simply a matter of applying min() and disjunction is done by max().

Evaluating formula (number 1 in the example above) can be done by the following query:

> select max(A.v) as result from F, (select min(v2) as v, c1 from C, V
where c2 = v1 group by c1) as A
where c1 = f2 and f1 = 1;
+--------+
| result |
+--------+
|      1 |
+--------+


The above approach is a bit simplified - NOT is not possible to express, but it is easy to add it as an extra boolean column of table C and XORing it with the variable value.