Structure de données pour plages non superposées dans une même dimension

Question

J'ai besoin d'une structure de données pouvant stocker des plages non superposées dans une même dimension. Toute la gamme de la dimension n'a pas besoin d'être complètement couverte.

Un exemple serait un planificateur de salle de conférence. La dimension est le temps. Il n'y a pas deux horaires qui peuvent se chevaucher. La salle de conférence n'est pas toujours programmée. En d'autres termes, pour un temps donné, il peut y avoir au plus un horaire.

Une solution rapide est pour une plage pour stocker les heures de début et de fin.

Range { 
    Date start 
    Date end 
} 

Ceci est non-normalisé et nécessite que le conteneur n'impose aucun chevauchement. Pour deux plages adjacentes, l'extrémité précédente sera redondante avec le démarrage suivant.

Un autre schéma pourrait impliquer le stockage d'une valeur limite avec chaque plage. Mais pour une séquence contiguë de plages, il y aura toujours une valeur de limite de plus que les plages. Pour contourner ce problème de la séquence peut être représentée par des valeurs et des plages limites alternatif:

B = valeur limite, r = distance

BrBrB

La structure de données peut ressembler à:

Boundary { 
    Date value 
    Range prev 
    Range next 
} 

Range { 
    Boundary start 
    Boundary end 
} 

Essentiellement, il s'agit d'une liste à double liaison avec des types alternés. En fin de compte, quelle que soit la structure de données que j'utilise, elle sera représentée à la fois dans la mémoire (code de l'application) et dans une base de données relationnelle.

Je suis curieux de savoir quelles solutions éprouvées académiques ou industrielles existent.

Answer 1

Le normalisé façon de représenter vos données serait de stocker un enregistrement pour chaque unité de temps. Cela peut être fait dans l'exemple de l'application de planification de conférence. Votre contrainte serait une contrainte unique pour

(RoomId, StartTime) 

Dans le cas des gammes continues, vous devez nécessairement stocker 2 choses, une frontière et soit la seconde limite ou la longueur. Il se fait habituellement en stockant la seconde limite et puis en créant une contrainte sur les deux limites du genre

(boundary not between colBoudaryA and colBoundaryB) 

avec la contrainte supplémentaire que

(startBoundary < endBoundary) 

Answer 2

Une liste doublement chaînée fonctionne bien parce que vous utilisez uniquement beaucoup de mémoire car vous avez rempli des plages, et vous devez seulement vérifier le chevauchement sur les insertions - c'est presque trivial de le faire à ce moment-là. S'il y a chevauchement, le nouvel élément est rejeté.

 
RoomID 
ReservationID 
PreviousReservationID 
NextReservationID 
StartTimeDate 
EndTimeDate 
Priority 
UserID 

La priorité et UserID permettre des horaires d'avoir des priorités (professeur pourrait avoir plus de poids qu'un groupe d'étudiants) de sorte qu'un nouvel élément peut « frapper » les éléments les moins prioritaires sur la voie pendant une insertion, et L'ID utilisateur permet d'envoyer un e-mail aux organisateurs de réunions à destination.

Vous voudrez ajouter un tableau qui pointe vers la première réunion de chaque jour afin que les recherches puissent être optimisées.

-Adam

Answer 3

Beaucoup dépend de ce que vous allez faire avec les données, et donc que les opérations doivent être efficaces. Cependant, je considérerais une liste doublement chaînée de Ranges avec une logique dans les setters de Start et End pour vérifier si elle chevauche maintenant ses voisins, et pour les réduire si c'est le cas (ou lancer une exception, ou bien vous voulez gérer une tentative chevauchement).

Cela donne une liste simple et agréable de périodes réservées à lire, mais aucun conteneur responsable de la gestion de la règle de non-chevauchement.

Answer 4

Ceci est appelé la contrainte "Unary Resource" dans le monde Constraint Programming. Il y a beaucoup de recherche dans ce domaine, en particulier dans le cas où les heures des événements ne sont pas fixes, et vous devez trouver des créneaux horaires pour chacun d'entre eux. Il existe un paquet commercial C++ qui fait votre problème et plus Ilog CP, mais il est probablement exagéré. Il existe également une version quelque peu open-source appelée eclipse (aucune relation avec l'IDE).

Answer 5

Ceci est non trivial car (dans le monde de la base de données) vous devez comparer plusieurs lignes pour déterminer les plages qui ne se chevauchent pas. Clairement, lorsque l'information est en mémoire, alors d'autres représentations telles que des listes dans l'ordre temporel sont possibles. Je pense, cependant, que vous seriez mieux avec votre notation «début + fin», même dans une liste.

Il existe des livres entiers sur le sujet - une partie de la gestion de la base de données temporelle. Deux vous pouvez regarder sont Darwen, Date et Lorentzos "Temporal Data and the Relational Model" et (à un extrême radicalement différent) "Developing Time-Oriented Database Applications in SQL", Richard T. Snodgrass, Éditions Morgan Kaufmann, Inc., San Francisco, Juillet 1999, 504 + xxiii pages, ISBN 1-55860-436-7. C'est épuisé mais disponible en format PDF sur son site Web au cs.arizona.edu (donc une recherche sur Google le rend très facile à trouver).

L'une des structures de données pertinentes est, je crois, R-Tree. Cela est souvent utilisé pour les structures bidimensionnelles, mais peut également être efficace pour les structures à une dimension.

Vous pouvez également rechercher "Allen's Relations" pour les intervalles - ils peuvent vous être utiles.

Answer 6

J'ai réussi à stocker une heure et une durée de début. Le test de chevauchement serait quelque chose comme

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 
) 

Je pense que sans test, mais nous espérons que vous obtenez la dérive

Answer 7

1. Pour des intervalles ne se chevauchent pas vous pouvez simplement vous trier intervalles avec point de départ. Lorsque vous ajoutez un nouvel intervalle à cette structure, vous pouvez simplement vérifier que les points de début et de fin n'appartiennent pas à cet ensemble d'intervalles. Pour vérifier si un point X appartient à l'intervalle défini, vous pouvez utiliser la recherche binaire pour trouver le point de départ le plus proche et vérifier que X appartient à son intervalle. Cette approche n'est pas optimale pour les opérations de modification.

2. Vous pouvez voir la structure Interval tree - pour les intervalles sans chevauchement, elle a des opérations optimales de requête et de modification.

Answer 8

Si vous êtes chanceux (!) assez pour utiliser PostgreSQL, vous pouvez utiliser une colonne et appliquer une contrainte pour éviter les chevauchements. Le bonus de l'utilisation d'un type de plage est qu'il empêchera de manière inhérente de commencer à être plus grand que finir.

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

Vous devrez peut-être CREATE EXTENSION IF NOT EXISTS btree_gist, comme la création d'un point essentiel à l'aide & & est pas pris en charge sans cette extension.