"순서로 검색"이 가능한 데이터 구조

Question

이 문제에는 어떤 데이터 구조/저장 전략을 사용해야 하는지 알고 싶습니다.

데이터베이스의 각 데이터 항목은 A-B-C-D와 같은 여러 주문 항목 목록으로 구성됩니다. 여기서 A, B, C, D는 서로 다른 항목입니다.

데이터베이스에 3개의 항목이 있다고 가정해 보겠습니다.

ABCD

E-F-G

G-H-B-A

사용자가 주문되지 않은 항목을 입력하면 데이터베이스에서 일치하는 주문 항목을 찾아야 합니다.예를 들어, 사용자가 A,B,G,H를 입력하면 데이터베이스에서 G-H-B-A를 사용자에게 반환하고 싶습니다.

데이터 저장 전략은 무엇이어야 합니까?

Answer 1

순서대로 정렬되지 않은 요소를 별도로 저장하는 것이 가장 좋습니다. 그렇지 않으면 정렬 된 요소의 모든 순열을 검색해야합니다.

이 시도:

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

위의 것은 3 : GHBA, 원하는 것처럼 반환됩니다. DCBA를 통과하면 다시 찾고있는 것처럼 1 : ABCD를 다시 얻을 수 있습니다. C를 통과하면 그룹이 C만으로 구성되지 않으므로 아무것도 되돌릴 수 없습니다.

당신은 아마 a를 사용하고 싶을 것입니다 테이블 값 매개 변수 위에 표시된 것처럼 입력의 경우 최종 선택을 간단한 목록으로 변환하고 ItemList 유형을 떨어 뜨릴 수 있습니다.

Answer 2

목록을 개별 항목으로 분할하고 해당 수준에서 작업합니다.

일부 테이블:

기울기

• 아이디(PK)
• 순서(위의 "A-B-C-D" 항목)
• [다른 건 뭐든지]

아이템

• 아이디(PK)
• 이름(값, 단어, 의미가 있는 모든 것)
• [다른 건 뭐든지]

목록_항목

• 목록_ID
• item_ID
• ["G-H-B-A"와 "A-B-G-H"가 다른 시퀀스로 간주되는 경우 서수 int]

(복합 PK 목록_ID, 항목_ID [, 서수], 기본 다대다 관계)

일부 데이터이므로 테이블이 나타내는 내용이 더 명확해집니다.

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

마지막으로 다음을 포함하는 목록을 찾으려면 모두 항목(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'

"A-B-G-H", "G-H-A-B", "H-A-T-B-A-G" 등과 같은 목록이 반환되어야 하지만 "B-U-G-H-U-T"(A 없음) 또는 "B-A-T-H"(G 없음)는 반환되지 않습니다. 모든 조건이 충족되어야 합니다."모든" 검색을 수행하는 것은 좀 더 복잡할 수 있습니다(점심 시간에 머리 속으로 이 글을 적었지만, RIGHT JOIN 혼자서는 아마도 모든 종류의 중복 및 속도 저하가 발생할 수 있습니다).

게놈을 매핑하거나 인간 언어를 재정의하지는 않지만 적당한 크기의 데이터 세트에는 괜찮을 것입니다.어느 쪽이든 각 목록을 varchar로 저장하고 "WHERE sequence LIKE '%A%' AND sequence LIKE '%B%'" 새 데이터를 추가하기 위한 추가 작업을 전혀 처리할 수 없는 경우를 제외하고는 말이죠.