estrutura de dados permitindo “Pesquisar por fim”
-
19-09-2019 - |
Pergunta
Gostaria de saber o que / estratégia de armazenamento estrutura de dados devo usar para este problema.
Cada entrada de dados na base de dados é constituído por uma lista de itens pedidos múltiplos, tais como A-B-C-D, em que A, B, C, D são diferentes itens.
Suponha que eu tenho 3 entradas em um banco de dados,
A-B-C-D
E-F-G
L-H-B-A
Quando o usuário entrou alguns itens não ordenadas, eu tenho que encontrar a correspondência ordenou entrada (s) do banco de dados. Por exemplo, se o utilizador entra A, B, G, H, I querem voltar G-H-B-à partir da base de dados para o utilizador.
Qual deve ser a minha estratégia de armazenamento de dados?
Solução
Você é melhor fora de armazenar os elementos ordenados e não ordenados separadamente, caso contrário você vai precisar pesquisar em todas as permutações dos elementos ordenados, o que seria demorado.
Tente isto:
/* 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
O acima retornará 3: GHBA, como você quiser. Se você passar no DCBA você vai voltar 1: ABCD, novamente como você está procurando. Se você passar em C, você vai voltar nada, já que nenhum grupo é composto por apenas C.
Você provavelmente vai querer usar um valor de tabela parâmetro para a sua entrada, como mostrado acima, mas você poderia converter o SELECT final para uma lista simples e soltar o tipo ITEMLIST.
Outras dicas
Dividir as listas em itens individuais e trabalho nesse nível.
Algumas tabelas:
listas
- ID (PK)
- sequência ( "A-B-C-D" entradas acima)
- [qualquer outra coisa]
itens
- ID (PK)
- nome (valor, palavra, tudo o que faz sentido)
- [qualquer outra coisa]
list_items
- list_id
- item_id
- [um int ordinal, se "G-H-B-A" e "A-B-G-H" são consideradas sequências diferentes]
(composto PK list_id, item_id [, ordinal] em que um, de base muitos: relação muitos)
Alguns dados, por isso é mais claro o que as tabelas representam:
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);
E, finalmente, para encontrar listas que contêm todas itens (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'
Isso deve retornar quaisquer listas como "A-B-G-H", "G-H-A-B", "H-A-T-B-A-G", etc, mas não "B-U-G-H-U-T" (sem A) ou "B-A-T-H" (sem G) - todas as condições têm de ser satisfeitas. Fazendo um "qualquer" busca pode ser um pouco mais envolvido (escrevendo isso na minha cabeça durante o almoço, mas RIGHT JOIN
sozinho provavelmente resultaria em todos os tipos de duplicatas e lentidão).
Não vai mapear quaisquer genomas ou redefinir a linguagem humana, mas deve estar bem para um conjunto de dados de tamanho decente. De qualquer maneira, eu evitar o armazenamento de cada lista como um varchar e fazendo coisas "WHERE sequence LIKE '%A%' AND sequence LIKE '%B%'
" a menos que você absolutamente não pode lidar com o trabalho extra para adicionar novos dados.