Re: an old worn interview question

user923005 wrote:
On Sep 17, 3:09 pm, Tegiri Nenashi <TegiriNena...@xxxxxxxxx> wrote:
"given a graph of pointers, can you find a loop there"

I must admit that during 20 or so years of programming I never came
across any practical program that required finding a loop in the
directed graph.

A typical problem is a database of workers and supervisors. All
employees are kept in a single table, where employees of supervisors
are identified with a 'works_for' field. I guess you can imagine how
easily loops can arise.

The Oracle database has a type of query called a hierarchical query.
This query will search a table for all the rows sharing a common
ancestor based on a parent/child relationship between rows.

For example, given this table (call it "foo"):

id parent_id name
-- --------- ----
1 NULL A
2 1 B
3 1 C
4 2 D
5 NULL E
6 5 F
7 5 G

you can give a query like this:

SELECT name
FROM foo
START WITH id = 1
CONNECT BY PRIOR id = parent_id

This query will return A, B, C, and D because all those rows can be
traced back to the row with id == 1 by the relationship of one row's
id with another row's parent_id.

As you can imagine, it's bad if you can give a query that causes
the database to go into an infinite loop, so it has to detect cycles
when performing this type of query. In fact, the Oracle documentation
says it will detect cycles:

If the CONNECT BY condition results in a loop in the
hierarchy, then Oracle returns an error[1].

I suppose Oracle could implement this in a cheesy fashion: it knows
the size of the graph (the number of rows in the table), so if your
table has N rows and you have gone N steps and not reached the root,
you're in a loop. But one would hope they did something a little
nicer than that. (You're supposed to be able to put zillions of
gigabytes of data in an Oracle database without it falling over
dead.)

In fact, there might be another interesting angle to this: Oracle
lets you specifying "constraints" so that modifications to the
database are disallowed if they would violate some particular
property (such as a column being a unique key). I don't know
whether it does or not, but if Oracle supports defining constraints
that prohibit loops in hierarchical relationships, then there would
be value in having an algorithm that can incrementally detect loops.
That is, given a graph that doesn't have loops, if you make a set of
changes to that graph (add/modify/delete nodes/edges), is it still
free of loops?

- Logan

[1] http://download-west.oracle.com/docs/cd/B10501_01/server.920/a96540/queries4a.htm
.

Relevant Pages

  • Re: hierarchical query - returning a treewalked subset
    ... pretty small), and if a row is LEVEL 1, it loops thru the resultset ... Take any query that produces a result set in Oracle. ... only for system account ... 100 torrent files; ...
    (comp.databases.oracle.server)
  • Re: MS SQL Server - a plethora of limitations...
    ... > Most of your objections are that MS-SQL is not Oracle. ... good SQL programmers do not use loops. ... standard, ... now) people test extits from loops at the begining, then in the middle, then ...
    (microsoft.public.sqlserver.programming)
  • Re: Cursor for loops
    ... No, no, I didn't mean simply 'for loops', but 'cursor for loops'. ... They look like this in Oracle: ... FOR mycursor IN ...
    (microsoft.public.sqlserver.programming)
  • Re: Cursor for loops
    ... No, no, I didn't mean simply 'for loops', but 'cursor for loops'. ... They look like this in Oracle: ... FOR mycursor IN ...
    (microsoft.public.sqlserver.clients)
  • Re: Cursor for loops
    ... No, no, I didn't mean simply 'for loops', but 'cursor for loops'. ... They look like this in Oracle: ... FOR mycursor IN ...
    (microsoft.public.sqlserver.server)