「順番から検索」が可能なデータ構造

Question

この問題に対してどのようなデータ構造/ストレージ戦略を使用すべきかを知りたいです。

データベース内の各データ エントリは、A-B-C-D などの複数の順序付けされた項目のリストで構成されます。ここで、A、B、C、D は異なる項目です。

データベースに 3 つのエントリがあるとします。

あいうえお

E-F-G

G-H-B-A

ユーザーが順序付けされていない項目を入力した場合、一致する順序付きエントリをデータベースから見つけなければなりません。たとえば、ユーザーが A、B、G、H と入力した場合、データベースから G-H-B-A をユーザーに返したいとします。

データストレージ戦略はどうあるべきですか?

Answer 1

あなたは、そうでなければ、時間がかかるだろう命じたすべての要素の順列、上で検索する必要があります、別途注文して順不同の要素を格納オフ最高です。

これを試してください：

/* Create a table to track your items (A, B, C, etc.). It contains all possible elements */
CREATE TABLE [Items](
    [Value] [char](1) NOT NULL,
 CONSTRAINT [PK_Items] PRIMARY KEY CLUSTERED ([Value]))

/* Create a table to track their grouping and stated ordering */
CREATE TABLE [Groups](
    [ID] [int] NOT NULL,
    [Order] [text] NOT NULL,
 CONSTRAINT [PK_Groups] PRIMARY KEY CLUSTERED ([ID]))

/* Create a mapping table to associate them */
CREATE TABLE [ItemsToGroups](
    [Item] [char](1) NOT NULL,
    [Group] [int] NOT NULL
)

ALTER TABLE [ItemsToGroups]  WITH CHECK ADD CONSTRAINT [FK_ItemsToGroups_Groups] FOREIGN KEY([Group])
REFERENCES [Groups] ([ID])

ALTER TABLE [ItemsToGroups] CHECK CONSTRAINT [FK_ItemsToGroups_Groups]

ALTER TABLE [ItemsToGroups]  WITH CHECK ADD CONSTRAINT [FK_ItemsToGroups_Items] FOREIGN KEY([Item])
REFERENCES [Items] ([Value])

ALTER TABLE [ItemsToGroups] CHECK CONSTRAINT [FK_ItemsToGroups_Items]

/* Populate your tables. 
   Items should have eight rows: A, B, C,...H
   Groups should have three rows: 1:ABCD, 2:EFG, 3:GHBA
   Items to groups should have eleven rows: A:1, B:1,...A:3 */

/* You will want to pass in a table of values, so set up a table-valued parameter
   First, create a type to support your input list */
CREATE TYPE ItemList AS TABLE (e char(1) NOT NULL PRIMARY KEY)
DECLARE @Input ItemList
GO

/* Create a stored procedure for your query */
CREATE PROCEDURE SelectOrderedGroup @Input ItemList READONLY AS
    SELECT *
    FROM Groups
    WHERE Groups.ID NOT IN (
        SELECT [Group]
        FROM ItemsToGroups
        WHERE Item NOT IN (SELECT e FROM @Input)
    )
GO

/* Now when you want to query them: */
DECLARE @MyList ItemList
INSERT @MyList(e) VALUES('G'),('H'),('B'),('A')
EXEC SelectOrderedGroup @MyList

は、上記の3を返します。GHBA、あなたが望むように。あなたはDCBAに合格した場合、あなたは戻って1取得します：ABCDを、あなたが探している再びよいます。あなたがCに渡すと何のグループはちょうどC.で構成されていないとして、あなたは、何を取り戻すんよ。

あなたはおそらくテーブル値パラメータを使用したいと思うでしょう上記のように、あなたの入力のために、しかし、あなたは単純なリストへの最終的なSELECTを変換し、ITEMLIST型を削除できます。

Answer 2

リストを個々の項目に分割し、そのレベルで作業します。

いくつかのテーブル:

リスト

• ID (PK)
• シーケンス (上記の「A-B-C-D」エントリ)
• [ことなど]

アイテム

• ID (PK)
• 名前 (値、単語、意味のあるものなら何でも)
• [ことなど]

リストアイテム

• リストID
• アイテムID
• [「G-H-B-A」と「A-B-G-H」が異なるシーケンスとみなされる場合の序数 int]

(複合 PK list_ID、item_ID [、その順序]、基本的な多対多の関係)

いくつかのデータがあるため、表が何を表しているのかがより明確になります。

INSERT INTO items (ID, name) VALUES (1, 'A'), (2, 'B'), (3, 'G'), (4, 'H');
INSERT INTO lists (ID, sequence) VALUES (1, 'A-B-G-H');
INSERT INTO list_items (list_ID, item_ID) VALUES (1, 1), (1, 2), (1, 3), (1, 4);
INSERT INTO lists (ID, sequence) VALUES (2, 'B-A-G');
INSERT INTO list_items (list_ID, item_ID) VALUES (2, 2), (2, 1), (2, 3);

そして最後に、以下を含むリストを見つけます。 全て 項目 (A、B、G、H):

SELECT lists.sequence FROM lists
JOIN list_items ON lists.ID = list_items.list_ID
JOIN items AS i1 ON list_items.item_ID = i1.ID HAVING i1.name = 'A'
JOIN items AS i2 ON list_items.item_ID = i2.ID HAVING i2.name = 'B'
JOIN items AS i3 ON list_items.item_ID = i3.ID HAVING i3.name = 'G'
JOIN items AS i4 ON list_items.item_ID = i4.ID HAVING i4.name = 'H'

これにより、「A-B-G-H」、「G-H-A-B」、「H-A-T-B-A-G」などのリストが返されますが、「B-U-G-H-U-T」（A なし）や「B-A-T-H」（G なし）は返されません。すべての条件が満たされている必要があります。「任意の」検索を実行すると、もう少し複雑になる可能性があります (昼食をとりながら頭の中でこれを書いていますが、 RIGHT JOIN 単独では、おそらくあらゆる種類の重複と速度低下が発生する可能性があります)。

ゲノムをマッピングしたり、人間の言語を再定義したりすることはありませんが、まともなサイズのデータ​​セットには問題ないはずです。いずれにせよ、各リストを varchar として保存して「WHERE sequence LIKE '%A%' AND sequence LIKE '%B%'新しいデータを追加するための余分な作業を絶対に処理できない場合を除き、このようなものです。