Re: XQuery question
From: Sebastian Schaffert <schaffer_at_informatik.uni-muenchen.de>
Date: Fri, 16 May 2003 17:23:16 +0200
Message-ID: <ba2vv6$ng4$1_at_minotaurus.cip.informatik.uni-muenchen.de>
>
> There are a million-and-one uses. I suggest you Google on Djikstra
> or Floyd-Warshall algorithms. Undoubtedly, you can come across pages
> that explain the algorithms and how they may be applied. Common student
> examples are network routing, the Travelling Salesman problem,
> scheduling, etc...
>
Undoubtedly there are such problems. On the other hand, they are usually not represented in relational databases, because they lack the efficiency for such calculations. I've never seen Dijkstra's algorithm applied to a graph which is represented in a relational database.
>
> Define "well-suited"? Performance? Maintainability? Data
> integrity? Ease of use? What is "well-suited" to you might not be "well-
> suited" to others...
- Ease of use: SQL is not expressive enough to calculate graph algorithms, so you'll need to embed it in a foreign language anyway (and thus again lose performance).
Date: Fri, 16 May 2003 17:23:16 +0200
Message-ID: <ba2vv6$ng4$1_at_minotaurus.cip.informatik.uni-muenchen.de>
Paul Tiseo wrote:
> In article <4b45d3ad.0305152208.3ea6e13d_at_posting.google.com>, neo55592
> _at_hotmail.com says...
>> > Could you easily solve graph problems in XML? >> > Find the shortest path in a graph, for example? >> >> What is the significance or benefit of solving "shortest path in a >> graph"
>
> There are a million-and-one uses. I suggest you Google on Djikstra
> or Floyd-Warshall algorithms. Undoubtedly, you can come across pages
> that explain the algorithms and how they may be applied. Common student
> examples are network routing, the Travelling Salesman problem,
> scheduling, etc...
>
Undoubtedly there are such problems. On the other hand, they are usually not represented in relational databases, because they lack the efficiency for such calculations. I've never seen Dijkstra's algorithm applied to a graph which is represented in a relational database.
Also, you will have serious troubles with SQL's expressivity when calculating the shortest path in a graph represented as a binary relation.
>> and are rdbs well suited to solve such problems?
>
> Define "well-suited"? Performance? Maintainability? Data
> integrity? Ease of use? What is "well-suited" to you might not be "well-
> suited" to others...
I'd say that rdbms fail in at least half of the criteria that you mention for graph algorithms:
- Performance: a join for each edge is hardly efficient - Maintainability: arguable, depends on what you call arguable - Data integrity: RDBMS can probably ensure this with constraints, howeverthis is rather inconvenient when compared to a language of which the syntax alone precludes inconsistencies (in the graph structure) in many cases.
- Ease of use: SQL is not expressive enough to calculate graph algorithms, so you'll need to embed it in a foreign language anyway (and thus again lose performance).
Sebastian Received on Fri May 16 2003 - 17:23:16 CEST