database-design - ブール式のデータモデル

Question

式の無限のネストを許可しながら、データベースでブール式を編成する方法を知っていますか?

例：

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

データの整合性を維持するために、式全体を varchar として保存しないでください。

score 15 · Accepted Answer

オプション 1 は、Gamecat が提案したように、ネストされたテーブル (id / parent_id 構造を持つツリー) を使用することです。これを行うには比較的コストがかかり、単一のネストされた式と同等のものを構築するには、SQL クエリを繰り返し発行する必要があります。

オプション 2 は、シリアル化されたオブジェクトを使用し、それを varchar 列に格納することです。たとえば、JSON が適しています。空白に敏感ではなく、膨大な数の言語で作成および解析でき、データの整合性を保持します。

式の文字列をメモリ内のツリーオブジェクトに解析したら、すぐにそれをシリアル化して格納できます。データベースレベルで式を操作する必要がない場合は、そのルートに進むと思います。

score 9 · Accepted Answer

式は木のような構造です。したがって、ツリーをテーブルに表示する方法が必要です。

たとえば、次のフィールドを使用できます。

この場合、次のタイプがあります。

しかし、表現を整理するためのより良い方法があると思います。私はかつて、文字列を受け入れて数値結果を生成する単純な式評価器を作成しました。

score 3 · Accepted Answer

このタイプの式は、ほとんどの場合、ツリー（階層）として表現されます。これは、SQLでのクエリが煩わしいことで有名です。

とは今のところ数値であり、リテラル（ '1'、 '2'）は変数とは区別されるaと仮定します。b

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

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

この構造は非常に柔軟性がありますが、複雑な式を取得するためにクエリを実行すると、「楽しい」（「やりがいのある」と読む）ことができます。

また、最初に構造を解析し、式が再構築された後に式を評価する必要があります。

score 3 · Accepted Answer

式を洗練された形式で、varchar/text 列に格納します。洗練された形式 (オペランドの前にオペランドがあり、ブラケットがない) の式は、再帰関数 (またはもちろんスタック) を使用して解析する方がはるかに簡単です。

a = 1 かつ (b = 1 または b = 2)

ポーランド語では、次のように表示されます。

AND = a 1 OR = b 1 = b 2

score 2 · Accepted Answer

これは、その性質上、階層的で多態的であるため、リレーショナルに表現するのは困難です (ツリーの葉は変数または定数のいずれかになります)。

score 2 · Accepted Answer

ブール関数をモデル化する従来の方法は、二分決定図、特に低次数二分決定図を使用することです。この概念を適切にサポートする DBMS の拡張機能を見つけることができる可能性があります。

更新: または、ブール論理を照会する必要がない場合は、BDD ライブラリを使用して、BDD をBLOBまたは同等のものにシリアル化することができます。varcharBDD ライブラリはデータが有効であることを保証するため、フィールドを使用するよりも優れています。

score 0 · Accepted Answer

@Gamechat の回答に追加

こうあるべきだと思う

ID

TypeExpression (および、またはなど...)

FirstChildID -- これは、リーフノードまたは同じテーブル内の別の行へのポインタです。

SecondChildID -- これは、リーフノードまたは同じテーブル内の別の行へのポインタです。

isFirstChildLeaf

isSecondChildLeaf

database-design - ブール式のデータ モデル