les parents de regroupement contenant le même ensemble d'enfants

Question

j'ai cette relation parent-enfant

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


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

Je voudrais trouver les paragraphes qui sont équivalents; c'est des paragraphes qui contiennent le même ensemble de phrases. Deux phrases sont considérées comme identiques si elles ont le même Texte, Offset et Score - SentenceID/ParagraphID ne fait pas partie de la comparaison, et deux paragraphes sont équivalents s'ils contiennent un ensemble de phrases égales.

Quelqu'un pourrait-il me montrer à quoi ressemblerait une requête pour trouver des paragraphes égaux?

EDIT: Il y a ca. 150K paragraphes, et des phrases de 1,5M. La sortie doit inclure l'ID Paragraphe et l'ID de paragraphe le plus bas équivalent à celui-ci. Par exemple. si paragraph1 et paragraph2 sont égaux, alors la sortie sera

ParagraphID EquivParagraphID 
1   1 
2   1 

Answer 1

En résumé, vous avez besoin d'une signature pour chaque paragraphe, puis comparez les signatures. Vous n'avez pas mentionné la nature de la sortie elle-même. . Ici, je "suis de retour d'une rangée de valeurs ParagraphId de délimité par des virgules pour chaque signature de paragraphe identique

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 

Étant donné que vous plus à propos de la sortie désirée, vous pouvez modifier la requête comme ceci:

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 

Évidemment, il est possible que trois ou quatre paragraphes partagent la même signature, donc soyez averti que les résultats ci-dessus vous donneront un produit cartésien de paragraphes correspondants (par exemple (P1, P2), (P1, P3), (P2, P1), (P2, P3), (P3, P1), (P3, P2))

Dans les commentaires, vous avez demandé abo Je cherche effectivement sur la dernière phrase. Puisque vous avez deux autres paramètres, vous pouvez réduire le nombre de signatures générées en faisant en comparant les deux colonnes int première:

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 

Answer 2

Depuis que vous avez énuméré SQL 2008 (je ne sais pas si cette syntaxe était disponible en 2005), vous pourriez être en mesure d'utiliser les comparaisons EXCEPT ou INTERSECT. Cela implique des sous-requêtes corrélées, donc la performance peut être un problème.

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)