database design - que - Modelo de datos para expresiones booleanas

mongodb español

Question

¿Conoce una forma de organizar expresiones booleanas en una base de datos al tiempo que permite el anidamiento infinito de las expresiones?

Ejemplo:

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

La expresión como un todo no se debe almacenar como varchar para preservar la integridad de los datos.

Answer 1

Este tipo de expresión generalmente se expresa como un árbol (una jerarquía), que son notoriamente molestos para consultar en SQL.

Supondremos que a y b son numéricos por el momento y que los literales (''1'', ''2'') se distinguen de las variables.

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

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

Esta estructura es muy flexible, pero consultarla para recuperar una expresión compleja va a ser "divertida" (léase "desafiante").

Y todavía tiene que analizar la estructura para comenzar y evaluar la expresión después de que haya sido reconstruida.

Answer 2

Esto será difícil de representar relacionalmente, porque por su naturaleza es tanto jerárquico como polimórfico (las hojas de tu árbol pueden ser variables o constantes).

Answer 3

La forma tradicional de modelar las funciones booleanas es usar diagramas de decisión binarios , especialmente diagramas de decisión binarios de orden reducida. Es posible que pueda encontrar una extensión para su DBMS que brinde un buen soporte para el concepto.

ACTUALIZACIÓN: Alternativamente, si no necesita consultar en la lógica booleana, puede usar una biblioteca BDD y simplemente serializar el BDD en un BLOB o equivalente. Es mejor utilizar un campo varchar porque la biblioteca BDD aseguraría que los datos fueran válidos.

Answer 4

La opción 1 sería utilizar una tabla anidada (un árbol con estructura id / parent_id), como se sugirió Gamecat. Esto es relativamente costoso de hacer, y requiere emitir consultas SQL repetitivamente para construir el equivalente de una sola expresión anidada.

La opción 2 sería usar un objeto serializado y almacenarlo en una columna varchar. Por ejemplo, JSON sería una buena opción. No es sensible al espacio en blanco, se puede crear y analizar en una gran cantidad de idiomas y conserva la integridad de los datos.

Tan pronto como haya analizado la cadena de expresiones en un objeto de árbol en la memoria, puede serializarlo y almacenarlo. Si no hubiera necesidad de manipular la expresión en el nivel de la base de datos, creo que iría por esa ruta.

Answer 5

Una expresión es una estructura arborescente. Entonces necesitas una manera de presentar el árbol en una tabla.

Puede, por ejemplo, usar los campos:

• CARNÉ DE IDENTIDAD
• TypeExpression (y, o etc ...)
• FirstChildID
• SecondChildID

En este caso, tiene los siguientes tipos:

1. Y, los niños apuntan a otra expresión.
2. O bien, los niños apuntan a otra expresión.
3. Igual, los niños apuntan a otra expresión.
4. Literal, FirstChild apunta a una entrada en una tabla literal.
5. VariableLookup, FirstChild apunta a una entrada en una tabla que se puede usar.

Pero creo que hay mejores formas de organizar la expresión. Una vez hice un evaluador de expresiones simples que acepta una cadena y produce un resultado numérico.

Answer 6

Agregando a @Gamechat respuesta

Creo que debería ser así

CARNÉ DE IDENTIDAD

TypeExpression (y, o etc ...)

FirstChildID: puede ser un nodo hoja o un puntero a otra fila en la misma tabla

SecondChildID: puede ser un nodo hoja o un puntero a otra fila en la misma tabla

isFirstChildLeaf

isSecondChildLeaf

Answer 7

Guardaría la expresión en forma de pulido, en una columna varchar / text. Una expresión en forma pulida (operando antes de operandos, sin corchetes) es mucho más fácil de analizar con una función recursiva (o una pila de curso).

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

en forma polaca se muestra así:

AND = a 1 OR = b 1 = b 2