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@minotaurus.cip.informatik.uni-muenchen.de>

Paul Tiseo wrote:

> In article <4b45d3ad.0305152208.3ea6e13d_at_posting.google.com>, neo55592
> @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, however 

  this 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 - 10:23:16 CDT