Die Datenstruktur ermöglicht „Suche nach Ordnung“

Question

Ich mag wissen, welche Datenstruktur / Storage-Strategie I für dieses Problem verwenden soll.

Jeder Dateneintrag in der Datenbank besteht aus einer Liste von mehreren bestellten Artikel, wie A-B-C-D, wobei A, B, C, D sind verschiedene Artikel.

Angenommen, ich habe 3 Einträge in einer Datenbank,

A-B-C-D

E-F-G

G-H-B-A

Wenn der Benutzer einige ungeordnete Artikel eingegeben, muss ich die passende bestellt Eintrag (n) aus der Datenbank finden. Zum Beispiel, wenn der Benutzer A eintritt, B, G, H, I will G-H-B-A aus der Datenbank an den Benutzer zurück.

Was soll meine Datenspeicherstrategie sein?

Answer 1

Sie sind am besten dran, die geordnete und ungeordnete Elemente separat zu speichern, sonst werden Sie auf alle Permutationen der geordneten Elemente suchen müssen, was zeitaufwendig wäre.

Versuchen Sie folgendes:

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

Das oben zurückkehren 3: GHBA, wie Sie wollen. Wenn Sie in DCBA bestehen werden Sie zurück 1 erhalten: ABCD, wieder wie Sie suchen. Wenn Sie in C passieren, erhalten Sie nichts zurück, da keine Gruppe von nur C besteht

Sie wollen wahrscheinlich ein Tabellenwertparameter rel="nofollow wie oben für Ihre Eingabe, gezeigt, aber man konnte die letzte SELECT auf eine einfache Liste und legen Sie die ItemList Typ umwandeln.

Answer 2

Teilen Sie die Listen in einzelnen Positionen und Arbeiten auf diesem Niveau.

Einige Tabellen:

Listen

• ID (PK)
• Sequenz (der "A-B-C-D" -Einträge oben)
• [was auch immer]

Elemente

• ID (PK)
• name (Wert, Wort, was Sinn macht)
• [was auch immer]

list_items

• LIST_ID
• ITEM_ID
• [int ordinal ein, wenn "G-H-B-A" und "A-B-G-H" werden als unterschiedliche Sequenzen]

(Composite-PK LIST_ID, ITEM_ID [, Ordnungs] auf, dass man, Grund viele: viele Relation)

Einige Daten, so dass es mehr klar, was die Tabellen darstellen:

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

Und schließlich Listen zu finden, enthält alle Artikel (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'

Das sollte keine Listen zurückgeben wie "A-B-G-H", "G-H-A-B", "H-A-T-B-A-G", etc, aber nicht "B-U-G-H-U-T" (kein A) oder "B-A-T-H" (keine G) - alle Bedingungen müssen erfüllt sein. eine „any“ Suche tun könnte ein wenig mehr beteiligt sein (schreibt dies in meinem Kopf über das Mittagessen, aber RIGHT JOIN allein wahrscheinlich in allen Arten von Dubletten & Langsamkeit führen würde).

Es wird keine Genome Karte oder die menschliche Sprache neu zu definieren, sollte aber für einen recht großen Datensatz in Ordnung sein. So oder so, ich vermeiden würde jede Liste als varchar zu speichern und zu tun „WHERE sequence LIKE '%A%' AND sequence LIKE '%B%'“ Sachen, es sei denn man kann absolut nicht die zusätzliche Arbeit behandeln, um neue Daten hinzufügen.