Структура данных, обеспечивающая «Поиск по заказу» - PullRequest
Новая
       30

Структура данных, обеспечивающая «Поиск по заказу»

1 голос
/ 07 февраля 2010

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

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

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

А-В-С-D

E-F-G

G-Н-В-А

Когда пользователь вводит неупорядоченные элементы, я должен найти соответствующую упорядоченную запись (записи) из базы данных. Например, если пользователь вводит A, B, G, H, я хочу вернуть G-H-B-A из базы данных пользователю.

Какой должна быть моя стратегия хранения данных?

Ответы [ 2 ]

1 голос
/ 10 февраля 2010

Лучше всего хранить упорядоченные и неупорядоченные элементы по отдельности, в противном случае вам потребуется выполнить поиск по всем перестановкам упорядоченных элементов, что может занять много времени.

Попробуйте это: 

/* 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.

1 голос
/ 09 февраля 2010

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

Некоторые таблицы:

списки

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

товар

  • ID (PK)
  • имя (значение, слово, все, что имеет смысл)
  • [что-нибудь еще]

list_items

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

...