Trouver des emplacements libres dans un système de réservation

Question

Dans my question about searching for date ranges J'ai essayé de simplifier le problème et j'ai posé par inadvertance un problème différent et plus simple. Plutôt que de compliquer cette question avec un montage, je vais poser le problème que je voulais réellement.

J'ai deux tables Propriété et réservation. Les réservations ont une clé étrangère pour les propriétés ainsi que les dates de début et de fin.

L'utilisateur est à la recherche d'emplacements libres et fournit la durée souhaitée en jours. Ils fournissent également une gamme de dates de début qui les intéressent. Par conséquent, une recherche sera sur le modèle de: "Trouvez-moi toutes les propriétés que je veux un slot de 3 jours qui commence à tout moment en mai."

Maintenant, je peux le faire par: 1. Exécution 31 requêtes pour chaque jour de départ potentiel 2. Trouver toutes les réservations en mai dernier, les condenser en un réseau de 31 booléens représentant jours et boucle à travers la recherche de créneaux horaires.

Je suppose que (2) est plus efficace dans la plupart des cas. Y a-t-il de meilleurs algorithmes? Y a-t-il une solution SQL pure?

Je vais utiliser Django et mon jeu de données est petit, donc je vais probablement être OK avec une approche «bête» mais je suis curieux de savoir à quoi ressemble le meilleur algorithme.

Answer 1

probablement surpuissant pour votre application - mais:

Une façon relativement simple d'améliorer vos recherches au détriment de rendre le processus « d'écriture » plus compliquée, serait de changer la table de réservation pour en faire une « disponibilité ' table.

Ajouter dans une colonne booléenne pour indiquer si l'emplacement est libre ou réservé (ou mieux encore mettre dans l'id du client qui l'a réservé, et utiliser 0 si l'emplacement est libre).

Commencez avec une seule place libre, le 1er janvier 2009 -> 31 décembre 20 ?? Lorsque vous obtenez une réservation, divisez l'emplacement libre en 3 (deux insertions et une mise à jour), l'emplacement réservé et les deux emplacements disponibles.

continuer à le faire et que le laps de temps devient plus fragmenté le processus de réservation consistera en une des opérations suivantes:

• Attribution d'une entière « emplacement disponible » à quelqu'un (une mise à jour)
• Fractionnement une 'slot disponible' en deux (une mise à jour et une insertion)
• Diviser une fente en 3 (comme ci-dessus) si quelqu'un réserve la section du milieu d'un emplacement disponible.

Ce n'est pas très compliqué à gérer et le processus de recherche devient une simple requête: trouver des créneaux horaires dans le laps de temps nécessaire qui sont disponibles (réservé = false ou customerid = 0, la façon que vous allez avec elle) où enddate - startdate> = le nombre de jours que vous voulez.

Il double la taille de la table de réservation/disponibilité, et rend les réservations moins simples, mais le compromis est que le processus de recherche est à peu près aussi facile que possible.

Answer 2

Les définitions de tables auraient aidé, mais ici va.Cela devrait fonctionner pour MS SQL Server, mais convertir l'application en MySQL une fois que vous aurez compris l'idée qui la sous-tend devrait être une tâche triviale.

La table Calendrier est juste une table utilitaire standard avec toutes les dates qu'il est utile d'avoir dans votre base de données. Si vous n'en avez pas déjà un, je vous suggère d'en créer un et de le remplir.

CREATE TABLE Calendar 
(
    date  DATETIME  NOT NULL, 
    is_holiday BIT   NOT NULL, 
    -- any other columns that might be relevant for your business 
    CONSTRAINT PK_Calendar PRIMARY KEY CLUSTERED (date) 
) 

Vous devrez alors remplir le tableau avec des dates qui pourraient être significatives pour votre entreprise. Même si vous remontez 100 ans et avancez 100 ans, c'est toujours moins de 75K lignes dans la table et il est groupé sur la date, donc il devrait être rapide et facile de travailler avec. Il simplifie beaucoup les requêtes basées sur les dates.

SELECT 
    P.property_id, 
    C.date 
FROM 
    Calendar C 
JOIN Properties P ON 1=1 
WHERE 
    C.date BETWEEN @search_start_date AND @search_end_date AND 
    NOT EXISTS 
    (
      SELECT 
       * 
      FROM 
       Bookings B 
      WHERE 
       B.property_id = P.property_id AND 
       B.start_date <= DATEADD(dy, @slot_length, C.date) AND -- You would use MySQLs date function 
       B.end_date >= C.date 
    ) 

Ou bien:

SELECT 
    P.property_id, 
    C.date 
FROM 
    Calendar C 
JOIN Properties P ON 1=1 
LEFT OUTER JOIN Bookings B ON 
       B.property_id = P.property_id AND 
       B.start_date <= DATEADD(dy, @slot_length, C.date) AND -- You would use MySQLs date function 
       B.end_date >= C.date 
WHERE 
    C.date BETWEEN @search_start_date AND @search_end_date AND 
    B.booking_id IS NULL