SQL Mozgalice, mozgalica broj 4

Postoji vip restoran u koji menadzeri raznih kompanija dovode svoje poslovne partnere, kolege i clanove upravnih odbora...Nazalost taj restoran ima ogranicen kapacitet (recimo 200 osoba) i zbog toga svaka osoba mora da se unapred najavi, da kaze vreme kada ce biti tu i koliko osoba dovodi (ukljucujuci i sebe)
Tabela vip_restoran koja sadrzi vremena dolaska i odlaska odredjenih grupa osoba koje dovodi vip_customer.


Zamislimo da ja hocu da povedem mojih p_number kolega u taj restoran izmedju p_start_time i p_end_time. (p je prefiks koji oznacava parametar zbog lakseg citanja koda). Sada postoji problem ako se to ubaci u tabelu jer moze da se desi da u nekom trenutku bude vise od 200 osoba u restoranu. Stoga nama treba query koji ce da u tabelu vip_restoran ubaci (p_customer_id, p_start_time, p_end_time, p_number) samo ako to kapacitet restorana dozvoljava (znaci ne sme da bude vise od 200 osoba u nekom trenutku). Da vas sad vidim :-)

@srki, problem je jako interesantan, ali ako sam ja dobro shvatio problem imamo tabelu "destinaciju", ali nam nedostaje tabela iz koje radimo INSERT, pa te molim samo da ako je ovo tacno da nam das i podatke o "izvornoj" tabeli, ili si to mislio da se resi preko Stored Procedure koja ima 4 navedena parametra? Dakle, samo malo dodatnog pojasnjenja

Glupo pitanje:

Mogu li se koristiti trigeri?

---

Moze, koristi sta god hoces.



Recimo da imas 4 parametra u stored procedure i treba da napises naredbu (po mogustvu standardni sql, ne pl/sql) koja ce da ti ubaci novi podatak u tabelu ako je u skladu sa kapacitetom restorana.

Jos objasnjenja za one koji nisu shvatili.
Neka u tabeli trenutno imamo ovo:


Tu vidimo da ni u jednom trenutku nema preko 200 gostiju u restoranu. Ako bismo hteli da bukiramo 60 gostiju od 2:30 do 5 onda to ne bi moglo da se desi jer bi od 4 do 4:15 bilo ukupno 28+130+60=218 gostiju a kapacitet je samo 200. To znaci da treba da odbijemo to bukiranje i da ga ne ubacimo u tabelu.

Mala pomoc: probajte da smislite kako biste algoritamski resili ovaj problem na najefikasniji nacin.

OK, znaci:

... je zadatak, a ne:


Nisam se bezveze zakacio za ovo, jer kod ovog problema nije svejedno kada insertujes vise redova (I verzija zadatka, preko query), ili samo jedan red (II verzija, preko procedure).

A sad na posao

Da, treba mi nesto kao INSERT WHEN condition THEN INTO vip_restoran VALUES (p_customer_id, p_start, p_end, p_broj) a fora je samo naci taj condition.

Zadatak se svodi na pronalazenje ukupnog broja ljudi u bilo kom trenutku zadatog intervala (p_start, p_end)

Prohvaticu dizajn tabele ovakav kakav jeste, uz jednu dopunu: Zakazivanje je an svakih 15 miuta. ne mozete zakazati ud 1:43PM do 5:27PM, ali moze 1:45PM do 5:30PM. ovo nece uticati na opstost resenja, ali ce biti lakse da se shvati.

Onda cu da u igru uvedem tabelu koju sam nazvao DanPo15Minuta. tabela ima dve kolone: (Od,Do) i obe su DateTime tipa. Tabela ima 24*4 = 96, redova, po jedan za svakih 15 minuta u danu. Ovako pocinje:

Od Do
12:00:00 AM 12:15:00 AM
12:15:00 AM 12:30:00 AM
12:30:00 AM 12:45:00 AM
12:45:00 AM 1:00:00 AM
1:00:00 AM 1:15:00 AM
1:15:00 AM 1:30:00 AM
1:30:00 AM 1:45:00 AM
1:45:00 AM 2:00:00 AM
2:00:00 AM 2:15:00 AM

a ovako zavrsava:

Od Do
10:30:00 PM 10:45:00 PM
10:45:00 PM 11:00:00 PM
11:00:00 PM 11:15:00 PM
11:15:00 PM 11:30:00 PM
11:30:00 PM 11:45:00 PM
11:45:00 PM 12:00:00 PM

Onda cu tabelu vip_restoran da "explodiram", tako sto cu za svaki interval (strt_time, end_time) da prikazem sve cetvrtine sata (15 min) koji pripadaju tom intervalu. Interval od 2pm do 6pm prikazao bi se ovako:

vip_cutomer_id start_time Od Do end_time broj_musterija_koje_customer_dovodi
63 2:00:00 PM 3:15:00 PM 3:30:00 PM 6:00:00 PM 130
63 2:00:00 PM 2:00:00 PM 2:15:00 PM 6:00:00 PM 130
63 2:00:00 PM 2:15:00 PM 2:30:00 PM 6:00:00 PM 130
63 2:00:00 PM 2:30:00 PM 2:45:00 PM 6:00:00 PM 130
63 2:00:00 PM 3:00:00 PM 3:15:00 PM 6:00:00 PM 130
63 2:00:00 PM 5:45:00 PM 6:00:00 PM 6:00:00 PM 130
63 2:00:00 PM 3:30:00 PM 3:45:00 PM 6:00:00 PM 130
63 2:00:00 PM 3:45:00 PM 4:00:00 PM 6:00:00 PM 130
63 2:00:00 PM 5:00:00 PM 5:15:00 PM 6:00:00 PM 130
63 2:00:00 PM 5:30:00 PM 5:45:00 PM 6:00:00 PM 130
63 2:00:00 PM 2:45:00 PM 3:00:00 PM 6:00:00 PM 130
63 2:00:00 PM 5:15:00 PM 5:30:00 PM 6:00:00 PM 130
63 2:00:00 PM 4:45:00 PM 5:00:00 PM 6:00:00 PM 130
63 2:00:00 PM 4:30:00 PM 4:45:00 PM 6:00:00 PM 130
63 2:00:00 PM 4:15:00 PM 4:30:00 PM 6:00:00 PM 130
63 2:00:00 PM 4:00:00 PM 4:15:00 PM 6:00:00 PM 130

Ako ovako uradim za sve zadate intervale, mogu da uradim

GROUP BY Od, Do, SUM(broj_musterija_koje_customer_dovodi)

i to ce mo dati za svaki interval od 15 minuta koliko ljudi ima u restoranu.

Kveri koji pokazuje ukupan broj ljudi po intervalu od 15 minuta izgleda ovako (Access, ali mislim da ce raditi svuda):

CREATE VIEW vip_restoran_exp
AS
SELECT
DanPo15Minuta.Od
, DanPo15Minuta.Do
, Sum(vip_restoran.broj_musterija_koje_customer_dovodi) AS SumOfbroj_musterija_koje_customer_dovodi
FROM vip_restoran, DanPo15Minuta
WHERE (((DanPo15Minuta.Od)>=[start_time]) AND ((DanPo15Minuta.Do)<=[end_time]))
GROUP BY DanPo15Minuta.Od, DanPo15Minuta.Do;

Onda kreiram jos jednu pomocnu tabelu, vip_to_test, gde cu da drzim parametre. Identicna struktura kao vip_restoran, i samo jedna red dozvoljen. Unesem moje parametre pa onda tu tabelu takodje explodiram, na slican nacin:

CREATE VIEW vip_to_test_exp
AS
SELECT vip_to_test.Id, vip_to_test.vip_cutomer_id, vip_to_test.start_time, DanPo15Minuta.Od, DanPo15Minuta.Do, vip_to_test.end_time, vip_to_test.broj_musterija_koje_customer_dovodi
FROM vip_to_test, DanPo15Minuta
WHERE (((DanPo15Minuta.Od)>=[start_time]) AND ((DanPo15Minuta.Do)<=[end_time]));

Ovde mi ne treba GROUP BY posto imam tacno jedan red u tabeli vip_to_test.

Sada ova dva view-a JOINujem po paru (Od,Do) ovako:

SELECT
vip_restoran_exp.Od
, vip_restoran_exp.Do
, vip_restoran_exp.SumOfbroj_musterija_koje_customer_dovodi
, vip_to_test_exp.broj_musterija_koje_customer_dovodi
, [SumOfbroj_musterija_koje_customer_dovodi]+[broj_musterija_koje_customer_dovodi] AS Total
FROM vip_restoran_exp
INNER JOIN vip_to_test_exp
ON (vip_restoran_exp.Do = vip_to_test_exp.Do)
AND (vip_restoran_exp.Od = vip_to_test_exp.Od);

Ovaj SELECT mozeet da upotrebite da vidite da li ce dodavanje nove grupe premasiti dozvoljeni broj posetilaca.

Ako vam se interval od 15 minuta cini nedovoljno finim, napravite tabelu koja sadrzi svaki minut u danu, ili svaku sekundu cak i dbicete sta vam treba.

Komentar na datu tabelu vp_restoran: iz dizajna tabele sledi da se posete zakazuju u jednom danu, i da se restoran zatvara najkasnije u ponoc, 24:00.

Ako bi u igru uveli i datumski deo timestampa, kveriji bi se donekle zakomplikovali i to je sve. Ako uvedete cele datume u igru, mozete ovo resenje da primenite na hotele i rezervacije soba, sa pomocnom tabelom koja sadrzi sve dane u narednih 50 godina na primer.

Zakacio sam Access fajl, gde se vide kveriji i primer. Zavrsni kveri je vip_to_test_exp_show_total, a on se dobija od vip_restoran_exp i vip_to_test_exp. A njih dva smo objasnili u tekstu.
Postoji i kveri vip_restoran_exp_long, koji je samo demonstracija da se lakse shvati proces "exsplodiranja" vremenskih intervala.

Toliko od mene. Sigurno moze i elegantnije, ali je meni ovo najlakse da pratim i da objasnim.

Kako ide ona statra "jedna slika hiljadu reci" :)



Objasnjenje:

Plave linije oznacavaju ono sto se vec nalazi u tabeli
Crvena oznacava ono sto hocemo da dodamo

start = pocetna vrednost plave linije
end = krajnja vrednost plave linije

insert start = pocetna vrednost crvene linije
insert end = krajnja vrednost crvene linije

Slika se gleda tako sto se za svaku vrednost uporedjuje pocetne i krajnje vrednosti (oni obojeni pravouganici)
Rezultat prva dva pravouganika se racuna sa OR pa se zatim taj rezultat sa AND racuna sa trecim pravouganikom. Mislim da je jasno. Nadam se da nisam pogresio :)

znaci uslov bi trebalo da bude

E, ovaj Zidar me uvek pretekne

Zidar, ovo sa zakazivanjem sam uzeo kao primer, konkretno mi smo imali slucaj sa nekakvim donacijama gde nista nije smelo da bude preko 100% a donacije su mogle poceti od bilo kog trenutka vremena (kada korisnik klikne ok na jedno dugme u web browseru) tako da resenje treba da radi i kada mozes da zakazes u 2h:32m:56.42342s.

Ako ides na cetvrtu decimalu sekunde, onda se verovatno predlozeni metod ne isplati. :-(

Testirano na PostgreSQL 8.1

Evo upit koji vraca raspoloziv broj slobodnih mesta:

U upit sam ubacio parametre:
p_max_number = maksimalan kapacitet restorana
p_start_time = startno vreme zeljene rezervacije
p_end_time = krajnje vreme zeljene rezervacije
Naravno pre izvrsavanja upita parametri se moraju zameniti konkretnim vrednostima

Upit vraca broj raspolozivih mesta u zadatom intervalu i sa zadatim kapacitetom. Ovaj upit se lako moze ubaciti u trigger ili stored procedure.

Upit se oslanja na standardnu operaciju sa vremenskim intervalima OVERLAPS, s tim da treba napomenuti da se po SQL standardu vremenski intervali uzimaju kao poluotvoreni skupovi, to jest start_time pripada intervalu, ali interval konvergira ka end_time.

Primer za parametre:
p_max_number = 200
p_start_time = '13.03.2007 22:04:21'
p_end_time = '13.03.2007 23:14:15.1400'
upit izgleda:

---

@negyxo: Izgleda da nisi lepo procitao zadatak. Za svaki taj pravougaonik imas razlicit broj osoba i onda u svakom trenutku moras da saberes te osobe iz svih pravougaonika koji prolaze kroz taj trenutak da bi izracunao koliko ti je popunjeno mesta u restoranu u tom trenutku.

@Zidar:
Pa da, ja sam ovo radio za neke finansijske transakcije kod kojih se obavezno cuva timestamp. Te transakcije ti daju neku nagradu u poenima i korisnik moze da izabere da odredjen procenat te nagrade da nekome i onda pre nego sto uradi transakciju na internetu on moze da klikne da hoce da radi donacije nekome i onda moramo makar sekunde da pamtimo. Posto donacije mogu da se stave da vaze i vise godina i da pocnu od odredjenog dana onda ne mozemo da idemo sekundu po sekundu da bi smo pokrili nekoliko godina unapred. Cak i da pamtimo po danima opet bi bilo sporo da gledamo za svaki dan unapred nekoliko godina jer se dosta korisnika kaci na bazu u isto vreme i za sve njih mi treba da racunamo da donacije od njih ne smeju da predju 100%.

_{[Ovu poruku je menjao srki dana 13.03.2007. u 23:38 GMT+1]}

Nije mi jasno. TIMESTAMP tip podataka podrazumeva datum + vreme. Da li to znaci da je Microsoft i ovde napravio neslanu salu sa nepridrzavanjem standarda?

---

Ma ne, to sam ja lupio vrednosti, naravno da se pamti i dan i vreme. MSSQL nikad ni nisam koristio tako da ne znam kako je to tamo implementirano. Koristim Oracle.

Ovo mi izgleda dobro ali mislim da treba umesto

da stoji

A evo kako sam ja uradio. Selektovao sam sve start_time i end_time u jednu kolonu i sortirao po vremenu. U drugu kolonu sam stavio broj musterija kada upisujem start_time a negativan broj musterija kada upisujem end_time. Onda sam samo isao po redu i sabirao i gledao da taj running sum ne bude veci od 200 ni u jednom trenutku.


Ako je rezultat manji od 200 onda mozemo da ubacimo taj booking u schedule. Ovo resenje radi u svim bazama koje podrzavaju sql-2003 standard jedino treba promeniti from dual (Oracle) u odgovarajuci ekvivalent u drugim bazama.

_{[Ovu poruku je menjao srki dana 14.03.2007. u 02:12 GMT+1]}

@srki: Interesantno resenje, mada si nam ga rano prezentovao. Jos se o ovoj mozgalici moglo diskutovati.

Sto se tice komentara za izmenu mog upita nisi u pravu. U sustini mog upita je takodje ideja da se pohvataju tacke u kojima se desavaju promene, sto se radi sa:

Pored ovih tacaka mi je bilo bitno da uhvatim i zavrsetak poslednjeg perioda, sto je uradjeno sa MAX:

Vremenski intervali koje sam dobio pokrivaju interval [MIN(start_time), MAX(end_time)), ali se medjusobno preklapaju. Cini mi se da ovo preklapanje ne utice na krajnji rezultat, pa se vise nisam ni trudio da dobijem intervale koji se ne preklapaju (a da zadrze potpuno pokrivanje intervala [MIN(start_time), MAX(end_time))).

Ono sto tvoja sugerisana izmena nije uspela da obezbedi je da dobijeni intervali potpuno pokriju interval [MIN(start_time), MAX(end_time)).

---

Evo da i ja probam, rešenje koje radi na MSSQL:

1. Ideja je u tome da u proizvoljnom trenutku možemo saznati broj slobodnih mesta, tako što napravimo sumu svih dolazaka i onda oduzmemo sumu svih odlazaka čije vreme je manje-jednako od traženog. Evo udf koji nam to radi:



Sad određujemo koji su nam trenutci važni, odnosno u kojima proveravamo stanje u restoranu. Očigledno, trebamo proveriti koliko je ljudi u restoranu na početku traženog intervala, i koliko je na kraju. Dalje nas zanima svaki trenutak unutar traženog intervala.
SQL koji to radi:



Dakle, dobili smo sve "zanimljive" trenutke kad se nešto dogodilo, i stanje u svakom od njih. Sad je potrebno samo proveriti da li su stanja dovoljno mala da dozvoljavaju unos nove grupe, i na osnovu toga izvšiti unos.

Još jedna stvar: ako je rešenje sporo, može se optimizovati na par načina:
1. Uvesti check-pointe, pa se ne mora računati suma za celu tabelu nego od zadnjeg poznatog stanja (na primer u restoranu smo sigurni da je stanje svaki dan u 5:00 = 0, pa nam je to check-point)
2. Kad izračunamo početno stanje, to možemo proslediti kao dodatni parametar funkciji, pa da ona računa samo promenu stanje a ne sve ispočetka.

ss.

---

Mozda nisam dobro procitao ali lepo jesam
Cekaj, zar tebi ne treba da u momentu kada hoce neko da ti dodje u restoran - da se prebroje gosti u tom momentu koji se nalze u restoranu i ako broj gostiju, zajedno sa gostima koji dolaze premasuje kapacitet restorana - onda se ovi novi gosti odbacuju?

Ako je tako onda ne vidim u cemu je problem sa onim resenjem koje sam dao (jedino sto izgleda naivno ).

Evo procedura pa probaj nad podacima ako meni ne verujes



Mala primedba u vezi procedure
Koristio sam float umesto timestamp, posto timestamp znaci nesto drugo na SQL Serveru.

@negyxo
Pogledaj ovu sliku iz attachmenta. Mislim da tvoje rešenje ne obuhvata taj slučaj koji sam zaokružio, doduše možda grešim. Meni izgleda da ti samo sabereš sve u datom intervalu, ali ne vodiš računa da se u međuvremenu prostor oslobađa, tj. ljudi odlaze i prave mesto za nove. Ili sam ja sve pogrešno razumeo :)

---