CODEWITHSUNDEEP
sql
Artium
Artium

Reputation: 5329

Find all links of certain depth

This is from a homework question. We solved it by building the SQL query dynamically. But we are interested if it is possible to do with pure SQL.

A simplification of what is desired: There is a table with two columns: source id and destination id. Given an id and a number n, we need to find all id of distance smaller equal n from the given id.

Clarification Edit:
Think about the table as representing web-links. If the row (1,3) appears in the table, it means that web-page 1 has a link to web-page 3.
We need to find all webpages that are reachable from a starting web-page with n clicks or less.

Since it is a "curiosity" question, use whatever SQL implementation you prefer. "Pure SQL" means everything that fits into the "structured query style". Using loops is not considered "pure SQL" (for the sake of the question).

Upvotes: 3

Views: 214

Answers (3)

Chris Bednarski
Chris Bednarski

Reputation: 3424

In MS SQL 2005+ you can use a recursive query

;WITH RecursiveTbl AS
(
  SELECT WL.SouriceID, WL.DestinationId, 0 AS level
  FROM WEBLINKS WL
  WHERE WL.SouriceID = @your_top_level_id

  UNION ALL

  SELECT WL.SouriceID, WL.DestinationId, RWL.level + 1 AS level
  FROM RecursiveTbl RWL
  JOIN WEBLINKS WL ON RWL.DestinationId = WL.SourceID
)
SELECT * FROM RecursiveTbl WHERE level BETWEEN 1 AND 3;

The query initially selects records with the same SourceID and then recursively join to itself.

After that, it's as simple as filtering out all the records that you don't need.

Upvotes: 1

hugomg
hugomg

Reputation: 69944

You cannot express transitive closure using relational algebra or pure old SQL, so a general solution for any N is not possible.

The best you can do is choose the N at "compile time" and use lots of joins, as you already do in the dynamically generated query approach.

Upvotes: 1

kuriouscoder
kuriouscoder

Reputation: 5582

The short answer is that for any "n" it might not be possible via vanilla SQL. What you are attempting to do is to explore all the links breadth wise until a given depth "n".

Upvotes: 1

Related Questions