Database for lenge mellom steder

[ntec]

 

Hvordan lager jeg en database for lengen på strekningen mellom hver plass på best mulig måte? Man må ta hensyn til at nye plasser kan tilføyes. (Ta hensyn til at det kan hende at jeg skal legge til 50 steder i databasen)

 

Det skal lages i mySQL, og spørringene skjer via php. Per i dag koder jeg begge delene i notisblokk og ikke via program. Jeg har phpMyAdmin tilgjengelig.

 

Versjoner:

phpMyAdmin: 2.6.1

tror jeg har php 5 eller noe sånt. ikke sikker

Endret 10. mai 2006 av ntec

[siDDis]

Eit tips, blir det ikkje betre om du designer kvar *veg* til ein plass du må forbi uansett. Så feks du slår sammen alle vegene mellom oslo og bodø sånn at det blir oslo + lillehammer + trondheim + bodø = veglengda mellom oslo og bodø?

 

Så må du ha ein tabell som legger inn veger der du har framandnøklar som er byene.

 

Feks ein tabell som inneheld vegen mellom oslo og lillehammer

 

pk_id

fk_fra_by_id

fk_til_by_id

vei_lengde

[ntec]

pk_id

fk_fra_by_id

fk_til_by_id

vei_lengde

6075863[/snapback]

ok:)

men forklar dette litt mer:P

[ntec]

Eit tips, blir det ikkje betre om du designer kvar *veg* til ein plass du må forbi uansett. Så feks du slår sammen alle vegene mellom oslo og bodø sånn at det blir oslo + lillehammer + trondheim + bodø = veglengda mellom oslo og bodø?

 

Så må du ha ein tabell som legger inn veger der du har framandnøklar som er byene.

 

Feks ein tabell som inneheld vegen mellom oslo og lillehammer

 

pk_id

fk_fra_by_id

fk_til_by_id

vei_lengde

6075863[/snapback]

Vil dette si at en database med:

bodø, narvik, fauske, drag og hamarøy se slik ut?

 

vei_id    fk_fra_by_id    fk_til_by_id    vei_lengde

1            bodø          narvik            350

2            narvik        bodø              350

3            drag            bodø            200

4            bodø            drag              200

5            narvik          drag              150

6            drag            narvik            150

7            hamarøy      bodø              220

8            bodø            hamarøy        220

9            hamarøy        narvik            130

10            narvik          hamarøy        130

11            hamarøy      drag              20

12            drag            hamarøy        20

13            fauske          bodø              60

14            bodø            fauske          60

15            fauske          narvik          290

16            narvik          fauske          290

17            fauske          drag            140

18            drag              fauske          140

19            fauske          hamarøy        160

20            hamarøy        fauske          160

[siDDis]

ja det er eit eksempel, men du trenger ikkje all den dataen. Du må bruke ein betre datastruktur, ein veg mellom 2 byer skal maks bruke 1 rad. Eg er ikkje heilt sikker på korleis eg skal få løst det idag, sitter på ein anna oppgåve som skal leveras om 2 timer. Får sjå etter då

[ntec]

ja det er eit eksempel, men du trenger ikkje all den dataen. Du må bruke ein betre datastruktur, ein veg mellom 2 byer skal maks bruke 1 rad. Eg er ikkje heilt sikker på korleis eg skal få løst det idag, sitter på ein anna oppgåve som skal leveras om 2 timer. Får sjå etter då

6077717[/snapback]

okei men si i fra når du har tid da:)

[siDDis]

Ok nå har eg ein løsning som du kan jobbe videre med.

 

Eg skriver alt korleis eg gjorde det i PostgreSQL så kan du prøve og forstå korleis det fungerer

 

CREATE TABLE Byer (
       by_id SERIAL NOT NULL,
       navn VARCHAR(32),
       PRIMARY KEY (
               by_id
       )
);

CREATE TABLE Veier (
       vei_id SERIAL NOT NULL,
       verdi FLOAT NOT NULL,
       PRIMARY KEY (
               vei_id
       )
);

CREATE TABLE byvei (
       by_id INTEGER NOT NULL,
       vei_id INTEGER NOT NULL,
       id SERIAL NOT NULL,
       PRIMARY KEY (
               id
       )
);


ALTER TABLE byvei
       ADD
       FOREIGN KEY (
               by_id
       )
       REFERENCES Byer (
               by_id
       );

ALTER TABLE byvei
       ADD
       FOREIGN KEY (
               vei_id
       )
       REFERENCES Veier (
               vei_id
       );



CREATE INDEX FK1_Byer_byvei ON byvei (
       by_id
);

CREATE INDEX FK2_Veier_byvei ON byvei (
       vei_id
);

 

 

INSERT INTO veier (verdi)
VALUES(20);
INSERT INTO veier (verdi)
VALUES(35.5);
INSERT INTO veier (verdi)
VALUES(52.2);

INSERT INTO byer (navn)
VALUES('Oslo');
INSERT INTO byer (navn)
VALUES('Lillehammer');
INSERT INTO byer (navn)
VALUES('Trondheim');
INSERT INTO byer (navn)
VALUES('Bodø');

INSERT INTO byvei(by_id, vei_id)
VALUES(1,2); 
INSERT INTO byvei(by_id, vei_id)
VALUES(2,1);
INSERT INTO byvei(by_id, vei_id)
VALUES(2,2);
INSERT INTO byvei(by_id, vei_id)
VALUES(3,2);
INSERT INTO byvei(by_id, vei_id)
VALUES(3,3);
INSERT INTO byvei(by_id, vei_id)
VALUES(4,3);

 

 

SELECT SUM(verdi) FROM veier WHERE vei_id IN (
SELECT vei_id
FROM byvei WHERE by_id = 1 OR by_id = 2 OR by_id = 3
);

 

sum = 107.7

 

Løsninga mi er sikkert ikkje noko særleg optimal, men det var det beste eg greide å tenkja ut. Det som er viktig er at du kjenner alle 'nodene' mellom veiane for å kunne rekne ut lengda.

 

 

Skal du lage det meir komplisert så må du begynne å tenkja over korleis datastrukturen "graph" fungerer. Det er ein datastruktur med noder som peker til mange andre noder som igjen peiker til mange andre noder.

 

Putter du inn i tillegg Bergen mellom Oslo og Trondheim så er det viktig å tenkja lurt og logisk for å rekna deg fram. Du må sjekke begge veiane om kva av dei som er kortast.

 

***EDIT***

Nå begynner eg å tenkja rimeleg altfor komplisert her. Nå må eg vera på det nivået der eg lager meir feil enn rette ting som eg produserer hehe. Det du og sjølvsagt kan gjere er å leggja inn ein eigen heil 'veg' mellom byane så lenge du kjenner heile lengda.

Då blir det ein god del lettare og du slepp å tenkja for avansert.

Endret 10. mai 2006 av siDDIs

[ntec]

har du testet denne?

[ntec]

Skal du lage det meir komplisert så må du begynne å tenkja over korleis datastrukturen "graph" fungerer. Det er ein datastruktur med noder som peker til mange andre noder som igjen peiker til mange andre noder.

 

Hvor finner jeg informasjon om det?

[ntec]

fikk flg feilmelding.

#1064 - You have an error in your SQL syntax.  Check the manual that corresponds to your MySQL server version for the right syntax to use near 'SERIAL NOT NULL,

navn VARCHAR(32),

PRIMARY KEY (

by_id

)

)

[siDDis]

MySQL bruker INTEGER AUTO_INCREMENT, ikkje SERIAL

[ntec]

 

Det er slik infrastrukturen ser ut nå, hvis jeg har forstått systemet ditt rett?

 

Og hvis jeg skal fra Bodø til Lillehammer, så må jeg igjennom trondheim, ikke sant?

 

Men det store spørsmålet: jeg forsto meg ikke på spørringen du lagde for å hente ut info

Endret 11. mai 2006 av ntec

[roac]

For informasjon om slike problemstillinger, Joe Celko har skrevet en bok om trees and hierarchies, som kan være til god hjelp.

 

Videre så kan jeg ikke dy meg: Common Table Expressions i IBM DB2 / SQL Server 2005 gjør jobben vannvittig mye enklere Slike problemstillinger som presenteres her er for en lek å regne i SQL Server 2005.

[siDDis]

Nå beveger me oss inn på eit nivå der MySQL er eit godt stykke ifrå.

 

I PostgreSQL så har du PostGIS http://www.postgis.org/

 

Informasjon og eksempler finner du her

 

http://postgis.refractions.net/files/OSDB2...resentation.ppt

http://www.cs.umn.edu/research/shashi-grou...ialQueries.html

 

Eg har aldri prøvd det men det virker utroleg kjekt å lære seg. Tipper eg kjem til å setje meg ned med det til sommeren når eg får litt betre tid. Nå er det andre fag som må prioriteras.

Endret 15. mai 2006 av siDDIs

[ntec]

Omg.. mye å sette seg inn i.

 

Noen som er interessert i å gjøre den jobben for meg? Å lage en database av veistruktur. Jeg kan betale for jobben.

 

Men det er et krav: det må være lagt til et grensesnitt for å legge til nye veier

 

Svar på dette innlegget om dette høres interessant ut. Jeg bruker mysql.

[roac]

For det første, beklager å skuffe deg, men denne jobben tar jeg ikke på meg. I hvert fall ikke med MySQL

 

En artig problemstilling med denne er følgende (tallene er ikke nøyaktige, jeg har de med for "illustrasjonen sin del":

 

1. Røros-Trondheim: 15 mil

2. Hamar-Oslo: 15 mil

3. Oslo-Trondheim: 60 mil.

 

Med disse dataene i en slik databaseløsning vil resultatet sannsynligvis bli at at Hamar-Røros er ca 90 mil, mens det i realiteten er ca 30. Sannsynligvis er dette en av de faktorene som gjør at karttjenester har det med å komme med litt merkelige forslag i ny og ne. Og dessverre: Det er noe som MÅ tas i betraktning i en slik løsning som du skisserer.

[siDDis]

Men nå skulle ikkje database systemet hans vere så utroleg komplisert og stort då.

 

Gjer det enkelt, legg heller inn ferdig rekna strekninger. Då funker MySQL ypperlig.

[ntec]

Hm, skal på multiLAN i Bodø på torsdag eller fredag, kan kanskje få hjelp hos han som har laget fettnerd.org

[Manfred]

Som det ble sagt vil den mest optimale løsningen være å sette deg inn i hvordan datatypen "graf" fungerer, da det er nettopp denne datatypen som er tilpasset denne type jobber.

[Jørgen E]

For det første, beklager å skuffe deg, men denne jobben tar jeg ikke på meg. I hvert fall ikke med MySQL

 

En artig problemstilling med denne er følgende (tallene er ikke nøyaktige, jeg har de med for "illustrasjonen sin del":

 

1. Røros-Trondheim: 15 mil

2. Hamar-Oslo: 15 mil

3. Oslo-Trondheim: 60 mil.

 

Med disse dataene i en slik databaseløsning vil resultatet sannsynligvis bli at at Hamar-Røros er ca 90 mil, mens det i realiteten er ca 30. Sannsynligvis er dette en av de faktorene som gjør at karttjenester har det med å komme med litt merkelige forslag i ny og ne. Og dessverre: Det er noe som MÅ tas i betraktning i en slik løsning som du skisserer.

6127339[/snapback]

 

Dette løser seg litt vel gjennom å bruke graf som datastruktur. Med disse dataene vil nødvendigvis hamar ligge mellom oslo og røros:

 

 

Oslo ------- Hamar ------------- Røros --------- Trondheim

 

Ergo, kalkulerer du avstanden fra den avreisenoden din i grafen, Hamar, til målnoden din, Røros. I dette tilfellet vet du ikke denne avstanden, du har en case med grafen din. Her trenger du en algoritme for å finne denne.

 

Skulle du f.eks. fra hamar til tr.heim, så ville du lagt sammen 30 mil fra hamar til røros og 15 til fra røros til tr.heim, for en total på 45 mil.

 

Men, hvordan du skal representere grafer i databaser, er litt for stort til å gå inn på her, sorry Google is your friend!