Intersecciones por pares

Question

Tengo una tabla con dos columnas, digamos Nombre y Apellido.Necesito obtener otra tabla, que para cada par de nombres del primero contenga un recuento de los apellidos comunes.

¿Es esto siquiera factible de hacer en SQL?

Hay apellidos mucho más exclusivos que nombres, si esto afecta la eficiencia de la consulta.

Un ejemplo de juguete, entrada:

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

Producción:

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

Como esta relación es reflexiva y simétrica, está bien si el resultado es solo uno de los triángulos (por ejemplo, el que está encima de la diagonal).

Answer 1

Voy a utilizar MS SQL Server para hacer esto ya que tengo una copia a mano.Creo que la mayoría de las grandes empresas lo harían de manera similar.

Primero una tabla de muestra, con datos.Utilizo una variable de tabla pero es igual para cualquier tipo de tabla.

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

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

Puedes obtener todos los pares haciendo una autounión:

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

Usando CROSS APPLY evita tener que pasar por obstáculos para encontrar una condición de unión para un ON cláusula.

A continuación necesitas algo para contar.Aquí es donde el CASE Entra la declaración.El caso devuelve un valor entero por par de nombres, que es lo que se cuenta.(Si estoy leyendo tu pregunta correctamente, querrás saber dónde coinciden los apellidos, así que esa es la comparación que tengo.Con suerte, será obvio cómo modificar esto si me equivoco).

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

Añadir un SUM() y GROUP BY y obtienes tu respuesta:

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

Tengo que admitir que mi pregunta fue un poco defectuosa. Lo que realmente necesitaba fue "porque cada par de Nombre del primer nombre de la primera contiene un recuento del apellido común".De hecho, no me importa los pares con recuentos cero.

Cuando se corrige la pregunta, la solución se vuelve mucho más rápida.

Dada la entrada:

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');

Para la pregunta original, la solución es O (n ^ 2) (porque la pregunta insiste en "cada par"):

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;

Si está bien omitir los recuentos cero, entonces una buena relación en el último nombre funciona mucho más rápido (asumiendo que los datos son suficientemente escasos):

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

Todavía me pregunto cómo me perdí esta solución trivial.

Answer 3

¡DOH!Aquí hay una mejor manera:

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;

Salida:

+-----------+-------------+----------+
| 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`.

Verificación de la cordura en el primer artículo:

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)

Los principales valores de estado del Handler% muestran que hizo mucho trabajo, pero no del todo o (n * n) (probablemente porque la unión cruzada es solo un estado a la vez):

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

Extrapolando a millones de filas: probablemente tomará días.

Answer 4

Ese fue un desafío interesante.Usando una lista de ciudades de los EE. UU., Subí esta solución (en 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) ayuda con el rendimiento.

Los resultados:

+----------+------------+-----------------------+
| 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)

Podría haber tomado 4 veces más tiempo que incluya todo el alfabeto.Solo había filas 4K en la mesa, por lo que esto es no una tarea rápida.

"Prueba" de los resultados: MySQL> Seleccionar ciudad, estado de nosotros donde la ciudad en ('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)