リレーショナル データベースでの順序を表現する
https://stackoverflow.com/questions/21388
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
データベース内にオブジェクトのコレクションがあります。フォトギャラリーの画像、カタログの製品、本の章など。各オブジェクトは行として表されます。これらの画像を任意に並べ替えて、その順序をデータベースに保存して、オブジェクトを表示するときに正しい順序になるようにしたいと考えています。
たとえば、私が本を書いていて、各章がオブジェクトであるとします。私は本を執筆し、章を次の順序で配置します。
概要、アクセシビリティ、フォーム vs.機能、エラー、一貫性、結論、インデックス
これはエディターに送られ、次の推奨順序で返されます。
はじめに、形式、機能、アクセシビリティ、一貫性、エラー、結論、索引
この順序を堅牢かつ効率的な方法でデータベースに保存するにはどうすればよいでしょうか?
次のようなアイデアがありましたが、どれも気に入りませんでした。
配列。各行には順序付け ID があり、順序が変更されると (削除とその後の挿入によって)、順序 ID が更新されます。これにより、検索が簡単になります。
ORDER BY, でも壊れやすそうです。// REMOVAL
UPDATE ... SET orderingID=NULL WHERE orderingID=removedID
UPDATE ... SET orderingID=orderingID-1 WHERE orderingID > removedID
// INSERTION
UPDATE ... SET orderingID=orderingID+1 WHERE orderingID > insertionID
UPDATE ... SET orderID=insertionID WHERE ID=addedIDリンクされたリスト。各行には、順序付けされた次の行の ID を表す列があります。ここではトラバーサルにコストがかかるように見えますが、何らかの方法で使用できる可能性があります
ORDER BYそれは私が考えていないことです。間隔をあけた配列。orderID (#1 で使用したもの) を大きく設定して、最初のオブジェクトが 100、2 番目のオブジェクトが 200 になるようにします。挿入が発生したら、それを次の場所に配置するだけです。
(objectBefore + objectAfter)/2. 。もちろん、これは時々再バランスする必要があるため、互いに近づきすぎないようにする必要があります (浮動小数点を使用しても、最終的には丸め誤差が発生します)。
私にはどれも特にエレガントとは思えません。誰かがそれを行うより良い方法を持っていますか？
解決 9
私は主に Django でこれに遭遇したので、次のことがわかりました。 この解決策 最も働きやすいものになるように。リレーショナル データベースでこれを行う「正しい方法」はないようです。
他のヒント
他の代替方法は、(RDBMS がサポートしている場合) 配列型の列を使用することです。これは正規化ルールに違反しますが、このような状況では役立つ可能性があります。私が知っている配列を持つデータベースの 1 つは PostgreSQL です。
Rails の act_as_list ミックスインは、基本的に #1 で説明した方法でこれを処理します。これは、position と呼ばれる INTEGER 列 (もちろん名前にオーバーライドできます) を検索し、それを使用して ORDER BY を実行します。順序を変更したい場合は、位置を更新します。使用するたびにうまく機能してきました。
余談ですが、スパース番号付けを使用することで、INSERTS/DELETES で常に位置を変更する必要をなくすことができます。これは、昔の基本的な方法のようなものです...ポジションに 10、20、30 などの番号を付けることができます。10 と 20 の間に何かを挿入する必要がある場合は、15 の位置に挿入するだけです。同様に、削除する場合も行を削除してギャップを残すことができます。番号を再設定する必要があるのは、実際に順序を変更する場合、または挿入を実行しようとして挿入する適切なギャップがない場合のみです。
もちろん、特定の状況に応じて（例：他の行がすでにメモリにロードされているかどうかに関係なく、ギャップアプローチを使用することが意味がある場合とそうでない場合があります。
検討しただけの考え オプション #1 対 #3:間隔をあけた配列オプション (#3) は、通常の配列 (#1) の問題を先送りするだけではありませんか?どのアルゴリズムを選択するにせよ、それが壊れていて後で #3 で問題に遭遇するか、機能していて #1 も同様に機能するかのどちらかです。
オブジェクトが他のテーブルによって高度にキー設定されておらず、リストが短い場合は、ドメイン内のすべてを削除して、正しいリストを再挿入するのが最も簡単です。ただし、リストが大きく、削除を遅くするための制約がたくさんある場合、これは現実的ではありません。最初の方法が本当に最もクリーンだと思います。トランザクションで実行すると、更新の途中で注文を台無しにするような奇妙なことが何も起こらないことを確認できます。
前回のプロジェクトでこれを実行しましたが、それは特別に注文する必要が時々しかなく、あまり頻繁にアクセスされないテーブル用でした。平均的な場合、1 つの値の変更と 2 つの値のクエリだけで順序変更が最も安価になるため、間隔をあけた配列が最良の選択肢であると思います。
また、ORDER BY はデータベース ベンダーによってかなり高度に最適化されると思います。そのため、その機能を活用すると、リンク リストの実装よりもパフォーマンスの面で有利になるでしょう。
浮動小数点数を使用して各項目の位置を表します。
項目 1 -> 0.0
アイテム 2 -> 1.0
アイテム 3 -> 2.0
項目 4 -> 3.0
単純な二等分によって、他の 2 つの項目の間に任意の項目を配置できます。
項目 1 -> 0.0
項目 4 -> 0.5
アイテム 2 -> 1.0
アイテム 3 -> 2.0
(項目 4 を項目 1 と 2 の間に移動しました)。
浮動小数点数がコンピュータ システムでエンコードされる方法により、二等分プロセスはほぼ無限に継続する可能性があります。
項目 4 -> 0.5
項目 1 -> 0.75
アイテム 2 -> 1.0
アイテム 3 -> 2.0
(項目 1 を項目 4 の直後に移動)
私なら、テーブルに優先順位がすでに存在する場合に「スペースを空ける」トリガーを付けて、連続した番号を付けます。
私もこの問題を抱えていました。私は時間のプレッシャーが大きかったので (誰もがそうでしょう)、オプション #1 を選択し、変更された行のみを更新しました。
品目 1 を品目 10 と交換する場合は、2 回の更新を行うだけで、品目 1 と品目 10 の注文番号が更新されます。アルゴリズム的には単純で、最悪のケースは O(n) であることはわかっていますが、その最悪のケースはリストの全順列がある場合です。それはどれくらいの頻度で起こるのでしょうか？それはあなたが答えることです。
私も同じ問題を抱えており、適切なデータ モデリングについておそらく少なくとも 1 週間は悩みましたが、ようやく理解できたと思います。PostgreSQL で配列データ型を使用すると、注文された各商品の主キーを保存し、注文が変更されたときに挿入または削除を使用してその配列を更新できます。単一行を参照すると、配列列の順序に基づいてすべてのオブジェクトをマップできます。
まだ少し不安定な解決策ですが、オプション 1 では順序変更時に他のすべての行の順序番号を更新する必要があるため、オプション 1 よりもうまく機能する可能性があります。
スキーム #1 とスキーム #3 は、すべての操作で同じ複雑さを持ちます。 INSERT と書いています。スキーム #1 には O(n) 件の書き込みがあります INSERT スキーム #3 には O(1) 件の書き込みがあります INSERT.
他のすべてのデータベース操作の複雑さは同じです。
スキーム #2 は考慮すべきではありません。 DELETE O(n) 回の読み取りと書き込みが必要です。スキーム #1 とスキーム #3 には O(1) があります DELETE 読み取りと書き込みの両方に対応します。
新しい方法
要素に別個の親要素がある場合 (つまり、外部キー行を共有している場合）、次のことを試すことができます...
Django は、整数のリストをデータベースに保存するためのデータベースに依存しないソリューションを提供します。 CharField(). 。欠点の 1 つは、保存される文字列の最大長が次の値を超えることはできないことです。 max_length, 、これは DB に依存します。
複雑さの観点から見ると、スキーム #1 では O(1) の書き込みが行われます。 INSERT, これは、順序情報が親要素の行に単一のフィールドとして保存されるためです。
もう一つの欠点は、 JOIN 順序を更新するには、親行へのアクセスが必要になりました。
