データベーススキーマでハッシュテーブルコレクションをどのように表現しますか？

https://stackoverflow.com/questions/449202

19-08-2019
|

質問

データベーススキーマにドメインオブジェクトを作成しようとしており、コード内でドメインオブジェクトにハッシュテーブル/リストメンバーがある場合：

public class SpaceQuadrant : PersistentObject
{

    public SpaceQuadrant()
    {
    }

    public virtual Dictionary<SpaceCoordinate, SpaceObject> Space
    {
        get;
        set;
    }
}

ディクショナリは、オブジェクトキーを値キーにマッピングするハッシュテーブル/リストです。さまざまな結合テーブルを作成したり、ロードテクニックを作成したりするための複数の方法を考え出しましたが、O （1）ハッシュテーブルで取得するアクセス時間。

データベーススキーマでSpaceQuadrant、SpaceCoordinate、およびSpaceオブジェクトをどのように表現しますか？簡単なスキーマコードの説明がいいでしょう。すなわち。

table SpaceQuadrant
{
    ID int not null primary key,
    EntryName varchar(255) not null,
    SpaceQuadrantJoinTableId int not null
                 foreign key references ...anothertable...
}

でも、考えがあればいいと思います、読んでくれてありがとう！

詳細情報：

すばらしい回答をありがとう、すでに、私はそれらをざっと読んだだけであり、応答する前にそれぞれについて考える時間をとりたいです。

これらのクラスを定義するより良い方法があると思われる場合は、ぜひ例を挙げてください。あなたが使いやすい言語はどれでもクールです

解決

まず、多くのデータベースに位置情報データの専用サポートが存在します-異なるアルゴリズムを使用できます（たとえば、Bツリーの空間バージョンが存在します）。おそらく、近接検索のサポートが存在します。

SpaceQuadrantごとに異なるハッシュテーブルがあるため、次のようなものが必要になります（S.Lottの投稿から編集）：

table Space {
    SpaceCoordinate,
    Quadrant Foreign Key SpaceQuadrant(ID),
    SpaceObject -- whatever the object is (by ID)
    Primary Key(SpaceCoordinate, Quadrant)
}

これは(SpaceCoordinate, Quadrant) -> SpaceObjectId辞書です。

=====

今、O（1）のパフォーマンスの懸念について、間違って対処されている理由はたくさんあります。

誰かがあなたに言ったように、多くのDBでメモリベースのテーブルのハッシュインデックスを使用できます。ただし、永続的なストレージが必要な場合は、1つではなく2つのテーブル（メモリ1つと永続的なテーブル）を更新する必要があります（これに対する組み込みのサポートがない場合）。それが価値があるかどうかを知るには、実際のデータ（実際のデータサイズ）でベンチマークを行う必要があります。

また、テーブルをメモリに強制すると、より悪い意味を持つ可能性があります。

何かが交換されたとしても、あなたは死んでいます-Bツリー（つまり、通常のディスクベースのインデックス）を使用した場合、そのアルゴリズムは必要なI / Oを最小化したでしょう。それ以外の場合、すべてのDBMSはハッシュテーブルを使用し、Bツリーではなくスワッピングに依存します。メモリに収まるかどうかを予測することはできますが、...

さらに、BツリーはO（1）ではなく、O（log_512（N））、またはそのようなものです（O（log N）に崩壊することは知っていますが、これについては私に責任があります）。 4になるには（2 ^ 9）^ 4 = 2 ^ 36 = 64GiBが必要になります。大量のデータがある場合は、とにかくメモリに収まるように大きな鉄のサーバーが必要になります。そのため、ほぼO（1）であり、一定の要因が実際に重要なものです。
低漸近的複雑性、大きな定数係数のアルゴリズムについて聞いたことがありますか？これは、非実用的なデータサイズで単純なアルゴリズムよりも高速になりますか？

最後に、DB著者は私やあなたよりも賢いと思います。特にSQLの宣言的な性質を考えると、このように手動で最適化することは意味がありません。インデックスがメモリに収まる場合、価値があれば、必要に応じてディスクインデックスのハッシュテーブルバージョンを構築して使用することを選択できると思います。そのためのドキュメントを調査してください。

しかし、最終的な最適化は、特にこの種の場合（標準のSQL最適化とは対照的に独自に考えている奇妙な最適化）、宣言型言語では、時期尚早な最適化が悪であるということです。

他のヒント

リレーションはハッシュテーブルではありません。セットです。

座標をキーとして使用してデータベースを整理しません。オブジェクトの場所が変わったらどうなりますか？代わりに、おそらくオブジェクトの属性として座標を扱います。

また、固定された次元数、たとえば3次元があると仮定します。その場合、オブジェクトのこれらの属性を固定列に保存できます。

CREATE TABLE SpaceQuadrant (
  quadrant_id INT NOT NULL PRIMARY KEY,
  quadrant_name VARCHAR(20)
  -- other attributes
);

CREATE TABLE SpaceObject (
  object_id INT NOT NULL PRIMARY KEY,
  x NUMERIC(9,2) NOT NULL,
  y NUMERIC(9,2) NOT NULL
  z NUMERIC(9,2) NOT NULL,
  object_name VARCHAR(20) NOT NULL,
  -- other attributes
  quadrant_id INT NOT NULL,
  FOREIGN KEY (quadrant_id) REFERENCES SpaceQuadrant(quadrant_id)
);

オブジェクト指向クラスでは、オブジェクトが辞書にある理由は明確ではありません。 O（1）の時間でそれらにアクセスすることに言及していますが、なぜ座標によってそれを行うのですか？

特定のポイント（たとえば、プレイヤーの宇宙船）の近くにあるオブジェクトの検索を最適化するためにそれを使用している場合、このSpaceQuadrantに入力するSQLクエリに、その特定のポイントからのすべてのオブジェクトの距離の計算を組み込むこともできます、結果を距離で並べ替えます。

これらの提案が関連するかどうかを知るには、プログラムについて十分に知りません。しかし、少なくともデータを整理するさまざまな方法を考えさせているのでしょうか？

最も単純な場合、ディクショナリにはテーブルの主キーにマップするキーがあります。そのため、キーの値を指定すると、単純なルックアップを介して一致するデータをすぐに見つけることができます。

この場合、スペース象限を説明または特徴付ける一般的な（単一値の）属性を持つテーブルSpaceQuadrantが必要です。 SpaceQuadrantテーブルには、主キー、場合によっては生成されたID、場合によっては自然値が含まれます。ハッシュテーブルは、SpaceQuadrantを相互参照するための主キー値、位置（SpaceCoordinate）、および象限と座標の属性を持つテーブルで構成されます。

現在、拡張可能なDBMSがある場合、SpaceCoordinateのユーザー定義型を定義できます。それに失敗すると、列（x、y、zまたはr、シータ、ローなど）のトリオを使用して位置（SpaceCoordinate）を表すことができます。

一般的に言えば、私が説明している構造は、ビル・カーウィンのものと非常に似ています。キー（私がメッセージを再読するまで意図されていません）の違いは、それが整理するための最良の方法であると確信している場合、下位テーブルの主キーの一部として位置を持つことは私の本で完全にOKですそれ。代替候補キーであるオブジェクトID列がある場合もあります。また、オブジェクトがスペース象限から独立して存在している場合、それらはその瞬間に存在します（または、複数の位置に存在する可能性があります-ポイントではなく、宇宙ステーションまたは何かであるため）、SpaceObjectは別のテーブル。何が最善かは、入手できない情報に依存します。

主キーの一部としてSpaceCoordinateを使用する場合の制限に注意する必要があります。

2つのオブジェクトが同じ位置を占有することはできません（これは、ハッシュテーブルおよび3D空間での衝突と呼ばれます）。
位置が変更された場合、キーデータを更新する必要があります。これは、非キーデータを更新するよりもコストがかかります
近接検索は困難です-正確な検索は簡単です。

メモリ内の辞書についても同様です。座標を変更する場合は、古い場所からレコードを削除して、辞書の新しい場所に配置する必要があります（または、言語が舞台裏でそれを行う必要があります）。

辞書はテーブルです。ハッシュは、どのような種類のインデックスが使用されるかという問題です。ほとんどのRDBMSは、テーブルが大きく密集していると想定しているため、ハッシュインデックスは適切ではありません。

table SpaceQuadrant { 
    ID Primary Key,
    -- whatever other attributes are relevant
}

table Space {
    SpaceCoordinate Primary Key,
    Quadrant Foreign Key SpaceQuadrant(ID),
    SpaceObject -- whatever the object is
}

スペースオブジェクトには、それらが配置されている象限へのFK参照があります。

RDBMSによっては、期待するパフォーマンスを得るためのハッシュベースのインデックスを見つけることができる場合があります。たとえば、HEAPストレージエンジンを使用するMySQLは、HASHインデックスをサポートしています。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow