none
Suche Denkanstoß bzw. Lösung für folgende Aufgabenstellung RRS feed

  • Frage

  • Irgendwie nicht einfach zu erklären, mal schauen...

    Stelle mal folgende 2 Tabellen vor
    - Standort (Router A, B, C, D, E, F,....)
    - Verbindungen (Router zu Router)
    z.B.

    Anstelle von IP-Adressen verwende ich mal Buchstaben.

    A->B (dieser führt nicht zum Zielpunkt)
    B->C ( - " - )
    B->D ( - " - )
    B->E (dieser führt zum nächsten Router)
    ...
    E->F (dieser führt nicht zum Zielpunkt)
    E->G (dieser führt zum nächsten Router)
    ...
    G->K (dieser führt zum nächsten Router am Ziel)

    Bei Abfrage z.B. Zeige mir alle Verbindungen von A nach K an, sollte als Ergebnis eine Liste des Weges der Strecke mit allen Zwischenstellen von A nach K (ähnlich wie tracert) zurückgeben werden.
    Wie findet man, den Weg der Strecke heraus?

    Wie sollte eurer Meinung nach so etwas aufgebaut werden?

    Dienstag, 22. Dezember 2009 14:46

Antworten

  • Das ist ja wirklich ein interessantes Problem. Ich hatte mich noch nicht intensiver mit gerichteten Graphen beschäftigt, habe aber hier (http://www.zdnet.de/anwendungsentwicklung_gerichtete_graphen_mit_sql_loesen_teil_1_story-20000201-39124191-1.htm) eine Idee bekommen und diese umgesetzt. Bitte mal testen:
    Set Nocount on 
    
    create table t_connection (Start char(1), Ziel char(1));
    
    insert into t_connection values('A','B');
    insert into t_connection values('B','C');
    insert into t_connection values('B','D');
    insert into t_connection values('B','E');
    insert into t_connection values('C','F');
    insert into t_connection values('C','K');
    insert into t_connection values('E','F');
    insert into t_connection values('E','G');
    insert into t_connection values('G','K');
    
    
    
    -- Gesuchte Strecke definieren
    create table t_params (Start char(1), Ziel char(1));
    Insert into t_params (Start, Ziel) values('K','D');
    
    -- Diverse Testaufrufe
    -- update t_params  set Start = 'A', Ziel = 'K';
    -- update t_params  set Start = 'B', Ziel = 'C';
    -- update t_params  set Start = 'A', Ziel = 'D';
    -- update t_params  set Start = 'K', Ziel = 'D';
    -- update t_params  set Start = 'D', Ziel = 'K';
    
    -- Gibt es nicht
    -- update t_params  set Start = 'A', Ziel = 'X';
    
    
    
    create table t_Wege
    (
    Start      char(1),
    Ziel       char(1),
    hops        integer,
    route       varchar(30)
    constraint XPK_t_Wege primary key (Start,Ziel, route)
    );
    
    
    go
    create view v_nexthop
    as
    select src.Start,
    dst.Ziel,
    src.hops+1 hops,
    src.route +',' + dst.Ziel route
    from t_Wege src,
    (select Start, Ziel from t_connection 
    union  
    select Ziel as Start, Start as Ziel from t_connection) dst
    where src.Ziel = dst.Start
    and dst.Ziel != src.Start;
    go
    
    
    Declare @Anzahl	int;
    
    truncate table t_Wege;
    
    -- initial connections
    insert into t_Wege (Start, Ziel, Hops, route)
    select Start,Ziel,1,Start+','+Ziel
    from (select Start, Ziel from t_connection 
    union  
    select Ziel as Start, Start as Ziel from t_connection) a;
    
    Set @Anzahl =@@ROWCOUNT;
    
    While @Anzahl > 0
       begin
    		insert into t_Wege (Start, Ziel, Hops, route)
    		select Start,Ziel,hops,route 
    		from v_nexthop v
    		where not exists (select * from t_Wege t where t.Start = v.Start and t.Ziel = v.Ziel);
    		Set @Anzahl =@@ROWCOUNT;
    	end ;
    
    go
    select * 
    from t_Wege 
    order by Start,Ziel;
    
    Select *
    from t_params;
    
    Select *
    from t_Wege 
    where Start in (select Start from t_params)
    and Ziel in  (select Ziel from t_params);
    
    
    -- Am Ende wieder aufräumen
    go
    Drop Table t_connection;
    Drop Table t_params;
    Drop Table t_Wege;
    Drop View v_nexthop;

    Einen schönen Tag noch, Christoph Muthmann Microsoft SQL Server MVP, http://www.insidesql.org
    • Als Antwort markiert Christoph MuthmannEditor Donnerstag, 7. Januar 2010 13:55
    • Tag als Antwort aufgehoben Billardheld Freitag, 8. Januar 2010 05:33
    • Als Antwort markiert Billardheld Freitag, 8. Januar 2010 09:04
    • Tag als Antwort aufgehoben Billardheld Freitag, 8. Januar 2010 09:09
    • Als Antwort markiert Billardheld Freitag, 8. Januar 2010 09:11
    Donnerstag, 7. Januar 2010 10:57
    Beantworter

Alle Antworten

  • Hallo Herbert,
    da die weitere Diskussion in der Newsgroup stattgefunden hat, sollten wir den Thread hier schliessen.

    http://groups.google.de/group/microsoft.public.de.sqlserver/browse_thread/thread/d5141462325ac79c/417304b942b17c67


    Einen schönen Tag noch, Christoph Muthmann Microsoft SQL Server MVP, http://www.insidesql.org
    Dienstag, 5. Januar 2010 09:22
    Beantworter
  • Hallo Christoph,

    Im Prinzip hast Du recht. 

    Allerdings hab ich noch das Problem über eine Prozedure eine Wegstrecke z.B. von F nach C aufzubauen.

    Wäre schön, wenn ich hierfür noch eine Hilfestellung erhalten könnte.

    Mittwoch, 6. Januar 2010 07:53
  • Hallo Herbert,
    das ist ja nicht so ganz ohne. Ich habe mal versucht das entsprechend kommentiert zu lösen. Achtung: Ich droppe am Ende die angelegten Tabellen und Views wieder! Bitte in einer Testdatenbank ausprobieren.

    Set Nocount on 
    
    create table t_connection (Start char(1), Ziel char(1));
    -- Bedingung ist keine rückwärts gerichtete Verbindung, um Rekursionen zu vermeiden
    insert into t_connection values('A','B');
    insert into t_connection values('B','C');
    insert into t_connection values('B','D');
    insert into t_connection values('B','E');
    insert into t_connection values('C','F');
    insert into t_connection values('C','K');
    insert into t_connection values('E','F');
    insert into t_connection values('E','G');
    insert into t_connection values('G','K');
    
    -- Gesuchte Strecke definieren
    create table t_params (Start char(1), Ziel char(1));
    Insert into t_params (Start, Ziel) values('A','K');
    
    -- Diverse Testaufrufe
    -- update t_params  set Start = 'A', Ziel = 'K';
    -- update t_params  set Start = 'B', Ziel = 'C';
    -- update t_params  set Start = 'A', Ziel = 'D';
    
    -- Gibt es nicht
    -- update t_params  set Start = 'A', Ziel = 'X';
    
    
    
    
    -- Simple-Lösung über n Joins
    select a.Start, a.Ziel, b.Start, b.Ziel, c.Start, c.Ziel, d.Start, d.Ziel
    from t_connection a 
    left join t_connection b on a.Ziel = b.Start
    left join t_connection c on b.Ziel = c.Start
    left join t_connection d on c.Ziel = d.Start
    where a.Start IN (select Start from t_params)
    order by a.Start;
    
    -- http://msdn.microsoft.com/de-de/library/ms186243.aspx
    -- Rekursive Abfragen mithilfe von allgemeinen Tabellenausdrücken
    
    WITH tr (Start, Ziel, Tiefe, Fertig)AS
    (
    -- Ankerelement ist z. B. 'A'
    SELECT t.Start, t.Ziel, 1 as Tiefe, case when t.Ziel IN (select Ziel from t_params) then 'J' else 'N' end as Fertig
    FROM t_connection t
    WHERE t.Start IN (select Start from t_params)
    
    UNION ALL
    -- Verknüpfe mit dem Vorgänger
    SELECT t.Start, t.Ziel, tr.Tiefe + 1 as Tiefe, case when t.Ziel IN (select Ziel from t_params)  then 'J' else 'N' end as Fertig
    FROM t_connection t
    INNER JOIN tr
    ON (t.Start = tr.Ziel)
    )
    SELECT DISTINCT Start, Ziel, Tiefe, Fertig
    FROM tr
    ORDER BY Start;
    
    go
    
    -- Als View dynamisch mit Start aus Parameter-Tabelle
    create view v_Rekursion2 as 
    WITH tr (Start, Ziel, Tiefe, Fertig)AS
    (
    -- Ankerelement ist z. B. 'A'
    SELECT t.Start, t.Ziel, 1 as Tiefe, case when t.Ziel IN (select Ziel from t_params) then 'J' else 'N' end as Fertig
    FROM t_connection t
    WHERE t.Start IN (select Start from t_params)
    
    UNION ALL
    -- Verknüpfe mit dem Vorgänger
    SELECT t.Start, t.Ziel, tr.Tiefe + 1 as Tiefe, case when t.Ziel IN (select Ziel from t_params)  then 'J' else 'N' end as Fertig
    FROM t_connection t
    INNER JOIN tr
    ON (t.Start = tr.Ziel)
    )
    SELECT DISTINCT Start, Ziel, Tiefe, Fertig
    FROM tr;
    go
    
    -- Zeige die View
    Select *
    from v_Rekursion2;
    
    -- Jetzt das ganze rekursiv vom Ende zum Anfang, unter Berücksichtigung der Tiefe
    -- Dann werden die Routen, die nicht am Ziel enden automatisch eliminiert
    -- Das Order by Tiefe führt dazu, dass nur die kürzeste Route ausgegeben wird
    Declare @Start	varchar(1),
    		@Ziel	varchar(1),
    		@Tiefe	int,
    		@Anzahl	int,
    		@Route varchar(100);
    
    -- Suchbedingung zeigen
    Select @Start = Start, @Ziel = Ziel
    from t_params;
    Print 'Gesuchte Route : ';
    Print @Start + ' - ' + @Ziel;
    Print 'Gefundene Route : ';
    
    Select @Start = Start, @Ziel = Ziel, @Tiefe = Tiefe
    from (Select top 1 Start, Ziel, Tiefe from v_Rekursion2 where Fertig = 'J' order by Tiefe ) a;
    
    Set @Anzahl =@@ROWCOUNT;
    If @Anzahl > 0 
    	Set @Route =  @Ziel + '-' + @Start;
    
    While @Anzahl > 0
       begin
    	Select @Start = Start, @Ziel = Ziel, @Tiefe = Tiefe
    	from (Select top 1 Start, Ziel, Tiefe from v_Rekursion2 where Tiefe < @Tiefe and Ziel = @Start) a;
    	Set @Anzahl =@@ROWCOUNT;	
    	If @Anzahl > 0 
    		Set @Route =  @Route + '-' + @Start;
      
       end;
    
    If  @Route is not null
    	Print Reverse(@Route);
    Else
    	Print 'Keine Route vorhanden!';	
    
    
    -- Am Ende wieder aufräumen
    Drop View v_rekursion2;
    Drop Table t_connection;
    Drop Table t_params;
    

    Einen schönen Tag noch, Christoph Muthmann Microsoft SQL Server MVP, http://www.insidesql.org
    • Als Antwort markiert Billardheld Freitag, 8. Januar 2010 09:09
    • Tag als Antwort aufgehoben Billardheld Freitag, 8. Januar 2010 09:09
    Mittwoch, 6. Januar 2010 14:01
    Beantworter
  • Danke für die Unterstützung.

    bei Strecke C nach B liefert die Simple-Lösung ein falsches Ergebnis!

    Auf jedem Fall interessant, aber leider ist das noch keine endgültige Lösung. Da nur in einer Richtung ermittelt wird.

    Probleme wirft z.B. die Strecke K nach D auf und genau da hackt es. Das ist das Schwierige an der Sache zu dem ich noch die Lösung suche.

    • Bearbeitet Billardheld Donnerstag, 7. Januar 2010 06:13 Falsche Beispielstrecke
    Donnerstag, 7. Januar 2010 06:07
  • Das ist ja wirklich ein interessantes Problem. Ich hatte mich noch nicht intensiver mit gerichteten Graphen beschäftigt, habe aber hier (http://www.zdnet.de/anwendungsentwicklung_gerichtete_graphen_mit_sql_loesen_teil_1_story-20000201-39124191-1.htm) eine Idee bekommen und diese umgesetzt. Bitte mal testen:
    Set Nocount on 
    
    create table t_connection (Start char(1), Ziel char(1));
    
    insert into t_connection values('A','B');
    insert into t_connection values('B','C');
    insert into t_connection values('B','D');
    insert into t_connection values('B','E');
    insert into t_connection values('C','F');
    insert into t_connection values('C','K');
    insert into t_connection values('E','F');
    insert into t_connection values('E','G');
    insert into t_connection values('G','K');
    
    
    
    -- Gesuchte Strecke definieren
    create table t_params (Start char(1), Ziel char(1));
    Insert into t_params (Start, Ziel) values('K','D');
    
    -- Diverse Testaufrufe
    -- update t_params  set Start = 'A', Ziel = 'K';
    -- update t_params  set Start = 'B', Ziel = 'C';
    -- update t_params  set Start = 'A', Ziel = 'D';
    -- update t_params  set Start = 'K', Ziel = 'D';
    -- update t_params  set Start = 'D', Ziel = 'K';
    
    -- Gibt es nicht
    -- update t_params  set Start = 'A', Ziel = 'X';
    
    
    
    create table t_Wege
    (
    Start      char(1),
    Ziel       char(1),
    hops        integer,
    route       varchar(30)
    constraint XPK_t_Wege primary key (Start,Ziel, route)
    );
    
    
    go
    create view v_nexthop
    as
    select src.Start,
    dst.Ziel,
    src.hops+1 hops,
    src.route +',' + dst.Ziel route
    from t_Wege src,
    (select Start, Ziel from t_connection 
    union  
    select Ziel as Start, Start as Ziel from t_connection) dst
    where src.Ziel = dst.Start
    and dst.Ziel != src.Start;
    go
    
    
    Declare @Anzahl	int;
    
    truncate table t_Wege;
    
    -- initial connections
    insert into t_Wege (Start, Ziel, Hops, route)
    select Start,Ziel,1,Start+','+Ziel
    from (select Start, Ziel from t_connection 
    union  
    select Ziel as Start, Start as Ziel from t_connection) a;
    
    Set @Anzahl =@@ROWCOUNT;
    
    While @Anzahl > 0
       begin
    		insert into t_Wege (Start, Ziel, Hops, route)
    		select Start,Ziel,hops,route 
    		from v_nexthop v
    		where not exists (select * from t_Wege t where t.Start = v.Start and t.Ziel = v.Ziel);
    		Set @Anzahl =@@ROWCOUNT;
    	end ;
    
    go
    select * 
    from t_Wege 
    order by Start,Ziel;
    
    Select *
    from t_params;
    
    Select *
    from t_Wege 
    where Start in (select Start from t_params)
    and Ziel in  (select Ziel from t_params);
    
    
    -- Am Ende wieder aufräumen
    go
    Drop Table t_connection;
    Drop Table t_params;
    Drop Table t_Wege;
    Drop View v_nexthop;

    Einen schönen Tag noch, Christoph Muthmann Microsoft SQL Server MVP, http://www.insidesql.org
    • Als Antwort markiert Christoph MuthmannEditor Donnerstag, 7. Januar 2010 13:55
    • Tag als Antwort aufgehoben Billardheld Freitag, 8. Januar 2010 05:33
    • Als Antwort markiert Billardheld Freitag, 8. Januar 2010 09:04
    • Tag als Antwort aufgehoben Billardheld Freitag, 8. Januar 2010 09:09
    • Als Antwort markiert Billardheld Freitag, 8. Januar 2010 09:11
    Donnerstag, 7. Januar 2010 10:57
    Beantworter
  • Wow, perfekt. Danke. :-)

    Demnächst bekomme ich die IP-Adressen der mehr als 50 Router, dann teste ich das Script mit echten Daten ;-)

    Einen angenehmen Tag noch.
    Donnerstag, 7. Januar 2010 12:58
  • Prima!
    Ich habe mal meine Antwort als Antwort markiert, damit andere schneller die Lösung finden. Kannst Du das noch bestätigen? Vielleicht schreibe ich dazu auch noch einen Artikel auf insidesql.org!
    Einen schönen Tag noch, Christoph Muthmann Microsoft SQL Server MVP, http://www.insidesql.org
    Donnerstag, 7. Januar 2010 13:56
    Beantworter
  • mmh, was meinst Du mit Bestätigen?

    Habe es zwischenzeitlich mal mit ein paar echten IP-Adressen (bei 34 Verbindungen/1000 Datensätze=Routen) getestet, mit kleinen Änderungen geht das perfekt. Bin gespannt, wie die Geschwindigkeit bei Erstellen der Routen mit Echtdaten ist.

    Bei der Tabelle "t_wege" sollte die Spalte "Route" mehr als 30 Zeichen haben. Denke sogar, das es auch als Beispiel für einen Artikel besser wäre, jeden hops/Step als eigenen Datensatz abzulegen und diese mit einer zusätzliche Spalte "Route-Nr" versehen, damit bei der Spalte "Route" auf keinen Fall die Einträge abgeschnitten werden.

    Falls du Artikel schreibst, hätte ich noch eine Ergänzungsidee ;-)

    SQL Server 2008 hat Unterstützung für GPS-Daten. Somit sollte es doch möglich sein, die Routerstrecken auf eine Landkarte anzuzeigen!?
    Freitag, 8. Januar 2010 06:20
  • Im Gebrauch dieses Web-Forums bin ich auch noch relativ neu. Man hat zum einen die Möglichkeit einen Artikel als Antwort zu markieren und/oder als hilfeich zu bewerten. Alternativ kann man wohl einen Artikel als Antwort vorschlagen, wenn man sich nicht so ganz sicher ist. Bisher ist von den Möglichkeiten in diesem Forum aber nur wenig Gebrauch gemacht worden und irgendwann haben die Moderatoren einen Thread auf "beantwortet" gesetzt.

    Das mit den Routen-Nr funktioniert nicht so einfach, da dann die Ermittlung der Steps wieder schwieriger wird. Der Trick ist ja, dass sukzessive die Routen immer weiter verlängert werden, bis alle möglichen Kombinationen von Start und Ziel erreicht werden. Auf einer Ebene (Anzahl Hops) kann es hierzu mehrere Lösungen geben, eine schlechtere Route zwischen gleichen Punkten wird aber nicht mehr ermittelt.
    Es sollte aber kein Problem sein, die Routen in einem varchar(max) unterzubringen, oder notfalls anderweitig zu splitten oder sogar auszulagern.

    Zu den geographischen Möglichkeiten des SQLServer habe ich mal eine spannende Session von Klaus Aschenbrenner gehört. Bislang hatte ich aber keine Verwendung für solche Konstrukte. Mal schauen, ob ich da noch was ergänzen kann.
    Einen schönen Tag noch, Christoph Muthmann Microsoft SQL Server MVP, http://www.insidesql.org
    Freitag, 8. Januar 2010 07:22
    Beantworter
  • Prima!
    Ich habe mal meine Antwort als Antwort markiert, damit andere schneller die Lösung finden. Kannst Du das noch bestätigen? Vielleicht schreibe ich dazu auch noch einen Artikel auf insidesql.org!
    Einen schönen Tag noch, Christoph Muthmann Microsoft SQL Server MVP, http://www.insidesql.org

    ...und dieser Artikel ist jetzt auch online zu finden unter: http://www.insidesql.org/beitraege/entwicklung/routenfindung-in-graphen

    -- Frank Kalis Microsoft SQL Server MVP Webmaster: http://www.insidesql.org
    Freitag, 8. Januar 2010 12:22
  • Wird im Artikel gut erklärt, super und Danke.

    So nebenbei als Info um welche Erweiterungsmöglichkeit es bei mir geht. Um in einer Webanwendung (Steuerung von Videolive-Stream) eine Bandbreiten-/Kapazitätbeschränkung zu einzurichten ;-)

     

    Freitag, 8. Januar 2010 13:15
  • Zwischenzeitlich sind in der Datenbank über 450 Standorte bzw. Router, was mehr als 250.000 mögliche Routenstrecken entspricht.

    Funktioniert super und nochmal Danke für die Unterstützung.

    Freitag, 6. August 2010 10:26
  • Hallo Herbert,
    vielen Dank für die Rückmeldung. Kannst Du etwas zu der Laufzeit der Auswertung sagen?

    Einen schönen Tag noch,
    Christoph


    Microsoft SQL Server MVP
    http://www.insidesql.org

    Montag, 23. August 2010 13:24
    Beantworter
  • Hallo Christoph,

    Antwort hat etwas gedauert, hatte Urlaub :-)

    Laufzeit ist ja auch abhängig von der Leistungfähigkeit des Rechner/Server.

    Bei ca. 450 Standorte, werden nach deinem Script ca. 250.000 Datensätze bzw. Routenliste angelegt in ca. 5-15 Sekunden.

    Da ich die Routenliste aus den einzelnen Datensätze benötige, also Hops/Step (zusätzliche Spalte "Route-Nr") jeweils als eigenen Datensatz - durchlaufe ich diese Datensätze doch mal um eine entsprechende Tabelle zu erstellen. Diese benötigt dann 1-5 min. um 2.400.000 Datensätze aus den Routenlisten zu erstellen. Denke hier ist noch Optimierung angesagt, Cursor sind sehr langsam :-( .

    Da sich die Routen nicht ständig ändern, sehe ich die Laufzeit noch zweitrangig.

    Reicht Dir das als Info oder willst Du mehr wissen? Gern auch per PM.

    Gruß
    Herbert 

    Montag, 6. September 2010 12:39
  • Hallo Herbert,
    das hört sich doch erst mal gut an! Ich werde bei Gelegenheit meinen Artikel um die Info ergänzen.

    Freut mich, dass es so gut funktioniert!

    Einen schönen Tag noch,
    Christoph


    Microsoft SQL Server MVP
    http://www.insidesql.org/blogs/cmu

    Montag, 6. September 2010 13:45
    Beantworter
  • Hallo Christoph,

    Das liest sich, als würde die Laufzeit in Ordnung sein :-)).

    Demnächst installiere ich neu, dann kann ich Dir auch die Werte aus dem SQL-Profiler mitteilen, wenn gewünscht.

    Noch eine Anregung und Hilfe für mich ;-) , die in Deinem Artikel Platz finden sollte: wie für jeden Hops/Step mit zusätzlicher Spalte "Route-Nr" je als eigenen Datensatz in einer extra Tabelle optimal erstellt werden könnte.

    Herzlichen Gruß
    Herbert

    Montag, 6. September 2010 14:31
  • Prima!
    Ich habe mal meine Antwort als Antwort markiert, damit andere schneller die Lösung finden. Kannst Du das noch bestätigen? Vielleicht schreibe ich dazu auch noch einen Artikel auf insidesql.org!


    Einen schönen Tag noch, Christoph Muthmann Microsoft SQL Server MVP, http://www.insidesql.org


    ...und dieser Artikel ist jetzt auch online zu finden unter: http://www.insidesql.org/beitraege/entwicklung/routenfindung-in-graphen

    -- Frank Kalis Microsoft SQL Server MVP Webmaster: http://www.insidesql.org

    Der Link stimmt nicht mehr und hat sich geändert. Ist unter

    http://www.insidesql.org/blogs/cmu/sql_server/routenfindung-in-graphen

    zu finden.

    Montag, 14. Mai 2012 09:57