Wie kann man die Anzahl der bidirektional verbundenen Nachbarn von A oder B zählen?

Question

Nachfolgend die Abfrage, die ich erstellt habe, um die Anzahl der gemeinsamen stark verbundenen (in beide Richtungen verbundenen) Nachbarn von zwei Benutzern zu zählen:

DECLARE @monthly_connections_test TABLE (
  calling_party VARCHAR(50)
  , called_party VARCHAR(50))

INSERT INTO @monthly_connections_test
          SELECT 'z1', 'z2'
UNION ALL SELECT 'z1', 'z3'
UNION ALL SELECT 'z1', 'z4'
UNION ALL SELECT 'z1', 'z5'
UNION ALL SELECT 'z1', 'z6'
UNION ALL SELECT 'z2', 'z1'
UNION ALL SELECT 'z2', 'z4'
UNION ALL SELECT 'z2', 'z5'
UNION ALL SELECT 'z2', 'z7'
UNION ALL SELECT 'z3', 'z1'
UNION ALL SELECT 'z4', 'z7'
UNION ALL SELECT 'z5', 'z1'
UNION ALL SELECT 'z5', 'z2'
UNION ALL SELECT 'z7', 'z4'
UNION ALL SELECT 'z7', 'z2'

SELECT  t1.user1, t1.user2,
        0 AS calling_calling, 0 AS calling_called, 
        0 AS called_calling, 0 AS called_called, 
        COUNT(*) AS both_directions
  FROM (SELECT relevant_monthly_connections.calling_party AS user1, 
               relevant_monthly_connections_1.calling_party AS user2,
               relevant_monthly_connections.called_party AS calledUser
          FROM @monthly_connections_test relevant_monthly_connections 
            INNER JOIN @monthly_connections_test AS relevant_monthly_connections_1 
               ON    relevant_monthly_connections.called_party  = relevant_monthly_connections_1.called_party 
                 AND relevant_monthly_connections.calling_party < relevant_monthly_connections_1.calling_party
       ) t1 
     INNER JOIN @monthly_connections_test AS relevant_monthly_connections_2
       ON     relevant_monthly_connections_2.called_party  = t1.user1
          AND relevant_monthly_connections_2.calling_party = t1.calledUser
  GROUP BY t1.user1, t1.user2

Jetzt möchte ich die stark verbundenen Nachbarn von user1 ODER user2 zählen. Also zum Beispiel für das Paar (z1, z2) die Anzahl der stark verbundenen Nachbarn ist 3 (z1 ist stark verbunden mit z2, z3, z5 und z2 wird ignoriert, da es einer der Knoten aus dem Paar ist und z2 ist stark verbunden mit z1, z5 und z7. wieder, z1 wird ignoriert und count((z3, z5) U (z5, z7)) ist 3).

Weiß jemand, wie die Abfrage zu erstellen, um die Anzahl aller Knoten zu zählen, die stark mit einem der Knoten aus dem Paar für jedes Paar verbunden sind (die Abfrage muss automatisch die Anzahl aller Nachbarn für jeden Datensatz berechnen)?

Bearbeiten #1:

Die folgende Abfrage gibt die Tabelle mit allen bidirektionalen Verbindungen zurück:

WITH bidirectionalConnections AS
(
SELECT calling_party AS user1, called_party AS user2 FROM @monthly_connections_test WHERE calling_party < called_party
INTERSECT
SELECT called_party AS user2, calling_party AS user2 FROM @monthly_connections_test
)
SELECT user1, user2 FROM bidirectionalConnections

Nun muss für jedes Knotenpaar in der Tabelle bidirectionalConnections überprüft werden, wie viele Knoten stark mit dem ersten oder zweiten Knoten des Paares verbunden sind.

Die Paare und die Anzahl ihrer Nachbarn im Ergebnis müssen automatisch generiert werden.

Bearbeiten #2:

Hier ist das Bild, das durch die Tabelle @monthly_connections_test beschrieben wird:

Die Nachbarn, die eng mit z1 ODER z2 verbunden sind, sind also z3, z5, z7

z1, z3: z2, z5

z1, z4: z2, z3, z5, z7

...

z1, z7: z2, z3, z4, z5

...

Die Ergebnistabelle sollte das folgende Format haben:

user1, user2, total_neighbors_count
z1, z2, 3
z1, z3, 2
z1, z4, 4
...
z1, z7, 4
...

Ich danke Ihnen!

P.S.

Ich habe eine ähnliche Frage gestellt Wie kann man JOIN anstelle von UNION verwenden, um die Nachbarn von "A OR B" zu zählen? aber es ist nicht dasselbe, also hoffe ich, dass diese Frage nicht als Duplikat betrachtet wird.

Answer 1

Ich glaube, dass die unten stehende Abfrage das gewünschte Ergebnis liefert. Ich habe die Abfrage so strukturiert, dass jede Stufe der Pipeline explizit ist, was den zusätzlichen Nebeneffekt hat, dass der Abfrageoptimierer einen starken Hinweis darauf erhält, wie die Größe der Zwischenzeilenmengen minimiert werden kann. In den Kommentaren in der Abfrage selbst finden Sie den Zweck der einzelnen Phasen.

;WITH
  -- identify the strongly connected parties
  -- both directions are included here for later convenience
  stronglyConnected AS (
    SELECT DISTINCT
      l.calling_party AS party1
    , l.called_party AS party2
    FROM @monthly_connections_test AS l
    INNER JOIN @monthly_connections_test AS r
      ON r.calling_party = l.called_party
      AND r.called_party = l.calling_party
  )
  -- identify all of the parties that participated in a strong connection
, uniqueParties AS (
    SELECT DISTINCT party1 AS party FROM stronglyConnected
  )
  -- make all unique pairs of such parties
, allPairs AS (
    SELECT
      u1.party AS party1
    , u2.party AS party2
    FROM uniqueParties AS u1
    CROSS JOIN uniqueParties AS u2
    WHERE u1.party < u2.party
  )
  -- find the neighbours of each pair
, pairNeighbors AS (
    SELECT DISTINCT
      p.party1
    , p.party2
    , sc.party2 AS neighbor
    FROM allPairs AS p
    INNER JOIN stronglyConnected AS sc
      ON sc.party1 IN (p.party1, p.party2)
      AND sc.party2 NOT IN (p.party1, p.party2)
  )
  -- count the neighbours of each pair
, neighbourCounts AS (
    SELECT
      party1 AS user1
    , party2 AS user2
    , COUNT(*) AS total_neighborCount
    FROM pairNeighbors
    GROUP BY
      party1
    , party2
  )
-- show the final result
SELECT * FROM neighbourCounts ORDER BY 1, 2
-- handy for testing, debugging and answering other queries:
-- SELECT * FROM stronglyConnected ORDER BY 1, 2
-- SELECT * FROM uniqueParties ORDER BY 1
-- SELECT * FROM allPairs ORDER BY 1, 2
-- SELECT * FROM pairNeighbors ORDER BY 1, 2

Answer 2

Ich denke, die Beispielabfrage, die Sie in der Frage bereitstellen, ist fehlerhaft (basierend auf der Beschreibung) - sie gibt zurück z5 - z7 als ein stark verbundenes Paar, obwohl diese Kombination in den Beispieldaten überhaupt nicht vorkommt. Ich glaube, dass dies eine korrekte Umsetzung ist:

SELECT calling.*
FROM    @monthly_connections_test AS calling
WHERE   EXISTS  (   SELECT 1
                    FROM @monthly_connections_test AS called
                    WHERE   calling.calling_party   = called.called_party
                    AND     calling.called_party    = called.calling_party
        )
AND     calling.calling_party   < calling.called_party  

Ich habe diese Implementierung so erweitert, dass sie das bietet, was Sie wollen. Dies ist keine besonders schöne Lösung und sollte an einem größeren Datensatz getestet werden, da sie möglicherweise nicht hervorragend skaliert. Ich habe die Variablennotation von SQL 2008 verwendet, da sich Ihre andere Frage auf SQL 2008 bezog.

DECLARE @user1 varchar(50) = 'z1'
DECLARE @user2 varchar(50) = 'z2'

;WITH strongCTE
AS
(
    SELECT  calling.calling_party AS c1,
            calling.called_party AS c2
    FROM    @monthly_connections_test AS calling
    WHERE   EXISTS  (   SELECT 1
                        FROM @monthly_connections_test AS called
                        WHERE   calling.calling_party   = called.called_party
                        AND     calling.called_party    = called.calling_party
            )
    AND     calling.calling_party   < calling.called_party  
)
SELECT COUNT(1) AS ConnectedNeighboursToUser1orUser2
FROM
(
    SELECT  c2
    FROM    strongCTE
    WHERE   c1 = @user1
    AND     c2 NOT IN (@user1,@user2)
    GROUP BY c1,c2

    UNION

    SELECT  c2
    FROM    strongCTE
    WHERE   c1 = 'z2'
    AND     c2 NOT IN (@user1,@user2)
    GROUP BY c1,c2
) AS x

Answer 3

Auf der Grundlage von Edit2 liefert die folgende Abfrage die aufgelisteten Ergebnisse:

declare @party1 varchar(50)
declare @party2 varchar(50)

--Since we're only interested in strong connections, we can treat both parties as calling_party in the following queries

select @party1 = 'z1', @party2 = 'z7'

select
    distinct mt.called_party 
from
    @monthly_connections_test mt
        inner join
    @monthly_connections_test mt2
        on
            mt.called_party = mt2.calling_party and
            mt.calling_party = mt2.called_party
where
    mt.calling_party in (@party1,@party2) and
    not mt.called_party in (@party1,@party2)

Um nur den Zählerstand zu erhalten, müssen Sie die Funktion COUNT(distinct mt.called_party) in der Select-Klausel

---

Im Folgenden sind alle Gruppen für jedes verbundene Paar aufgeführt. Ich denke, es wird schwieriger, wenn wir Duplikate für stark verbundene Paare vermeiden müssen:

select grp.called_party,grp.calling_party,COUNT(distinct mt.called_party )
from
    (select
          CASE WHEN calling_party < called_party THEN calling_party ELSE called_party END as calling_party,CASE WHEN calling_party < called_party THEN called_party ELSE calling_party END as called_party FROM @monthly_connections_test) grp,
    @monthly_connections_test mt
        inner join
    @monthly_connections_test mt2
        on
            mt.called_party = mt2.calling_party and
            mt.calling_party = mt2.called_party
where
    mt.calling_party in (grp.called_party,grp.calling_party) and
    not mt.called_party in (grp.called_party,grp.calling_party)
group by grp.called_party,grp.calling_party