SQLの階層的なタグ付け

StackOverflow https://stackoverflow.com/questions/256997

質問

オブジェクトのタグ付けにMySQLデータベースを使用するPHP Webアプリケーションがあり、このSOの質問。

各タグに一意の親タグを持たせることができるタグ階層を実装したいと思います。親タグTの検索は、Tのすべての子孫に一致します（つまり、T、親がT（Tの子）、Tの孫などのタグ）。

これを行う最も簡単な方法は、タグの親タグのID、またはタグに親がない場合はマジック番号を含むParentIDフィールドをタグテーブルに追加することです。ただし、子孫の検索では、データベースの全検索を繰り返して各「世代」のタグを見つける必要があります。これは避けたいと思います。

（おそらく）より高速ですが、これを行うための正規化されていない方法は、各タグのすべての子、または各タグのすべての子孫を含むテーブルを持つことです。ただし、これにより、データベース内のデータに一貫性がないというリスクが発生します（タグが複数の親の子であるなど）。

可能な限り正規化されたデータを維持しながら、子孫を高速に検索するクエリを作成する良い方法はありますか？

役に立ちましたか？

解決 2

Aliの答えには、 Joe CelkoのSQL for Smartiesのツリーと階層へのリンクがあります。 、これは私の疑念を裏付けています-すべての世界で最高のものを提供する単純なデータベース構造はありません。私の目的に最適なのは「頻繁な挿入ツリー」です。この本は、「ネストされたセットモデル」のようなものです。アリのリンクの、しかし、連続していないインデックス付けで。これにより、O（1）挿入（ a la 非構造化BASIC行番号付け）が可能になり、必要に応じて時折インデックスが再編成されます。

他のヒント

2つの列を使用して実装しました。異なる言語にローカライズする必要があるため、タグ名を別のフィールド/テーブルに保持する必要があるため、ここで少し簡略化します。

  • タグ
  • パス

たとえば、これらの行を見てください：

tag            path
---            ----
database       database/
mysql          database/mysql/
mysql4         database/mysql/mysql4/
mysql4-1       database/mysql/mysql4-1/
oracle         database/oracle/
sqlserver      database/sqlserver/
sqlserver2005  database/sqlserver/sqlserver2005/
sqlserver2005  database/sqlserver/sqlserver2008/

etc。

パスフィールドで like 演算子を使用すると、必要なすべてのタグ行を簡単に取得できます。

SELECT * FROM tags WHERE path LIKE 'database/%'

階層内のノードを移動する場合、すべての子も変更する必要があるなど、実装の詳細がいくつかありますが、難しくはありません。

また、パスの長さが十分に長いことを確認してください-私の場合、パスのタグ名ではなく、長すぎるパスを取得しないように別のフィールドを使用しました。

Kimballが階層ヘルパーテーブルと呼ぶものを構築できます。

Say you階層は次のようになります：A-＆gt; B | B-＆gt; C | C-＆gt; D

このようなテーブルにレコードを挿入します

ParentID, ChildID, Depth, Highest Flag, Lowest Flag
A, A, 0, Y, N
A, B, 1, N, N
A, C, 2, N, N
A, D, 3, N, Y
B, B, 0, N, N
B, C, 1, N, N
B, D, 2, N, Y
C, C, 0, N, N
C, D, 1, N, Y
D, D, 0. N, Y

私はそれが正しいと思います...とにかく。ポイントは、階層を正しく保存することです。適切なテーブルからこのテーブルを作成するだけです。このテーブルは、Bansheeのようなクエリです。 Bの下のすべての最初のレベルが何であるかを知りたいとします。

WHERE parentID = 'B' and Depth = 1

子タグを格納するためにある種の配列を使用します。これは、それ自体でテーブルを結合するよりもはるかに高速である必要があります（特に多数のタグがある場合）。見てみると、mysqlにネイティブ配列データ型があるかどうかわかりませんが、テキスト列を使用してシリアル化された配列を格納することでこれをエミュレートできます。さらに高速化する場合は、その列にテキスト検索インデックスを配置して、関連するタグを見つけることができるはずです。

[編集] Aliの記事を読んだ後、さらに狩りをして、このプレゼンテーションをたくさん見つけましたpostgresで階層を実装するためのアプローチ。それでも説明目的に役立つ場合があります。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top