Структура данных, позволяющая осуществлять “Поиск по порядку”

Question

Я хотел бы знать, какую структуру данных / стратегию хранения мне следует использовать для решения этой проблемы.

Каждая запись данных в базе данных состоит из списка нескольких упорядоченных элементов, таких как A-B-C-D, где A, B, C, D - разные элементы.

Предположим, у меня есть 3 записи в базе данных,

A-B-C-D

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.

Вероятно, вы захотите использовать параметр с табличным значением для вашего ввода, как показано выше, но вы могли бы преобразовать окончательный ВЫБОР в простой список и удалить тип ItemList.

Answer 2

Разделите списки на отдельные элементы и работайте на этом уровне.

Несколько таблиц:

Списки

• Идентификатор (PK)
• последовательность (записи "A-B-C-D" выше)
• [что бы там еще]

Товары

• Идентификатор (PK)
• имя (значение, слово, все, что имеет смысл)
• [что бы там еще]

список элементов

• list_ID ( Идентификатор списка )
• item_ID Элемент_id
• [порядковый номер int, если "G-H-B-A" и "A-B-G-H" считаются разными последовательностями]

(составной 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%'"материал, если только вы абсолютно не можете справиться с дополнительной работой по добавлению новых данных.