Группировка родителей, содержащих одинаковый набор детей

Question

У меня есть отношения родитель-ребенок

Paragraph
---------
ParagraphID   PK
// other attributes ...


Sentence
--------
SentenceID    PK
ParagraphID   FK -> Paragraph.ParagraphID
Text         nvarchar(4000)
Offset       int
Score        int
// other attributes ...

Я бы хотел найти абзацы, которые эквивалентны;то есть абзацы, которые содержат одинаковый набор предложений.Два предложения считаются одинаковыми, если они имеют одинаковый текст, смещение и оценку - SentenceID / ParagraphID не является частью сравнения, и два абзаца эквивалентны, если они содержат одинаковый набор предложений.

Может ли кто-нибудь показать мне, как будет выглядеть запрос для поиска равных абзацев?

РЕДАКТИРОВАТЬ: Есть ок.150 тыс. Абзацев и 1,5 млн. Предложений.Выходные данные должны включать ParagraphID и самый низкий идентификатор абзаца, эквивалентный этому.Например, если пункт1 и пункт2 равны, тогда результат будет

ParagraphID  EquivParagraphID
1            1
2            1

Answer 1

Поскольку у вас есть SQL 2008 в списке (я не уверен, что этот синтаксис был доступен в 2005 году), вы можете использовать EXCEPT или INTERSECT сравнения.Он включает в себя коррелированные подзапросы, поэтому производительность может быть проблемой.

SELECT
    *
FROM
    Paragraph P
WHERE
    (SELECT COUNT(*) FROM 
(
    SELECT
        S1.[Text],
        S1.Offset,
        S1.Score
    FROM
        Paragraph P1
    INNER JOIN Sentence S1 ON
        S1.ParagraphID = P1.ParagraphID
    WHERE
        P1.ParagraphID = P.ParagraphID
    INTERSECT
    SELECT
        S2.[Text],
        S2.Offset,
        S2.Score
    FROM
        Paragraph P2
    INNER JOIN Sentence S2 ON
        S2.ParagraphID = P2.ParagraphID
    WHERE
        P2.ParagraphID > P.ParagraphID
) SQ
) = (SELECT COUNT(*) FROM Sentence P3 WHERE P3.ParagraphID = P.ParagraphID)

Answer 2

Короче говоря, вам нужна подпись для каждого абзаца, а затем сравните подписи. Вы не упомянули природу самого выхода. Здесь я возвращаю строку значений ParagraphId, разделенных запятыми, для каждой идентичной подписи абзаца.

With ParagraphSigs As
    (
    Select P.ParagraphId
        , Hashbytes('SHA1'
                ,   (
                    Select '|' + S1.Text 
                        '|' + Cast(S1.Offset As varchar(10)) 
                        '|' + Cast(S1.Score As varchar(10))
                    From Sentence As S1
                    Where S1.ParagraphId = P.ParagraphId
                    Order By S1.SentenceId
                    For Xml Path('')
                    )) As Signature
    From Paragraph As P
    )
Select Stuff(
            (
            Select ', ' + Cast(PS1.ParagraphId As varchar(10))
            From ParagraphSigs As PS1
            Where PS1.Signature = PS.Signature
            For Xml Path('')
            ), 1, 2, '') As Paragraph
From ParagraphSigs As PS
Group By PS.Signature

Если вы добавите информацию о желаемом выводе, вы можете изменить запрос следующим образом:

With ParagraphSigs As
    (
    Select P.ParagraphId
        , Hashbytes('SHA1'
                ,   (
                    Select '|' + S1.Text 
                        '|' + Cast(S1.Offset As varchar(10)) 
                        '|' + Cast(S1.Score As varchar(10))
                    From Sentence As S1
                    Where S1.ParagraphId = P.ParagraphId
                    Order By S1.SentenceId
                    For Xml Path('')
                    )) As Signature
    From Paragraph As P
    )
Select P1.ParagraphId, P2.ParagraphId As EquivParagraphId
From ParagraphSigs As P1
    Left Join ParagraphSigs As P2
        On P2.Signature = P1.Signature
            And P2.ParagraphId <> P1.ParagraphId

Очевидно, что три или четыре абзаца могут иметь одну и ту же подпись, поэтому предупреждаем, что приведенные выше результаты дадут вам декартово произведение соответствующих параграфов. (например, (P1, P2), (P1, P3), (P2, P1), (P2, P3), (P3, P1), (P3, P2)).

В комментариях вы спрашивали об эффективном поиске по последнему предложению. Поскольку у вас есть два других параметра, вы можете уменьшить количество генерируемых подписей, сравнив сначала два столбца типа int:

With ParagraphsNeedingSigs As
    (
    Select P1.ParagraphId
    From Paragraph As P1
    Where Exists    (
                    Select 1
                    From Paragraph As P2
                    Where P2.ParagraphId <> P1.ParagraphId
                        And P2.Offset = P1.Offet
                        And P2.Score = P1.Score
                    )
    )
    , ParagraphSigs As
    (
    Select P.ParagraphId
        , Hashbytes('SHA1'
                ,   (
                    Select '|' + S1.Text 
                        '|' + Cast(S1.Offset As varchar(10)) 
                        '|' + Cast(S1.Score As varchar(10))
                    From Sentence As S1
                    Where S1.ParagraphId = P.ParagraphId
                    Order By S1.SentenceId
                    For Xml Path('')
                    )) As Signature
    From ParagraphsNeedingSigs As P
    )
Select P.ParagraphId, P2.ParagraphId As EquivParagraphId
From Paragraph As P
    Left Join ParagraphSigs As P1
        On P1.ParagraphId = P.ParagraphId
    Left Join ParagraphSigs As P2
        On P2.Signature = P1.Signature
            And P2.ParagraphId <> P1.ParagraphId