sql - password - Partición de una lista de conjuntos por elementos compartidos

tde sql server 2008

Question

Aquí está la cuestión del problema: dada una lista de conjuntos, como:

[ (1,2,3), (5,2,6), (7,8,9), (6,12,13), (21,8,34), (19,20) ]

Devuelve una lista de grupos de conjuntos, de modo que los conjuntos que tienen un elemento compartido estén en el mismo grupo.

[ [ (1,2,3), (5,2,6), (6,12,13) ], [ (7,8,9), (21,8,34) ], [ (19,20) ] ]

Tenga en cuenta la stickeyness - el conjunto (6,12,13) ​​no tiene un elemento compartido con (1,2,3), pero se ponen en el mismo grupo debido a (5,2,6).

Para complicar las cosas, debo mencionar que realmente no tengo estos juegos geniales, sino más bien una tabla DB con varios millones de filas que se ve así:

element | set_id
----------------
1 | 1
2 | 1
3 | 1
5 | 2
2 | 2
6 | 2

y así. Así que me encantaría una forma de hacerlo en SQL, pero estaría contento con una dirección general para la solución.

EDITAR : Cambió los nombres de columna de la tabla a (elemento, set_id) en lugar de (clave, id_grupo), para hacer que los términos sean más consistentes. Tenga en cuenta que la respuesta de Kev usa los nombres de las columnas antiguas.

Answer 1

Esto probablemente sea bastante ineficiente, pero debería funcionar, al menos: comience con una clave, seleccione todos los grupos que la contengan, seleccione todas las claves de esos grupos, seleccione todos los grupos que contienen esas claves, etc., y tan pronto como sea posible. un paso no agrega nuevas llaves o grupos, usted tiene una lista de todos los grupos de un sub-gráfico. Excluya esos y repita desde el principio hasta que no le queden datos.

En términos de SQL, esto necesitaría un procedimiento almacenado, creo. WITH RECURSIVE puede ayudarte de alguna manera, pero todavía no tengo ninguna experiencia con él, y no estoy seguro de que esté disponible en tu back-end de DB.

Answer 2

El problema es exactamente el cálculo de los componentes conectados de un hipergraph: los enteros son los vértices, y los conjuntos son los hyperedges. Una forma habitual de calcular los componentes conectados es inundándolos uno tras otro:

• para todo i = 1 a N, hacer:
• si me han etiquetado con j <i, entonces continúo (me refiero a saltar al siguiente i)
• else flood_from (i, i)

donde flood_from (i, j) se definiría como

• para cada conjunto S que contiene i, si ya no está etiquetado por j, entonces:
• etiquetar S por j y para cada elemento k de S, si k aún no está etiquetado por j, luego etiquetarlo por j, y llamar a flood_from (k, j)

Las etiquetas de los conjuntos le dan los componentes conectados que está buscando.

En términos de bases de datos, el algoritmo se puede expresar de la siguiente manera: agrega una columna TAG a su base de datos y calcula el componente conectado del conjunto i haciendo

• S = seleccionar todas las filas donde set_id == i
• establecer TAG en i para las filas en S
• S ''= selecciona todas las filas donde TAG no está establecido y donde el elemento está en el elemento (S)
• mientras que S ''no está vacío, hazlo
• ---- establece TAG en i para las filas en S ''
• ---- S '''' = selecciona todas las filas donde TAG no está establecido y donde el elemento está en el elemento (S '')
• ---- S = S unión S ''
• ---- S ''= S'' ''
• devolver set_id (S)

Otra forma (teórica) de presentar este algoritmo sería decir que está buscando los puntos fijos de un mapeo:

• si A = {A ₁ , ..., A _n } es un conjunto de conjuntos, defina la unión (A) = A ₁ unión ... unión A _n
• si K = {k ₁ , ..., k _p } es un conjunto de enteros, defina incidencias (K) = el conjunto de conjuntos que se cruzan con K

Entonces, si S es un conjunto, el componente conectado de S se obtiene al iterar (incidencias) o (unión) en S hasta que se alcanza un punto fijo:

1. K = S
2. K ''= incidencias (unión (K)).
3. si K == K '', entonces devuelve K, sino K = K'' y pasa a 2.

Answer 3

Se podría pensar que es un problema de gráfico donde el conjunto (1,2,3) se conecta al conjunto (5,2,6) a través de 2. Y luego utiliza un algoritmo estándar para ajustar los subgráficos conectados.

Aquí hay una implementación rápida de Python:

nodes = [ [1,2,3], [2,4,5], [6,7,8], [10,11,12], [7,10,13], [12], [] ]
links = [ set() for x in nodes ]
#first find the links
for n in range(len(nodes)):
for item in nodes[n]:
for m in range(n+1, len(nodes)):
if (item in nodes[m]):
links[n].add(m)
links[m].add(n)
sets = []
nodes_not_in_a_set = range(len(nodes))
while len(nodes_not_in_a_set) > 0:
nodes_to_explore = [nodes_not_in_a_set.pop()]
current_set = set()
while len(nodes_to_explore) > 0:
current_node = nodes_to_explore.pop()
current_set.add(current_node)
if current_node in nodes_not_in_a_set:
nodes_not_in_a_set.remove(current_node)
for l in links[current_node]:
if l not in current_set and l not in nodes_to_explore:
nodes_to_explore.append(l)
if len(current_set) > 0:
sets.append(current_set)
for s in sets:
print [nodes[n] for n in s]

salida:

[[]]
[[6, 7, 8], [10, 11, 12], [7, 10, 13], [12]]
[[1, 2, 3], [2, 4, 5]]

Answer 4

Después de pensar en esto un poco más, se me ocurrió esto:

1. Crea una tabla llamada groups con columnas (group_id, set_id)
2. Ordene los sets tabla por element . Ahora debería ser fácil encontrar elementos duplicados.
3. Itera a través de la tabla de conjuntos, y cuando encuentre un elemento duplicado, haga lo siguiente:
   1. si uno de los campos set_id existe en la tabla de groups , agregue el otro con el mismo group_id .
   2. Si ni set_id existe en la tabla de groups , genere una nueva ID de grupo, y agregue ambos set_id s a la tabla de groups .

Al final debería tener una tabla de groups contenga todos los conjuntos.

Esto no es SQL puro, pero parece que O (nlogn), así que supongo que puedo vivir con eso.

La respuesta de Matt parece más correcta, pero no estoy seguro de cómo implementarla en mi caso.