Structure de données permettant "Recherche par commande"

Question

Je voudrais savoir quelle structure de données/stratégie de stockage je devrais utiliser pour ce problème. Chaque entrée de données dans la base de données consiste en une liste de plusieurs éléments commandés, tels que A-B-C-D, où A, B, C, D sont des éléments différents.

Supposons que j'ai 3 entrées dans une base de données,

ABCD

EFG

GHBA

Lorsque l'utilisateur est entré quelques éléments désordonnées, je dois trouver l'entrée ordonnée correspondant (s) de la base de données. Par exemple, si l'utilisateur entre A, B, G, H, je veux retourner G-H-B-A de la base de données à l'utilisateur.

Quelle devrait être ma stratégie de stockage de données?

Answer 1

Il est préférable de stocker séparément les éléments ordonnés et non ordonnés, sinon vous devrez effectuer une recherche sur toutes les permutations des éléments ordonnés, ce qui prendrait beaucoup de temps.

Essayez ceci:

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

ci-dessus retournera 3: GHBA, comme vous voulez. Si vous passez en DCBA, vous récupérerez 1: ABCD, comme vous le souhaitez. Si vous passez en C, vous ne récupérerez rien, car aucun groupe ne se compose uniquement de C.

Vous voudrez probablement utiliser un table-valued parameter pour votre saisie, comme indiqué ci-dessus, mais vous pouvez convertir le SELECT final en liste simple et supprimez le type ItemList.

Answer 2

Divisez les listes en éléments individuels et travaillez à ce niveau.

Quelques tables:

listes

• ID séquence (PK)
• (les entrées "ABCD" ci-dessus)
• [tout ce]

des articles

• ID (PK)
• nom (valeur, mot, tout ce qui est logique)
• [quel que soit d'autre]

list_items

• LIST_ID
• ITEM_ID
• [un ordinal int, si "GHBA" et "ABGH" sont considérés comme des séquences différentes]

(composite PK LIST_ID, ITEM_ID [, ordinal] sur celui-là, beaucoup de base: nombre lien de parenté)

Certaines données, il est donc plus clair que les tableaux représentent:

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); 

Et enfin, trouver des listes qui contiennent tous articles (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' 

qui devrait renvoyer les listes comme "ABGH", "GHAB", "HATBAG", etc, mais pas « BUGHU- T "(non A) ou" B-A-T-H "(non G) - toutes les conditions doivent être remplies. Faire une "n'importe quelle" recherche pourrait être un peu plus impliqué (écrire ceci dans ma tête au cours du déjeuner, mais RIGHT JOIN seul entraînerait probablement toutes sortes de doublons & lenteur).

Il ne mappera aucun génome ou ne redéfinira pas le langage humain, mais devrait être acceptable pour un ensemble de données de taille décente. De toute façon, j'éviterais de stocker chaque liste comme un varchar et de faire des choses "WHERE sequence LIKE '%A%' AND sequence LIKE '%B%'" sauf si vous ne pouvez absolument pas gérer le travail supplémentaire pour ajouter de nouvelles données.