0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Derek Elkins Feb 13 at 21:27
  • $\begingroup$ 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. $\endgroup$ – Roman Susi Feb 14 at 4:15
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.