Les intersections deux à deux

Question

J'ai un tableau avec deux colonnes, disons FirstName et LastName.J'ai besoin d'une autre table, qui, pour chaque paire de Prénom à partir de la première contient un nombre de la commune Nom de l'.

Est-ce même possible de le faire en SQL?

Il y a beaucoup plus unique LastName est que le Prénom de l', si cela affecte l'efficacité de la requête.

Un jouet exemple, en entrée:

FirstName, LastName
John, Smith
John, Doe
Jane, Doe

Sortie:

FirstName1, FirstName2, CommonLastNames
John, John, 2
John, Jane, 1
Jane, Jane, 1
Jane, John, 1

Comme cette relation est réflexive et symétrique, c'est OK si le résultat est tout simplement l'un des triangles (e.g, l'un au-dessus de la diagonale).

Answer 1

Je vais utiliser MS SQL Server pour cela, car j'ai une copie à la main.Je crois que la plupart des tout des majors ferait de même.

D'abord un exemple de table, avec des données.J'utilise une variable de table mais c'est la même pour toute la saveur de la table.

declare @t table (FirstName char(10), LastName char(10));

insert @t(FirstName,LastName)
values ('John','Smith'),('John','Doe'),('Jane','Doe');

Vous pouvez obtenir toutes les paires en faisant une auto-jointure:

select
    a.FirstName, a.LastName, b.FirstName, b.LastName
from @t as a
cross apply @t as b;

À l'aide de CROSS APPLY évite d'avoir à sauter à travers des cerceaux pour trouver une condition de jointure pour un ON la clause.

Ensuite, vous besoin de quelque chose pour les compter.C'est là que l' CASE déclaration vient en.Le cas renvoie une valeur entière par paire de prénoms, qui est ce qui est compté.(Si je suis en train de lire votre question correctement vous voulez et où la LastNames match donc c'est la comparaison que j'ai.J'espère que c'est évident comment modifier cela si je me trompe.)

select
    ...
    case
        when a.LastName = b.LastName then 1
        else 0
    end
...etc.

Ajouter dans un SUM() et GROUP BY et vous obtenez votre réponse:

select
    a.FirstName,
    b.FirstName,
    sum(
    case
        when a.LastName = b.LastName then 1
        else 0
    end
    ) as CommonLastNames
from @t as a
cross apply @t as b
group by a.FirstName, b.FirstName;

Answer 2

Je dois admettre ma question était un peu imparfait. Ce que j'ai vraiment besoin, ce n'était pas vraiment "pour chaque paire de prénoms de la première contient un nombre de noms communs".En fait, je me soucie de paires avec zéro compte.

Lorsque la question est corrigée, la solution devient beaucoup plus rapide.

Compte tenu de l'entrée:

create local temp table t (FirstName char(10), LastName char(10)) ON COMMIT PRESERVE ROWS;
insert into t(FirstName,LastName) values ('John','Smith');
insert into t(FirstName,LastName) values ('John','Doe');
insert into t(FirstName,LastName) values ('Jane','Doe');

Pour la question initiale, la solution est O (n ^ 2) (car la question insiste sur "chaque paire"):

select a.FirstName, b.FirstName, 
  sum(case when a.LastName = b.LastName then 1 else 0 end) CommonNames 
  from t a, t b group by 1, 2;

S'il est correct de sauter zéro compte, alors un auto joint sur l'autre nom fonctionne beaucoup plus vite (en supposant que les données soient suffisamment clairsemées):

select a.FirstName, b.FirstName,
  count(*) CommonNames from t a
  join t b using (LastName) group by 1, 2;

Je me demande toujours comment j'ai manqué cette solution triviale.

Answer 3

Doh!Voici une meilleure façon:

SELECT city_a, city_b, COUNT(*)
    FROM (
        SELECT a.city city_a,
               a.state,
               b.city city_b
        FROM       us a
        CROSS JOIN us b
        WHERE a.state = b.state
          AND a.city < b.city
         ) x
    GROUP BY city_a, city_b
    ORDER BY 3 DESC;

sortie:

+-----------+-------------+----------+
| city_a    | city_b      | COUNT(*) |
+-----------+-------------+----------+
| Lebanon   | Springfield |        5 |
| Bedford   | Franklin    |        4 |  -- as shown in previous 'answer'
| Franklin  | Lebanon     |        4 |
| Franklin  | Hudson      |        4 |
| Franklin  | Salem       |        4 |
| Hudson    | Salem       |        4 |
| Salem     | Springfield |        4 |
| Clinton   | Columbia    |        4 |
| Auburn    | Fairfield   |        3 |
| Auburn    | Madison     |        3 |
...
(2.63 sec) -- for all 4175 cities in `us`.

Vérification de la santé du premier article:

mysql> SELECT city, state FROM us WHERE city IN ('Lebanon', 'Springfield');
+-------------+-------+
| city        | state |
+-------------+-------+
| Springfield | FL    |
| Springfield | IL    |
| Lebanon     | IN    |
| Springfield | MA    |
| Lebanon     | ME    |
| Lebanon     | MO    |
| Springfield | MO    |
| Lebanon     | NH    |
| Springfield | NJ    |
| Lebanon     | OH    |
| Springfield | OH    |
| Lebanon     | OR    |
| Springfield | OR    |
| Lebanon     | PA    |
| Springfield | PA    |
| Lebanon     | TN    |
| Springfield | TN    |
| Springfield | VA    |
| Springfield | VT    |
+-------------+-------+
19 rows in set (0.00 sec)

Le gestionnaire principal% valeurs d'état montre qu'il a fait beaucoup de travail, mais pas tout à fait o (n * n) (probablement parce que la croix rejoindre n'est qu'un seul état à la fois):

| Handler_read_key           | 4176   |
| Handler_read_next          | 667294 |
| Handler_read_rnd           | 1742   |
| Handler_read_rnd_next      | 701964 |
| Handler_update             | 1731   |
| Handler_write              | 703693 |

Extrapolatier à des millions de lignes - cela prendra probablement des jours.

Answer 4

C'était un défi intéressant.À l'aide d'une liste de villes des états-unis, je suis venu avec cette solution (MySQL):

SELECT  city_a, city_b,
        COUNT(DISTINCT state)
    FROM (
        ( SELECT a.city city_a,
                 b.city city_b,
                 a.state            -- This line differs
            FROM       us a
            CROSS JOIN us b
            WHERE a.state = b.state
              AND a.city != b.city   -- Added (to avoid noise)
              AND a.city < 'M'    -- to speed up test
              AND b.city < 'M'
        )
        UNION ALL
        ( SELECT a.city city_a,
                 b.city city_b,
                 b.state            -- This line differs
            FROM       us a
            CROSS JOIN us b
            WHERE a.state = b.state
              AND a.city != b.city   -- Added (to avoid noise)
              AND a.city < 'M'    -- to speed up test
              AND b.city < 'M'
        )
        ) ab
    GROUP BY 1, 2
    HAVING   COUNT(DISTINCT state) > 1
    ORDER BY COUNT(DISTINCT state) desc

INDEX(state, city) aide à la performance.

Les résultats:

+----------+------------+-----------------------+
| city_a   | city_b     | COUNT(DISTINCT state) |
+----------+------------+-----------------------+
| Franklin | Bedford    |                     4 |
| Lebanon  | Franklin   |                     4 |
| Franklin | Lebanon    |                     4 |
| Hudson   | Franklin   |                     4 |
| Columbia | Clinton    |                     4 |
| Clinton  | Columbia   |                     4 |
| Franklin | Hudson     |                     4 |
| Bedford  | Franklin   |                     4 |
| Lebanon  | Farmington |                     3 |
| Hanover  | Kingston   |                     3 |
...
(25.17 sec)

Il aurait pu prendre 4 fois plus de temps pour inclure l'ensemble de l'alphabet.Il n'y avait que 4K lignes dans la table, donc c'est pas un rapide de tâche.

La "preuve" des résultats:mysql> SELECT ville, état-unis OÙ la ville ("Franklin', 'Bedford');

+----------+-------+
| city     | state |
+----------+-------+
| Bedford  | IN    |
| Franklin | IN    |
| Bedford  | MA    |
| Franklin | MA    |
| Bedford  | NH    |
| Franklin | NH    |
| Bedford  | OH    |
| Franklin | OH    |
| Franklin | TN    |
| Bedford  | TX    |
| Franklin | WI    |
+----------+-------+
11 rows in set (0.00 sec)