Ja sam priucen za ovu oblast i ono sto nikad nisam naucio je da crtam ER dijagrame (oni rombovi i elipse), tako da to ne umem da nacrtam. Ja to po seljacki odmah pretvorim u tabele. Ko se razume u ER dijagrame, verovatno moze da iz tabela dodje do ER dijagrama. A ako i ne moze, bas me briga, posao odradjujem u tabelama, ne na ER shemi.

Evo dakle ovako:


Ovde postoji jedan odnos medju elementima mreze-grafa, a to je u najjednostavnijem obliku "Cvorovi se nalaze na krajevima grana". Naplasili ste me sa definicijama relacija pa ne smem ni da upotrebim tu rec :-)

E sad kontra pitanje. Nepisano je pravilo da onaj ko postavi 'mozgalicu', a ovo lici na mozgalicu, ima spreman bar deo odgovora. Prema tome, ocekujemo da nam pokazes tvoje vidjenje resenja zadatog problema.

Tabele (evo ni ja ne koristim reč "relacije") su OK. Odgovor na treće pitanje nije dobar jer se traži upit kojim se proverava da li postoji višestruka putanja od čvora X do čvora Y: Kada se krene od čvora X i stigne u čvor Y dobiće se spisak čvorova kroz koje se prošlo. Ovaj spisak je putanja. Vodi računa o tome da graf može biti i nepovezan, npr. sa čvorovima iz tvog primera nepovezani graf je:
(AB), (AC), (CB), (DE), (DF), (EF)

u tvom primeru putanje od čvora A do F su:
ABCF
ADF
ADEF
ADBCF
ADCF

(nadam se da nisam neku zaboravio)...

Ima li ovakav zadatak još neku svrhu osim mentalne gimnastike?

OK, nisam razumeo ono o putanjama. Da izlistas sve moguce putanje do nekog cvora, moguce je. Ne umem to iz glave da uradim ali mislim da moze i znam gde ima da se pogleda, pa cu za koji dan pokusati da pokazem resenje koje radi u MS SQL.

Doduse, ne vidim neki jak razlog da se uopste izlistavaju sve moguce putanje do nekog cvora. Mozda da se nadje koja je najkraca, pa da se nadje najkraci put kroz mrezu? Postoje algoritmi koji dodju do najkraceg/najduzeg puta bez da pronalaze svaku mogucu putanju. Nekako je brze

Ako i ne uspem, verujem da ces nam pokazati ispravno resenje, ako postoji. Ako resenje ne postoji, onda da ne gubimo vreme, lepo kazi ne moze i gotovo. Imao sam druga koji je predavao matematiku u nekoj skoli i kad bi hteo da umiri djake davao im je da nadju nacin da podele ugao na tri dela.....

Ima. Ako zamisliš da graf predstavlja električnu mrežu, traženim SQL upitom dobijaš odgovor da li se neki čvor napaja dvostrano.

Problem najkraće putanje je čuveni problem trgovačkog putnika. Do sada još nije pronađen algoritam koji u polinomijalnom vremenu rešava ovaj problem. Algoritmi koji u eksponencijalnom vremenu rešavaju ovaj problem postaju neupotrebljivi za veći broj čvorova jer se vreme računanja preterano povećava. Zato se ne traži najkraća putanja, već samo da li postoji dvostruka.

Nisam mislio na sam zadatak, već na uslov da se on rešava SQL-om.

Znači to je razlog mojih velikih računa za struju :)

U SQL Serveru? Mislim da nije moguce bez stored procedure jer obican SQL ne moze da radi rekurziju. U Oraclu je lako koriscenjem CONNECT BY.

Oraklov connect by je koristan samo delimično: Sa njim se ne može raditi rekurzija stabla po dubini u proizvoljnom smeru već samo u nekom nedefinisanom Oraklovom maniru. Dakle, u našem zadatku Oraklov CONNECT BY nije upotrebljiv. Uzgred, treba primetiti da rezultat SQL naredbe sa klauzulom CONNECT BY nije relacija (tabela) već stablo.

Koriscenjem klauzule CONNECT BY se dobije nova relacija (tj. tabela a ne stablo). A naravno da Oracle ne bira smer proizvoljno nego mu ti lepo definises sa prior a=b ili prior b=a, tako da ne razumem kako je to delimicno korisno kada se ovaj zadatak sasvim lako resi uz pomoc CONNECT BY, lepo stavis da krene od jednog cvora i da ti da putanje od njega i onda uradis count od onih redova gde se drugi cvor pojavljuje. Naravno, to malo ubrzas tako sto stavis filter da novi cvor nije pocetni i da prethodni cvor nije poslednji. Takodje stavis i da ne ide ciklicno.

Srki, nacrtaj neko stablo, ubaci podatke u Orakl pa probaj da ga sa CONNECT BY izlistaš sleva nadesno i sdesna nalevo. Klauzula PRIOR ti služi samo da definišeš šta je roditelj a šta dete.

Je l' ti pricas o bilo kakvom stablu ili o binarnom stablu gde znas da je nesto levo a nesto drugo desno (uz pomoc nekih atributa ili posebnih kolona)?
Mozes da dodas ORDER SIBLINGS BY na kraju querija i to ce da ti radi onako kako ti zelis.

_{[Ovu poruku je menjao srki dana 18.12.2007. u 10:40 GMT+1]}

Naravno da je bilo kakvo stablo. Ali u okviru čvora možeš da sortiraš odlazeće grane po rastućem (sleva nadesno) ili opadajućem (sdesna nalevo) poretku.

Samo na kraju stavis ORDER SIBLINGS BY value, gde je value atribut po kom poredis cvorove.

Nisam baš siguran da li ova klauzula utiče na redosled iteracija ili samo sortira podređene podatke. Kakvo je tvoje iskustvo?

Naravno da se dobije relacija (pa nisi valjda očekivao da iz Orakla nikne Novogodišnja jelka :-) ), ali je semantika te relacije da je u njoj sakriveno stablo. I u Zidarevom modelu sa dve tabele nalazi se graf. To je ono što vidimo mi ali ne i SQL. Otuda i problem. Nama treba upitni jezik npr. QWERT koji će u tim tabelama videti mrežu.

<sub>[Ovu poruku je menjao Fitopatolog dana 18.12.2007. u 14:32 GMT+1]

[Ovu poruku je menjao Fitopatolog dana 18.12.2007. u 14:33 GMT+1]</sub>

Mozes li da definises 'dvostrano napajanje'? Ako je dvostrano napajenaje isto sto i 'ima vise od dve zice koje dolaze u cvor', to sam ti dao. Nesto mi se cini da pojam dvostrano napajanje ima veze sa dva moguca izvora za celu mrezu. Predlazem da ne idemo tamo, to prestaje da bude cisto akademska teorija grafova i postaje egzaktna inzenjerska disciplina elektrotehnika. Nisu svi na forumu elektroinzenjeri i zapetljacemo se oko detalja i granicnih uslova i opet necemo znati o cemu pricamo.

Sto se tice nalazenja najkraceg puta u mrezi, problem trgovackog putnika je samo jedna varijanta. Vazni prakticni problemi su odavno reseni u praksi i to ne odredjivanjem svih mogucih puteva. Ako si se bavio operacionim istrazivanjima, cuo si za metod kriticnog puta koji se primenjuje u anlizi vrema kod izrade planova (primer MS project network diagram). Tamo se koristi nesto sto se zove Bellmanov algoritam i sluzi da se nadje najkraci put od cvora A do B u orijentisanoj mrezi bez petlji. Ja sam imao srecu da ove stvari slusam od veoma ucenog coveka. Prof. Radivoje Petrovica sa ETF napisao je osamdesetih godina prelepu knjzicu koja se zove 'Operacion Istrazivanja'. Kako sam prof. Petrovic rece 'knjiga je dosta tanka, malo stranica ima, ali se jako sporo cita' Verujem da si se sreo sa ovom knjigom, ako ne, onda je potrazi. Visoka nauka, a veom bliska praksi. Doduse, ne svakodnevnoj praksi, ali ipak praksi. Pusti Codd-a na miru. Nije ni Codd bas svuda potpuno u pravu. Vidim da si aktivan na forumu Fizika, pa pretpostavljam da znas sta je Karnoov ciklus - ono o gasovim i pritisku i temperaturi, na cemu se zasniva rad motora sa unutrasnjim sagorevanjem. To jeste osnova, ali zar mislis da u Toyoti ili Mercedesu ceo dan raspravljaju o Karnoovom ciklusu?

Za proracune elektricnih ili vodovodnih mreza koriste se drugi metodi, torija grafova se samo spomene, tek toliko da se kaze 'mreza je orjentisani graf'. To lepo zvuci, veoma umno i akademski. A onda dodje gospodin Hardy Cross i objavi iterativnu metodu koja od tada (pocetak 20 veka) se primenjuje u teoriji konstrukcija (gradjevinska statika), vodovodnim mrezama i elektricnim mrezama. Posle su Crossa prebacili na racunar, a stigle su i nove metode. Sve nove i stare metode su u stvari metodi resavanja sistema lineranih i/ili nelinarnih jednacina. Ni jedna meni poznata ne koristi teoriju grafova za nesto vise od onoga sto sam ti pokazao u odgovoru na mozgalicu - kako u tabeli prikazati mrezu.

Jos jednom, dacu ti (MS) SQL resenje za listanje svih mogucih puteva u mrezi, ako ga mogu naci u knjigama. Mislim da je Jablan u pravu sto se tice akademskog naklapanja.



Naravno da bi bilo lepo imati jezik QWERT koji ce u tabelama videti mrezu. Posto ga jos nema mi se sluzimo onim sta imamo. SQL inace ne vidi nista. To je kompjuterski jezik kao i svi ostali, napisan u C ili u assembleru i prevodi komade koje mi napisemo. A komande su takve da bolje od ostalih jezika rade operacije sa skupovima. Kad se napravi jezik za rad sa grafovima, mi ce mo i to koristiti kad nam zatreba. Za sada se snalazimo s ovim sto imamo.

Ne razumem, je l' mozes da pojasnis u cemu je problem? Je l' mozes da napises konkretan primer sa ulaznim podacima i onim sta ocekujes na izlazu a da ne mozes to da dobijes uz pomoc SQLa?

Evo najopstiji slucaj, svi moguci putevi u datoj mrezi, svi moguci pravci:

Ako ovo odradite, bez WHERE dobicete 350 redova. Za malecnu mrezu od 6 i 10 grana cvorova. Ne znam da li je ovo tacan broj, resenje sam 'prepisao' iz knjige "Inside Microsoft SQL Server 2005 T-SQL Querying", autori Itzik Ben Gan, Lubor Kollar and Dejan Sarka (nas covek izgleda

I ne pitajte kako ovo u stvari radi. Common Table Expressions....

Resenje u knjizi daje i duzinu svakog puta, sto se ovde nije trazilo ;-). Dakle, izgleda da MS SQL moze da odredi sve moguce puteve u ciklicnom neorjentisanom grafu. Sta cete posle s tim silnim putevima, vas problem. Pokusajte na primer da dobijete iz ovoga najkraci put od A fo F. Bellman to radi mnogo brze i efikasnije.

_{[Ovu poruku je menjao chachka dana 19.12.2007. u 00:33 GMT+1]}

@Zidar: Nisam imao pojma da tako nešto može... Hvala puno na ovom primeru!

Evo jedan članak sa MSDN koji još malo objašnjava ove rekurzivne kverije:

http://msdn2.microsoft.com/en-us/library/ms186243.aspx

Ja sam znao da DB2 ima rekurzivnu WITH klauzulu ali nisam imao pojma da su to ubacili u SQL Server 2005. Ovo je odlicno!

Zidaru, svaka čast na rešenju!

Drugo rešenje, koje ne prolazi nužno kroz sve čvorove bi bilo da se napravi rekurzivna procedura za obilazak čvorova po granama. Ona bi polazila od početnog čvora, usput bi se beležili čvorovi koje je rekurzija obišla. Povratak iz rekurzije je kada se naiđe na čvor koji je već posećen (i naravno kod listova). Kraj je kada se opet dođe do početnog čvora (a već je posećen drugi čvor koji je od interesa) ili ako su posećeni svi čvorovi. Statistički gledano, na ovaj način se u proseku prolazi kroz polovinu čvorova.

U MS SQL 2005 WITH ima i mnoge druge primene, koje se ne bave iteracijama. WITH kreira virtualnu temp tabelu, koja se onda upotrebi prvoj sledecoj naredbi. Ovo uproscuje ili bar cini manje nejasnim mnoge slucajeve gde bi se upotrebili subkveriji ili in-line izkazi.

Sto se tice iteracija, ima primer u Books On Line, nisam siguran da li je identican sa onim iz liknka koji je dao Jablan. Meni se dopao clanak koji je napisao neki Nigel Rivett, tejk sam tu uspeo da razumem delimicno kako cela stvar radi. Lepo se snalazim sa WITH tamo gde mi ne trebaju iteracije, a za iteracije jos uvek trazim primere po literaturi i webu pa enkako prilagodjujem svojim potrebama.

http://www.simple-talk.com/sea...lt.aspx?search=CTE+NIgel+Rivet

G. Rivett je ocigledno dobro potkovan. Pogledajte clanak "Partitioned Tables in SQL Server 2005"

Ako se prašina oko ove teme malo slegla, evo i nešto teorije: Za standardni SQL upitni jezik problem je rad sa objektima koji nisu tabele (da li smem da napišem relacije?) jer običan SQL "ne vidi" hijerarhiju ili mrežu sakrivenu u tabeli (tabelama). Zbog toga su SQLu dodate naredbe ("naočari" za stabla i mreže) za rekurziju (DB2 i MSSQL imaju bolje rešenje od Orakla). Uz prednosti koje su donele, ove naredbe imaju i svoje nedostatke: SQL kod je sada malo teži za razumevanje, postoji opasnost da se sa nekontrolisanom upotrebom preoptereti računar (postavljanje upita koji vrši višak rekurzija), tačan redosled rekurzija nije moguće uvek zadati. Zbog toga treba pažljivo proceniti kada da se ide sa SQL rekurzijom a kada praviti rekurziju peške pomoću procedura.

:-))