estructura de datos que permite “Búsqueda por orden”

Question

Me gustaría saber lo que la estrategia de la estructura de datos / almacenamiento que debe utilizar para este problema.

Cada entrada de datos en la base de datos consiste en una lista de varios elementos, tales como A-B-C-D, donde A, B, C, D son elementos diferentes clasificadas.

Supongamos que tengo 3 entradas en una base de datos,

A-B-C-D

E-F-G

G-H-B-A

Cuando el usuario ha introducido algunos elementos desordenados, tengo que encontrar la entrada coincidente ordenado (s) a partir de la base de datos. Por ejemplo, si el usuario entra en A, B, G, H, I quiero volver G-H-B-A de la base de datos para el usuario.

¿Cuál debe ser mi estrategia de almacenamiento de datos?

Answer 1

es el mejor de almacenar los elementos ordenadas y desordenadas por separado, de lo contrario tendrá que buscar en todas las permutaciones de los elementos ordenados, lo que sería mucho tiempo.

Prueba esto:

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

Lo anterior devolverá 3: GHBA, como lo desea. Si pasa en DCBA que pondremos en 1: ABCD, de nuevo como si estuviera buscando. Si pasa en C, que pondremos en nada, ya que ningún grupo se compone de solo C.

Es probable que desee utilizar un con valores de tabla de parámetros para su entrada, como se muestra arriba, pero se puede convertir la final SELECT para una lista simple y soltar el tipo ITEMLIST.

Answer 2

Dividir las listas de partidas individuales y trabajar en ese nivel.

Algunas tablas:

listas

• ID (PK)
• secuencia (los "A-B-C-D" entradas anteriores)
• [lo que sea]

artículos

• ID (PK)
• Nombre (valor, palabra, lo que tenga sentido)
• [lo que sea]

list_items

• list_id
• item_id
• [un int ordinal, si "G-H-B-A" y "A-B-G-H" se consideran diferentes secuencias]

(compuesto PK list_id, item_id [, ordinal] en que uno, muchos básica: muchos relación)

Algunos datos, por lo que es más claro cuáles son las tablas representan:

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

Y, por último, para encontrar listas que contienen todos artículos (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'

que debe devolver ninguna lista como "A-B-G-H", "G-H-A-B", "H-A-T-B-A-G", etc, pero no "B-T-G-H-T-T" (no A) o "B-A-T-H" (sin G) - todas las condiciones tienen que ser satisfecho. Hacer una "ninguna" búsqueda podría ser un poco más complicado (escribiendo esto en mi cabeza durante el almuerzo, pero RIGHT JOIN solos probablemente daría lugar a todo tipo de duplicados y lentitud).

No va a asignar cualquier genomas o redefinir el lenguaje humano, pero debería estar bien para un conjunto de datos de tamaño decente. De cualquier manera, yo evitaría almacenar cada lista como un varchar y haciendo cosas "WHERE sequence LIKE '%A%' AND sequence LIKE '%B%'" a menos que absolutamente no puede manejar el trabajo extra para añadir nuevos datos.