1

我想知道我应该使用什么数据结构/存储策略来解决这个问题。

数据库中的每个数据条目由多个有序项的列表组成，例如 ABCD，其中 A、B、C、D 是不同的项。

假设我在数据库中有 3 个条目，

A B C D

EFG

GHBA

当用户输入一些未排序的项目时，我必须从数据库中找到匹配的有序条目。例如，如果用户输入 A,B,G,H，我想将 GHBA 从数据库返回给用户。

我的数据存储策略应该是什么？

4

2 回答 2

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 类型。

于 2010-02-09T23:18:43.750 回答
1

将列表拆分为单个项目并在该级别上工作。

一些表：

列表

  • 身份证（PK）
  • 序列（上面的“ABCD”条目）
  • [不管怎么说]

项目

  • 身份证（PK）
  • 名称（值，单词，任何有意义的）
  • [不管怎么说]

列表项

  • list_ID
  • item_ID
  • [一个 int 序数，如果 "GHBA" 和 "ABGH" 被认为是不同的序列]

（复合PK list_ID, item_ID [, ordinal] 就那一个，基本多：多关系）

一些数据，所以更清楚表格代表什么：

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'

这应该返回任何列表，如“ABGH”、“GHAB”、“HATBAG”等，但不能返回“BUGHUT”（无 A）或“BATH”（无 G）——必须满足所有条件。进行“任何”搜索可能会涉及更多内容（午餐时在我的脑海中写下这个，但RIGHT JOIN单独可能会导致各种重复和缓慢）。

它不会映射任何基因组或重新定义人类语言，但对于一个体面的数据集来说应该没问题。无论哪种方式，我都会避免将每个列表存储为 varchar 并执行 " WHERE sequence LIKE '%A%' AND sequence LIKE '%B%'" 东西，除非您绝对无法处理添加新数据的额外工作。

于 2010-02-09T20:51:36.860 回答