Geek asks and answers

Find all links of a certain depth

This is from a household question. We solved this by building the SQL query dynamically. But we are wondering if this is possible with pure SQL.

Simplification of the desired: There is a table with two columns: a source identifier and a destination identifier. Given id and number n, we need to find all id of a distance less than n from a given id.

Editing explanations:
Think about how a table is a web link. If row (1,3) appears in the table, this means that web page 1 has a link to web page 3.
We need to find all web pages accessible from the initial web page with n clicks or less.

Since this is a matter of “curiosity,” 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).

+3
source share
3 answers

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

The best thing you can do is select N at the time of compilation and use many joins, as you already did in the dynamically generated approach to the query.

+1
source

, "n" vanilla SQL. , , - "n".

+1

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 source identifier, and then recursively connects to itself.

After that, it is as simple as filtering out all the records that you do not need.

+1
source

More articles:


All Articles