24

Hace unos días ví una pregunta que entre otras cosas implicaba un problema similar al que voy a plantear, lo quería hacer de una forma más general, por que entiendo que la solución bien planteada podría servir como referencia a problemas parecidos. Tal vez para algunos de ustedes la respuesta sea trivial o evidente, pero en mi caso recién cuando la mastique bastante encontré (al menos eso creo) que era más simple de lo que pensaba. Lo planteo en Sql pero podría ser más de algoritmos, el tema es que me pareció más práctico para poder testear las soluciones.

Supongamos el siguiente ejemplo:

CREATE TABLE A (
    NRO_DESDE INT,
    NRO_HASTA INT
    )

CREATE TABLE B (
    NRO_DESDE INT,
    NRO_HASTA INT
    )

INSERT INTO A (NRO_DESDE, NRO_HASTA)
VALUES (5, 8)

INSERT INTO B (NRO_DESDE, NRO_HASTA)
VALUES (1, 2), (4, 5), (5, 8), (6, 7), (7, 9), (4, 10), (9, 11)

SELECT NRO_DESDE, NRO_HASTA FROM A;
SELECT NRO_DESDE, NRO_HASTA FROM B;

La tabla A tiene un único valor:

NRO_DESDE NRO_HASTA
========= =========
5         8

La tabla B

NRO_DESDE NRO_HASTA
========= =========
1         2
4         5
5         8
6         7
7         9
4         10
9         11

Las tabla A y B representan conjuntos de intervalos, pero de los que no contamos con todos los valores sino que conocemos el primer y último elemento de cada conjunto, la idea es comparar el único conjunto en A con todos los de B y determinar si comparten algún elemento. A modo de ejemplo el registro de B (4, 5) comparte el 5 con A, el (1, 2) no comparte ningún elemento, el (7, 9) comparten el 7, 8. El resultado sería entonces los registros de B que tienen elementos compartidos con los de A, no es importante saber cuales son, solo saber que los hay, también podemos asumir que la cantidad de elementos en cada conjunto es relativamente manejable. No se preocupen por la ausencias de claves primarias es simplemente un ejemplo conceptual.

Nota: El código está armado en SQL Server pero podría ser resuelto en cualquier "sabor" de SQL.

2
  • quieres una respuesta en sql o podria ser en algun lenguaje de programacion Commented el 12 ago. 2017 a las 3:05
  • Sin duda, sería interesante ver las soluciones en otro lenguaje, pero habría que confeccionar una pregunta similar con la etiqueta del lenguaje correspondiente. Saludos. Commented el 12 ago. 2017 a las 23:07

3 respuestas 3

25

No se si es la query mas performante del planeta.. pero tenes un problema de conjuntos.

SELECT B.ID, *
FROM A, B
where
A.nro_desde between B.nro_desde and B.nro_hasta
or
A.nro_hasta between B.nro_desde and B.nro_hasta
or
B.nro_desde between A.nro_desde and A.nro_hasta
or
B.nro_hasta between A.nro_desde and A.nro_hasta

Con una consulta así estas buscando todas las variantes de los dos conjuntos que se cruzan.

Fíjate que primero probamos A contra los intervalos de B. Y después hacemos lo mismo para B. Esto ultimo, porque si el intervalo de A contiene completamente al de B, entonces no saldría en la primer consulta.

1
  • Efectivamente es un problema de conjuntos, y tu respuesta la forma natural de ver el problema. Estoy preparando otra respuesta-explicación con un poco de teoría de conjuntos y te adelanto que creo que hay una forma más compacta aún. Saludos. Commented el 3 ago. 2017 a las 17:50
24
+50

La respuesta de gbianchi efectivamente resuelve mi pregunta, contemplando los 4 distintos casos en que los intervalos pueden estar conectados. Veamos:

introducir la descripción de la imagen aquí

Los casos 1 y 2 son clásicas intersecciones de conjuntos, al ser intervalos, uno se puede ubicar antes del otro y tener contacto por sus extremos. En el ejemplo sería por ejemplo el intervalo 4-5 o 7-9 que se conectan con el intervalo A 5-8 por alguno de sus extremos.

introducir la descripción de la imagen aquí

Los otros dos casos posibles son los casos de inclusión, dónde un conjunto está incluido en el otro. Por ejemplo el intervalo B (6-7) está incluido en el A (5-8), o al revés, el A está incluido en el B (4-10). Para contemplar los 4 casos y como el único dato que tenemos de los conjuntos son sus límites, la consulta se debe resolver tal como lo menciona gbianchi.

SELECT *
FROM A, B
where
    A.nro_hasta between B.nro_desde and B.nro_hasta or -- Caso 1/3
    A.nro_desde between B.nro_desde and B.nro_hasta or -- Caso 2/3
    B.nro_desde between A.nro_desde and A.nro_hasta or -- Caso 1/4
    B.nro_hasta between A.nro_desde and A.nro_hasta    -- Caso 2/4

Otra forma de ver este problema es pensar que casos no cumplen estas condiciones. Si vamos a la teoría el único caso es el de los conjuntos disjuntos, es decir:

introducir la descripción de la imagen aquí

Conjuntos que no se conectan, al ser intervalos los casos son dos, cuando B es menor a A o al revés. Si estudiamos ahora como comparar los límites vamos a ver que es mucho más sencillo, sería:

  • que B.NRO_HASTA < A.NRO_DESDE o
  • que A.NRO_HASTA < B.NRO_DESDE

y lo interesante de esto, es que la negación de estos casos es alguno de los casos anteriores, por lo que podríamos simplificar la consulta original a lo siguiente:

SELECT *
    FROM A, B
    WHERE NOT (
                B.NRO_HASTA < A.NRO_DESDE OR
                A.NRO_HASTA < B.NRO_DESDE
              )

O mejor aún, con los Joins explicítos:

SELECT *
        FROM A 
        INNER JOIN B
        ON NOT (
                    B.NRO_HASTA < A.NRO_DESDE OR
                    A.NRO_HASTA < B.NRO_DESDE
               )

O como bien dice Fede H, aplicando un poco de álgebra para quitar el NOT:

SELECT *
        FROM A 
        INNER JOIN B
        ON (
                B.NRO_HASTA >= A.NRO_DESDE AND
                A.NRO_HASTA >= B.NRO_DESDE
           )

Si bien este es un ejemplo conceptual, en la realidad nos podremos encontrar con muchos casos parecidos a esto, por ejemplo, es común trabajar de este modo con las fechas en ciertos problemas:

  • ¿Qué habitaciones de un hotel están desocupadas entre un rango de fechas?
  • ¿Qué personas están de viaje entre fechas?
  • ¿Qué personajes históricos vivieron entre ciertos siglos?
4
  • Tu respuesta no es mala, pero, ¿por qué usar JOIN implícito en lugar de un explícito? El uso de JOIN implícito se consideró deprecado en el año 1992.
    – Phi
    Commented el 9 ago. 2017 a las 21:14
  • Absolutamente de acuerdo, se me escapó.. Commented el 10 ago. 2017 a las 11:51
  • Esto no genera un problema de full scan en los casos de tablas con muchos registros?
    – gbianchi
    Commented el 13 ago. 2017 a las 17:38
  • En el caso que el campo no este indizado, sin duda se hará un table scan. Si tiene un índice, me imagino, dependerá de la distribución de fechas, en el caso que la tabla A las fechas tengan un cierto orden, tal vez para el motor sea más económico hacer un table scan en vez de usar el índice. Commented el 14 ago. 2017 a las 0:48
9

Para mi la solución mas clara es parecida a la de Patricio pero con las condiciones invertidas. Justamente la he tenido que usar hace poco con fechas y quizas en ese caso se entienda mejor. Voy a tratar de parafrasearlo para ver si se entiende.

Los rangos que busco son lo que terminan despues del inicio del rango objetivo y empiezan antes del fin del rango objetivo

SELECT *
    FROM A, B
    WHERE B.NRO_HASTA >= A.NRO_DESDE
      AND B.NRO_DESDE <= A.NRO_HASTA

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.