Struttura dei dati permettendo “Ricerca per ordine”

Question

Mi piacerebbe sapere la strategia struttura di quali dati / storage dovrei usare per questo problema.

Ogni voce dati nel database è costituito da un elenco di più elementi, come A-B-C-D, dove A, B, C, D sono elementi diversi ordinato.

Supponiamo che io sono 3 voci in un database,

A-B-C-D

E-F-G

G-H-B-A

Quando l'utente ha inserito alcuni elementi non ordinate, devo trovare l'abbinamento ordinato entry (ies) dal database. Ad esempio, se l'utente inserisce A, B, G, H, voglio tornare G-H-B-A dal database per l'utente.

Quale dovrebbe essere la mia strategia di archiviazione dati?

Answer 1

Stai meglio memorizzare gli elementi ordinate e non ordinate a parte, in caso contrario è necessario per cercare tutte le permutazioni degli elementi ordinati, che sarebbe tempo.

Prova questo:

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

È possibile che questo restituirà 3: GHBA, come si desidera. Se si passa DCBA si otterrà indietro 1: ABCD, ancora una volta come si sta cercando. Se si passa in C, si otterrà indietro nulla, come nessun gruppo è composto da appena C.

Probabilmente si desidera utilizzare una parametro per il vostro input, come indicato sopra, ma si potrebbe convertire SELECT finale per un elenco semplice e rilasciare il tipo ITEMLIST.

Answer 2

Dividere le liste in singoli elementi e lavorare su quel livello.

Alcune tabelle:

list

• ID (PK)
• sequenza (i "A-B-C-D" voci precedenti)
• [qualsiasi altra cosa]

oggetti

• ID (PK)
• nome (valore, parola, tutto ciò ha un senso)
• [qualsiasi altra cosa]

list_items

• list_id
• item_id
• [int ordinale, se "G-H-B-A" e "A-B-G-H" sono considerati differenti sequenze]

(PK composito list_id, item_id [, ordinale] su quello, molti di base: molti relazione)

Alcuni dei dati, in modo che sia più chiaro quali sono le tabelle rappresentano:

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, infine, di trovare le liste che contengono tutti articoli (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'

Questo dovrebbe tornare elenchi come "A-B-G-H", "G-H-A-B", "H-A-T-B-A-G", ecc, ma non "B-U-G-H-U-T" (No a) o "B-A-T-H" (senza G) - tutte le condizioni devono essere soddisfatte. Facendo un "qualsiasi" ricerca potrebbe essere un po 'più coinvolto (scrivendo questo nella mia testa durante il pranzo, ma RIGHT JOIN sola sarebbe probabilmente avvenuta in tutti i tipi di duplicati e lentezza).

Non sarà mappare qualsiasi genomi o ridefinire il linguaggio umano, ma dovrebbe essere a posto per un set di dati di dimensioni decenti. Ad ogni modo, mi piacerebbe evitare la memorizzazione di ogni lista come varchar e fare cose "WHERE sequence LIKE '%A%' AND sequence LIKE '%B%'" a meno che non si può assolutamente gestire il lavoro supplementare per aggiungere nuovi dati.