Estructura de datos para rangos no solapados dentro de una única dimensión

Question

Necesito una estructura de datos que pueda almacenar rangos no solapados dentro de una sola dimensión. El rango completo de la dimensión no necesita estar completamente cubierto.

Un ejemplo sería un planificador de sala de conferencias. La dimensión es tiempo No hay dos horarios pueden solaparse. La sala de conferencias no siempre está programada. En otras palabras, por un tiempo dado puede haber como máximo un horario.

Una solución rápida es para un rango para almacenar las horas de inicio y finalización.

Range { 
    Date start 
    Date end 
} 

Esto no es normalizado y requiere que el contenedor no exija superposición. Para dos rangos adyacentes, el extremo anterior será redundante con el siguiente inicio.

Otro esquema puede implicar el almacenamiento de un valor de límite con cada rango. Pero para una secuencia contigua de rangos, siempre habrá un límite de valores más que rangos. Para evitar esto la secuencia puede ser representada como alternando valores de límites y rangos: podría parecerse

B = valor límite, r = rango

BrBrB

La estructura de datos:

Boundary { 
    Date value 
    Range prev 
    Range next 
} 

Range { 
    Boundary start 
    Boundary end 
} 

En esencia, es una lista doblemente vinculada con tipos alternativos.

En definitiva, cualquiera que sea la estructura de datos que utilizo se representará tanto en la memoria (código de aplicación) como en una base de datos relacional.

Tengo curiosidad por saber qué soluciones académicas o industriales existen.

Answer 1

El normalizado manera de representar sus datos sería almacenar un registro para cada unidad de tiempo. Esto se puede hacer en el ejemplo de la aplicación de programación de conferencias. Su limitación sería una restricción única para

(RoomId, StartTime) 

En el caso de los rangos continuos, que necesariamente tienen que almacenar 2 cosas, un límite y, o bien el segundo límite o la longitud. Por lo general se realiza almacenando el segundo límite y luego crear una restricción en tanto límite de la clase

(boundary not between colBoudaryA and colBoundaryB) 

con la restricción adicional de que

(startBoundary < endBoundary) 

Answer 2

Una lista doblemente enlazada funciona bien porque sólo se utiliza como mucha memoria a medida que ha llenado rangos, y solo necesita verificar la superposición de las inserciones; es casi trivial hacerlo en ese punto. Si hay superposición, el nuevo elemento es rechazado.

 
RoomID 
ReservationID 
PreviousReservationID 
NextReservationID 
StartTimeDate 
EndTimeDate 
Priority 
UserID 

La prioridad y el ID de usuario permitir horarios de tener prioridades (profesor podría tener más influencia que un grupo de estudiantes) para que un nuevo elemento se puede 'tocar' los artículos de menor prioridad fuera del camino durante una inserción, y el ID de usuario permite que se envíe un correo electrónico a los organizadores de reuniones golpeados.

Querrá considerar agregar una tabla que apunte a la primera reunión de cada día para que las búsquedas se puedan optimizar.

-Adam

Answer 3

Mucho depende de lo que va a hacer con los datos, y por lo tanto las operaciones que deben ser eficientes. Sin embargo, consideraría una lista de rangos doblemente enlazados con lógica en los iniciadores de inicio y fin para verificar si ahora se superpone a sus vecinos, y reducirlos si es así (o lanzar una excepción, o como quiera que intente un intento superposición).

Eso le da una buena lista simple enlazada de períodos reservados para leer, pero ningún contenedor es responsable de mantener la regla de no superposición.

Answer 4

Esto se conoce como la restricción "Recurso unario" en el mundo Constraint Programming. Hay mucha investigación en esta área, específicamente para el caso cuando los tiempos del evento no son fijos, y necesita encontrar espacios de tiempo para cada uno de ellos. Hay un paquete comercial de C++ que hace su problema y más Ilog CP, pero es probable que sea excesivo. También hay una versión de código abierto llamada eclipse (sin relación con el IDE).

Answer 5

Esto no es trivial porque (en el mundo de la base de datos) tiene que comparar varias filas para determinar los rangos no superpuestos. Claramente, cuando la información está en la memoria, entonces otras representaciones tales como listas en orden de tiempo son posibles. Creo, sin embargo, que sería mejor con su notación de "inicio + fin", incluso en una lista.

Hay libros enteros sobre el tema, que forman parte del manejo de 'Temporal Database'. Dos que podría ver son Darwen, Date y Lorentzos "Temporal Data and the Relational Model" y (en un extremo radicalmente diferente) "Developing Time-Oriented Database Applications in SQL", Richard T. Snodgrass, Morgan Kaufmann Publishers, Inc., San Francisco, julio de 1999, 504 + xxiii páginas, ISBN 1-55860-436-7. Eso está agotado, pero está disponible como PDF en su sitio web al cs.arizona.edu (por lo que una búsqueda en Google lo hace bastante fácil de encontrar).

Una de las estructuras de datos relevantes es, creo, una R-Tree. Esto se usa a menudo para estructuras bidimensionales, pero también puede ser efectivo para estructuras de 1 dimensión.

También puede buscar "Allen's Relations" para intervalos: pueden ser útiles para usted.

Answer 6

Tuve éxito almacenando una hora y duración inicial. La prueba para la superposición sería algo así como

WHERE NOT EXISTS (
    SELECT 1 FROM table 
    WHERE BeginTime < NewBeginTime AND BeginTime + Duration > NewBeginTime 
) 
AND NOT EXISTS (
    SELECT 1 FROM table 
    WHERE NewBeginTime < BeginTime AND NewBeginTime + NewDuration > BeginTime 
) 

Creo, sin pruebas, pero esperamos que pueda obtener la deriva

Answer 7

1. Para intervalos no se solapan sólo podría ordenar que los intervalos con punto de partida. Cuando agrega un nuevo intervalo a esta estructura, puede verificar que los puntos de inicio y fin no pertenecen a este conjunto de intervalos. Para verificar si algún punto X pertenece al conjunto de intervalos, puede usar la búsqueda binaria para encontrar el punto de inicio más cercano y verificar que X pertenece a su intervalo. Este enfoque no es tan óptimo para modificar operaciones.

2. Puede mirar la estructura Interval tree - para intervalos que no se solapan, tiene operaciones óptimas de consulta y modificación.

Answer 8

Si tiene suerte (!) lo suficiente como para utilizar Postgres, puede usar una columna tstzrange y aplicar una restricción para evitar superposiciones. La ventaja de usar un tipo de rango es que evitará que el inicio sea mayor que el final.

ALTER TABLE "booking" 
ADD CONSTRAINT "overlapping_bookings" 
EXCLUDE USING gist ("period" WITH &&, "room" WITH =); 

Es posible que necesite CREATE EXTENSION IF NOT EXISTS btree_gist, como la creación de una esencia usando & & no se admite sin esa extensión.