Модель данных для логических выражений

Question

Знаете ли вы, как организовать логические выражения в базе данных, допуская бесконечное вложение выражений?

Пример:

a = 1 AND (b = 1 OR b = 2)

Выражение в целом не должно храниться как varchar для сохранения целостности данных.

Answer 1

Вариант 1 - использовать вложенную таблицу (дерево со структурой id / parent_id), как предложил Gamecat. Это относительно дорого, и требует многократной выдачи SQL-запросов для создания эквивалента одного вложенного выражения.

Вариант 2 - использовать сериализованный объект и сохранить его в столбце varchar. Например, JSON будет хорошим выбором. Он не чувствителен к пробелам, может создаваться и анализироваться на большом количестве языков и сохраняет целостность данных.

Как только вы проанализировали строку выражения в объекте дерева в памяти, вы можете ее сериализовать и сохранить. Если бы не было необходимости манипулировать выражением на уровне базы данных, я бы пошел по этому пути.

Answer 2

Выражение является древовидной структурой. Поэтому вам нужен способ представить дерево в таблице.

Например, вы можете использовать поля:

• ID
• TypeExpression (и, или т. Д.)
• FirstChildID
• SecondChildID

В этом случае у вас есть следующие типы:

1. И, Дети указывают на другое выражение.
2. ИЛИ, Дети указывают на другое выражение.
3. Равно, Дети указывают на другое выражение.
4. Literal, FirstChild указывает на запись в буквальной таблице.
5. VariableLookup, FirstChild указывает на запись в доступной таблице.

Но я думаю, что есть лучшие способы организовать выражение. Однажды я сделал простой оценщик выражений, который принимает строку и выдает числовой результат.

Answer 3

Я бы сохранил выражение в польской форме, в столбце varchar / text. Выражение в польской форме (операнд перед операндами, без скобок) гораздо проще проанализировать с помощью рекурсивной функции (или стека, конечно)

a = 1 И (b = 1 ИЛИ b = 2)

в польской форме показывает так:

И = a 1 ИЛИ = b 1 = b 2

Answer 4

Этот тип выражения чаще всего выражается в виде дерева (иерархии), которое, как известно, раздражает запрос в SQL.

Предположим, что a и b на данный момент являются числовыми, а литералы ('1', '2') отличаются от переменных.

Table Nodes
id
type (Variable|Literal)
name (nullable for literal)
value

Table Operators
id
name (=, AND, OR, NOT)
leftNodeId
rightNodeId

Эта структура очень гибкая, но запрос ее для извлечения сложного выражения будет "забавным" (читай это "сложный").

И вам все равно придется сначала проанализировать структуру и оценить выражение после того, как оно было реконструировано.

Answer 5

Традиционным способом моделирования булевых функций является использование двоичных диаграмм решений , особенно диаграмм двоичных решений сокращенного порядка. Возможно, вы найдете расширение для вашей СУБД, которое обеспечит хорошую поддержку концепции.

UPDATE: Кроме того, если вам не нужно запрашивать логическую логику, вы можете использовать библиотеку BDD и просто сериализовать BDD в BLOB или эквивалентный. Это лучше, чем использование поля varchar, потому что библиотека BDD обеспечит правильность данных.

Answer 6

Это будет трудно представить реляционно, потому что по своей природе оно является как иерархическим, так и полиморфным (листья вашего дерева могут быть как переменными, так и постоянными).

Answer 7

Добавление к @Gamechat ответа

Я думаю, что так должно быть

ID

TypeExpression (и, или т. Д.)

FirstChildID - Это может быть листовой узел или указатель на другую строку в той же таблице

SecondChildID - Это может быть листовой узел или указатель на другую строку в той же таблице

isFirstChildLeaf

isSecondChildLeaf