database design - pairs - Estructura de datos para rangos no superpuestos dentro de una sola dimensión

poligono en r

Question

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

Un ejemplo sería un programador 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 los tiempos de inicio y fin.

Range {
    Date start
    Date end
}

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

Otro esquema podría implicar el almacenamiento de un valor 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 podría representarse como rangos y valores de frontera alternativos:

B = valor límite, r = rango

BrBrB

La estructura de datos podría verse así:

Boundary {
    Date value
    Range prev
    Range next
}

Range {
    Boundary start
    Boundary end
}

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

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

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

Answer 1

Esto se conoce como la restricción "Recurso Unario" en el mundo de Programación de Restricciones . 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 2

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

(RoomId, StartTime)

En el caso de rangos continuos, necesariamente necesita almacenar 2 cosas, un límite y el segundo límite o la longitud. Generalmente se realiza almacenando el segundo límite y luego creando una restricción en ambos límites del tipo

(boundary not between colBoudaryA and colBoundaryB)

con la restricción adicional que

(startBoundary < endBoundary)

Answer 3

Mucho depende de lo que harás con los datos y, por lo tanto, qué operaciones 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 y enlazada de períodos reservados para leer, pero ningún contenedor es responsable de mantener la regla de no superposición.

Answer 4

Una lista doblemente enlazada funciona bien porque solo utiliza la misma cantidad de memoria que los rangos llenos, 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 permiten que los horarios tengan prioridades (el profesor puede tener más influencia que un grupo de estudiantes) para que un nuevo elemento pueda "quitar" los elementos de menor prioridad durante una inserción, y el ID de usuario permite que se envíe un correo electrónico. enviado a los organizadores de la reunión golpeado.

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

-Adán

Answer 5

Esto no es trivial porque (en el mundo de la base de datos) debe comparar varias filas para determinar los rangos que no se superponen. 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 de los que podría ver son Darwen, Date y Lorentzos " Datos temporales y el modelo relacional " y (en un extremo radicalmente diferente) " Desarrollo de aplicaciones de bases de datos orientadas al tiempo en 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 disponible como PDF en su sitio web en 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, un 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 " Relaciones de Allen " para intervalos; pueden ser útiles para usted.

Answer 6

1. Para intervalos que no se superponen, puede ordenar los intervalos con el punto de inicio. 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 ver la estructura de árbol de Intervalo : para intervalos que no se solapan, tiene operaciones óptimas de consulta y modificación.

Answer 7

Tuve éxito almacenando una hora y duración de inicio. La prueba de 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 que sin pruebas, pero espero que entiendas la deriva

Answer 8

Si tiene la suerte (!) De 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 , ya que la creación de una idea principal utilizando && no es compatible sin esa extensión.