問題タブ [adjacency-list]

システムでアクセス制御リストを設計しています。その中で、以下に示すようなグループとアカウントのツリーがあります

上記のツリーでは、'すべてのユーザー''管理者''特権メンバーはグループです。上記の情報を保存するツリーを作成したいと思います。隣接リストでは、トラバーサル読み取り操作はコストがかかり、Mpttトラバーサル書き込み操作はコストがかかります。ACLの場合、何をもっと重要にするか、読み取りまたは書き込みを行います。readはよく使われると思いますが、ここで賢い人の意見を聞きたいと思います。ケーキphpaclでは、mpttを使用しています。

私は、ローカル変数を使用した再帰クエリを使用して、単純な隣接リスト内のノードのツリーを取得することで (興味がなく) 遊んでいました。

INDEXこれまでの解決策は楽しいですが、MySQL がこのクエリを最適化するために使用を拒否するのはなぜだろうか (これが私の唯一の質問です) 。MySQL は ? を使用して最も近い子を検索できませんINDEXか?

なぜMySQLがそうでないのか興味があります。実行計画を使用FORCE INDEXしても変更されません。

これはこれまでのクエリ5で、親ノードの ID です。

SQLfiddle で実際の例を試す

FORCE INDEX (id)orFORCE INDEX (parent_id)またはFORCE INDEX (id, parent_id)...を指定しても動作は変わらないため、理由は小さなデータセットではないことに注意してください。

ドキュメントは言う：

また、USE INDEX (index_list) のように機能する FORCE INDEX を使用することもできますが、テーブル スキャンは非常に高価であると想定されます。つまり、テーブル スキャンは、特定のインデックスのいずれかを使用してテーブル内の行を検索する方法がない場合にのみ使用されます。

クエリが INDEX を使用できないようにする何かがあるに違いありませんが、それが何であるかわかりません。

免責事項: SQL で階層データを格納および取得するには、さまざまな方法があることを知っています。ネストされたセットモデルについて知っています。私は代替の実装を探していません。入れ子になったセットを探しているわけではありません。

また、クエリ自体がおかしく、間違った結果を生成することも知っています。

INDEXこの場合、MySQL が を使用しない理由を (詳細に) 理解したいだけです。

私はこの質問をさまざまな方法で行ってきました。

隣接リストがある場合、順序は重要ですか？隣接リスト{1、2、5}が{2、1、5}と同等であるとしましょう。または、順序は何かを意味するので、これら2つのリストは同等ではありませんか？

グラフが方向付けられており、順序が隣接するノードの配置と時計回りに関係していることを示している場合にのみ問題になるなど、いくつかの回答を受け取りました。私はまた、それは問題ではないという意見を与えられましたが、彼はインターネットの注文方法（ページランク付けアルゴリズム）などの重み（使用されている場合）に関して注文することを望んでいます。私は要点を伝えたと思いますが、これらの応答のいずれかを正確に言い換えるとは思いません。どんな考えでもありがたいです。

また、私は質問を洗練して、答えられた場合、私が求めている正確な答えを私に与えると思います：

有向グラフの隣接行列があるとします。

0 0 1 0

0 0 1 1

1 1 0 1

0 1 1 0

同等の隣接リストは次のとおりであると言われ、私の先生は、特に最後のリストに見られるように、任意の並べ替えではなく、意図的にこのようにリストしたと思います。

{2}

{2、3}

{0、1、3}

{2、1}

最後のリストは{2、1}です！同等の隣接行列で、{1、2}ではなく{1、1}である必要があることを警告するものは何ですか？

ソース (頂点)、ターゲット (頂点)、重みを格納する Edge クラスがあります。

名前、x 座標、y 座標、および Edge[]隣接リストを格納する Vertex クラスがあります。

エッジと頂点の 2 つの ArrayList を格納する Graph クラスもあります。

現在、頂点/ノードとエッジがプロットされると、頂点とエッジのリストにそれぞれ自動的に追加されます。

これら 2 つの配列リストを使用して Edge[]隣接リストを埋めたいと思いますが、これを行う方法がわかりません。誰かが私にポインタやコードがどのように見えるかの概要を教えてくれれば幸いです.

ありがとうございました。

ノードのIDを指定して、隣接リストテーブルで、関連付けられているルートノードを見つけるにはどうすればよいですか？

ノート：

テーブルには複数のツリーが含まれているため、nullのparentIdを単純に検索することはできません。

さらに詳しい情報：

これは私が現在持っているものです、これに対する問題や改善はありますか？

私は現在、最終年度のプロジェクトのグラフで最大クリークを見つけるためのアプリケーションの開発に取り組んでいます。私はほとんどのプロジェクトを完了し、アプリケーションのテストを開始したばかりです。

アプリケーションは現在、隣接リストを入力として使用していますが、誰かが隣接リストのランダムジェネレーターを知っているかどうか疑問に思っていたので、アプリケーションをテストできますか？

どうもありがとう

このデータ構造モデルを使用するカテゴリにテーブルがあります。また、カテゴリのブランチのパスを示す別のテーブルを使用します。

私が欲しいのは、任意のアイテムの親のリストを取得することです。たとえば、「dog」を検索すると「dog、mascot」が表示され、「doberman」を検索すると「doberman、dog、mascot」が表示されます。

私はこれを試しました...しかしそれは逆です、私は両親が葉を手に入れるのを探すことを意味します：

そして明らかに得る：

しかし、私は「ドーベルマン」から入手したい：

葉っぱから相談することはできますか？

私たちはmysqlを使用しています。Adjacency List モデル テーブルがあるとします。（正規化されていないことはわかっています。）たとえば、次のようなフィールドを持つ人事テーブル：

何人かのユーザーがいるテーブルもあります。例えば、

給与情報は機密情報であるとします。そのため、一部のユーザーは特定の支店の給与情報を見ることができます。

たとえば、ロール b1 は、boss1 以下のすべての給与を表示/編集できます。ロール b2 は、boss2 以下のすべての給与を表示/編集できます。ロール sd は、slvdrvr1 および slvdrvr2 以降のすべての給与を表示/編集できます。したがって、これを実装するには、ユーザーと個人の権限テーブルをセットアップする必要があります。

Personnel テーブルは、何万行もある大規模なものです。

私の質問は、簡単に維持およびクエリできるアクセス許可テーブルをどのようにセットアップするかということです。

たとえば、オプション 1: 各個人のロール権限を設定できます。ただし、許可テーブルは巨大になります。

オプション 2: 親ノードのみにロール権限を設定できます。ただし、ユーザーが特定の量のレコードを表示するたびに、設定がある場所まで各レコードのアクセス許可を探す必要があります。

ユーザー数は約数百人。ロールの数が 100 未満です。

不明な点があれば質問してください。前もって感謝します。

エッジのリストから行列を作成するコードを書いています。

ただし、上記のコードを実行すると、入力データにない「ファントムエッジ」が発生し、プログラムの残りの部分が台無しになります。エッジは、マトリックスでは9,2、要素コード形式では8,1です。

マトリックス内のすべての要素は、事前に0に初期化されます。

マトリックスに関連する入力データは次のとおりです。

入力を処理する関数は次のとおりです。

*入力データではなく、存在してはならないエントリ

私には2つのエンティティがpostあり、categoryどちらが1:n関係です。

2つの列を持つ参照テーブルがありますpost_id。category_id

categoriesテーブルには、id列、status列、および列がありparent_idます

カテゴリが別のカテゴリ（n-depth）の子である場合、それparent_idはnullではありません。

カテゴリがオンラインの場合、ステータスは1です。それ以外の場合は、0です。

私がする必要があるのは、投稿が表示されているかどうかを確認することです。

これには以下が必要です。

投稿に参加したForeachカテゴリは、ルートノードまでのツリーをトレースします（カテゴリがparent_id==になるまでnull）。これらのカテゴリのいずれかがstatus0の場合、そのパスはオフラインと見なされます。

いずれかのパスがオンラインの場合、投稿は表示されていると見なされ、そうでない場合は非表示になります。

これを（半擬似コードとして）行うことを考えることができる唯一の方法は次のとおりです。

しかし、それは多くのSQLクエリになる可能性がありますが、より良い方法はありますか？