Recursive Selects using Common Table Expressions

Posted by Jonathan Allen on Oct 05, 2007

Sections

Architecture & Design,

Development,

Operations & Infrastructure

Topics

SQL Server ,

Data Access ,

.NET

Tags

SQL Server 2005

Relational databases are great for storing most forms of structured data. The most notable exception is recursive data. Tree-like structures, essential for menus, normally require awkward stored procedures to efficiently return. SQL Server 2005 does have an answer though.

Common Table Expressions, or CTEs, were introduced in SQL Server 2005, but they have not been getting the attention they deserve. In their simplest form, they are a named sub-query that appear before the main query. Since the CTE can be used multiple times, it can make complex queries look significantly cleaner.

The syntax is easy to use, but does have a few points to remember.

;WITH FirstCTE (column1, column2) AS
(SELECT column1, column2 FROM MyTable),

SecondCTE(column1, column2) AS
(SELECT column1, column2 FROM OtherTable)

Select * FROM FirstCTE UNION ALL Select * FROM SecondCTE

Multiple CTEs can be chained together, but they must be used immediately after being defined; no other code can appear between the last CTE and the final query. The semi-colon is only required if the CTE isn't the first statement in the batch, but it is easier to use it every time. CTEs cannot use ORDER BYor COMPUTE, as they are essentially sub-queries.

CTEs becomes really interesting when used recursively. An article in October's MSDN Magazine outlines the rules of recursion.

1. Create the query that returns the top level (this is the anchor member).
2. Write a recursive query (this is the recursive member).
3. UNION the first query with the recursive query.
4. Make sure you have a case where no rows will be returned (this is your termination check).

For example,

;WITH MenuCTE(MenuKey, ParentMenuKey, MenuName) AS
(
-- Anchor Query
SELECT MenuKey, ParentMenuKey, MenuName FROM Menu WHERE MenuKey = 1
UNION ALL
-- Recursive Query
SELECT m.MenuKey, m.ParentMenuKey, m.MenuName FROM Menu m
INNER JOIN MenuCTE r ON m.ParentMenuKey = r.MenuKey
)
SELECT MenuKey, ParentMenuKey, MenuName FROM MenuCTE

 

1. Back to top

   Other vendors?

   by Sam Smoot

   Nice post either way, but something I've never run across is even a shallow overview of the recursive solutions for several of the most popular databases.
   
   As far as I know, Oracle has this with the SQL99 "WITH" clause. I think PostgreSQL may have a module to support the same syntax. I'm not aware of any recursive query support for MySQL.

   Reply

2. Back to top

   Alternative

   by Kit Davies

   A vendor-neutral alternative tactic I've seen is to use an ancestry path column, ie. a column on the row containing a path of ancestor IDs, eg "/1/2/3/4". It is then possible to do some fairly sophisticated querying/updating on this using just LIKE and wildcards.
   Kit

   Reply

3. Back to top

   Re: Other vendors?

   by Nick Pierpoint

   Oracle has supported recursive SQLs for years with the "CONNECT BY" syntax:
   
   

   
   select
       node_id,
       parent_node_id,
       level -- pseudo-column
   from
       node
   connect by
       prior node_id = parent_node_id
   start with
       node_id = 'TOP';
   

   Reply

4. Back to top

   Rescursive triggers on a single table

   by Srgjan Srepfler

   I know this is a off topic but as far as SqlServer 2005 goes, I was a little disappointed when I discovered it still wasn't able to do triggers on self referencing tables. So, just a little bit of public exposure might make people at Redmond work a bit harder :)
   forums.microsoft.com/TechNet/ShowPost.aspx?Post...
   connect.microsoft.com/SQLServer/feedback/ViewFe...

   Reply

5. Back to top

   Re: Other vendors?

   by Jonathan Allen

   To be honest, I simply don't have the time to keep up with all the database vendors. But if you feel your favorite databases are being slighted, let me know and I'll try to run more articles on them.
   
   As for Oracle and CTEs, here is a link for our other readers.
   
   www.dba-oracle.com/t_sql99_with_clause.htm
   
   If anyone has something for other vendors, please post it here.

   Reply

6. Back to top

   Re: Rescursive triggers on a single table

   by Jonathan Allen

   Well if you want to write a brief article on why it is needed, I'll be happy to run it as a "guest opinion". I can't promise it will help, but maybe we can garner a few more votes on Microsoft Connect.

   Reply

7. Back to top

   Re: Alternative

   by Dan Thiffault

   Or the nested set model. Great for read heavy operations.
   
   www.developersdex.com/gurus/articles/112.asp

   Reply

8. Back to top

   Re: Other vendors?

   by billson chew

   i'm kinda outdated, and disapointed about the "WITH" syntax is not applicable in mysql.
   
   anyone could give me a clue that the following codes in sql2005 translated in mysql?
   
   thanks for respond.
   ******************************************************
   WITH MenuCTE(MenuKey, ParentMenuKey, MenuName) AS
   (
   -- Anchor Query
   SELECT MenuKey, ParentMenuKey, MenuName FROM Menu WHERE MenuKey = 1
   UNION ALL
   -- Recursive Query
   SELECT m.MenuKey, m.ParentMenuKey, m.MenuName FROM Menu m
   INNER JOIN MenuCTE r ON m.ParentMenuKey = r.MenuKey
   )
   SELECT MenuKey, ParentMenuKey, MenuName FROM MenuCTE
   ******************************************************

   Reply

• Older >