如何在 RDBMS 中存储和搜索序列？

Question

我需要在数据库（SQL Server 2008）中存储一些序列/列表，然后从数据库中查找特定序列的 ID（如果存在）。

例如，我有两个序列：

序列 1：A、B、C 序列2：A、C、M、N

目前它们存储在下表中。 （如果可以让事情变得更容易，我可以更改表。）

seq_id   token   order
1        A       0
1        B       1
1        C       2
2        A       0
2        C       1
2        M       2
2        N       3

我想编写一个查询来返回给定序列的 id，例如“A，B，C”（如果存在精确匹配）。序列的长度事先是未知的。谢谢你！

Answer 1

您需要的是所谓的关系划分（请参阅Celko）。最佳解决方案取决于您的 RDB 引擎。如果您能够这样做 - 最流行的解决方案是：

1. 将您的查询表示为一个表（A、B、C 的表）
2. 将您的表与现有表进行内连接，按 seq_id 进行分组，对组中的元素进行计数
3. 使用count 来过滤掉不精确的序列（即，当查找 A、B、C 时，计数必须为 3）

假设您有一个 #query 表，其中包含您希望查找的标记和排序（我使用 sort 而不是 order 来避免与保留关键字冲突）

create table #query
(
token nvarchar(1)
,sort int
)

insert into #query select 'A',0
insert into #query select 'B',1
insert into #query select 'C',2
go

select  seq_id
from    dbo.sequences s
inner join  #query q
    on  q.token = s.token
        and q.sort = s.sort
group by s.seq_id
having count(*) = (select count(*) from #query)

将返回与您的查询匹配的 seq_id。在较新版本的 MsSql 中，人们将使用表变量而不是 #query，但该技术可以普遍应用。

Answer 2

您需要的是每个序列的特定于订单的签名。使用 SQL Server 2008，您可以使用 For Xml Path 构造为每个序列和条件组合签名，然后将其与另一个进行比较。显然，这不会很快。您可以在保存每个序列或更改其成员资格时将签名存储到每个序列的相应表中，从而极大地提高速度（也可以使用触发器）。另外，我这里只是使用了原始签名。但是，通常情况下，我倾向于使用 Hashbytes 函数对签名使用组装值的哈希值。

Declare @TestInputs Table   (
                            seq_id int not null
                            , token char(1) not null
                            , [order] int not null
                            )
Insert @TestInputs( seq_id, token, [order] )
Values (1,'A',0)
    , (1,'B',1)
    , (1,'C',2)
    , (2,'A',0)
    , (2,'C',1)
    , (2,'M',2)
    , (2,'N',3);

Declare @Criteria Table (
                        token char(1) not null
                        , [order] int not null
                        )   
Insert @Criteria( token, [order] )
Values ('A',0)
    , ('B',1)
    , ('C',2);  

With Criteria As
    (
    Select  (
            Select '|' + Token
            From @Criteria
            Order By [order]
            For Xml Path('')
            ) As Signature
    )
    , InputSignatures As
    (
    Select T.seq_id
        ,   (
            Select '|' + T1.Token
            From @TestInputs As T1
            Where T1.seq_id = T.seq_id
            Order By T1.[order]
            For Xml Path('')
            ) As Signature
    From @TestInputs As T
    Group By T.seq_id
    )
Select I.*
From InputSignatures As I
    Join Criteria As C  
        On C.Signature = I.Signature

Answer 3

为什么不按原样存储：

seq_id   token
1        A,B,C       
2        A,C,M,N

查询变得微不足道