0

したがって、このプロジェクトは既存のコードベースを拡張しており、MySQLデータベース上に構築されています。タプルが建物内の場所を表すテーブルがあり、パスファインディング用のグラフでこれらの場所を接続するエッジを表すテーブルを作成しています。これは単純な2列のテーブルであり、各列はロケーションテーブルを参照する外部キーであるIDを保持しています。要約すると、状況は次のようになります。

CREATE TABLE node (
    ID int(10) AUTO_INCREMENT NOT NULL,
    (...)
    PRIMARY KEY(ID)
);

CREATE TABLE edge(
    ID_1 int(10),
    ID_2 int(10),
    FOREIGN KEY (ID_1) REFERENCES node(ID),
    FOREIGN KEY (ID_2) REFERENCES node(ID)
);

グラフが対称であるという既存の仮定です。つまり、ノードAがノードBに対してエッジを持っている場合、ノードBはノードAに対してエッジを持っている必要があります。一方通行のドアの場合はここでは無視されますが、私の場合は当てはまらないようです。ドメイン。そのため、ノードAとBが接続されている場合、それらの接続は次の3つの方法のいずれかでエッジテーブルに格納できます。

{(A,B)}
{(B,A)}
{(A,B),(B,A)}

この表を使用して答える質問は、「このノードを考えると、その隣接ノードは何ですか？」です。そして現在、私のアプリケーションは次のようなクエリを使用してそれを行います。

SELECT * FROM node
WHERE ID IN(
    SELECT ID_2
    FROM edge
    WHERE ID_1=?
    UNION
    SELECT ID_1
    FROM edge
    WHERE ID_2=?
);

ただし、私の本能は、CHECK制約を使用して、MySQLがサポートしていないと思われる後者の構造のみを格納できるようにすることでした。その答えから、そのような制約をエミュレートするには、すべてのエッジを両方の順序で格納するすべての操作のトリガーを作成する必要があります。利点は、当然のことながらパフォーマンスが向上し、質問に答えることができることです。

SELECT * FROM node
WHERE ID IN(
    SELECT ID_2
    FROM edge
    WHERE ID_1=?
);

CHECKをエミュレートするトリガーについて読んだら、友人と話し合いました。彼は、再帰ストレージを確保するのは無駄であり（ストレージの使用量が2倍になる）、データベースを正しく処理するためにアプリケーションに任せる必要があると提案しました。今、私は実際に最善の解決策が何であるかが少しわかりません-データベースはトリガーを使用して挿入と削除を2倍にすることによって再帰性を確保する必要がありますか、それともアプリケーションは再帰的に保存されていないデータを読み取り続けて、そのように見えるようにする必要がありますか？データベースが同じデータを複数の方法で表現できるようにすると、少し心配になります。それは無理ですか？UNIONとそのようなものは、かなりのパフォーマンスヒットになりますか？

（適度に小さなサイトを対象としているため、このシステムは数万のノードを超える可能性は低く、通常のノードには最大6つのエッジがあります）。

4

1 に答える 1

0

実際には、各接続を1つと見なすこともできます（必要に応じてブロックすることができます）。部屋の間に複数の接続がある場合はどうなりますか？同じロビーに2つの別々のドアがある部屋のように？

とにかく、それらはすべて遊ぶのにいいビットです...

個人的には方向に基づいて各接続を保存するので、aとbの間に2方向のドアが1つある場合は、そのように保存します。

tbl_connections

current_room_id edge      connecting_room_id
1               north     2
2               south     1
1               east      3
1               west      4
4               east      1
1               south     5

はい、そのデータが利用できる場合は、どのエッジが接続であるかを含めます。後でデータを含めることを決定したときに役立つでしょう。...（上記の構造では、1から3に変更できますが、3から1に変更することはできません）。

次のように保存すると、次を使用して部屋の隣人（および方向）を簡単に取得できます。

SELECT connecting_room, edge
FROM tbl_connections
WHERE current_room_id = 1;

これはあなたに与えるはずです：

2, north
3, east
4, west
5, south

また、現在の部屋と、このスキーマで通過する予定のエッジに基づいてパスをマップすることもできます。

あなたが言うように再帰データを保存することはかなり一般的な解決策であり、この場合、私はそれが正しい方法だと思います。

于 2012-08-02T14:26:58.813 に答える