Mar 16, 2010

Sử lý đệ quy trong SQL Server

Hôm nay làm môt tut về đệ qui trong SQL server. Trong lập trình thông thường bạn sẽ phải sử lý nhiều tình huống đề quy, nhưng ít khi nó thể hiện rõ tính chất đệ quy bởi nó chỉ là vòng lặp dạng for hoặc while. Và thực ra việc thiết kế giải thuật người ta cũng cố gắng đề giải đệ quy hoặc khử đệ quy để bảo đảm cấu trúc bộ nhớ của trương trình cũng như là cho code dễ hiểu.
Nhưng không phải lúc nào như lý thuyết cũng là đúng, trong một số tình huống cụ thể cách đệ quy chở nên hiệu quả ngắn ngọn và tối ưu hơn cách viết thông thường. Vậy bài viết này hướng dẫn bạn đệ quy trong DB.

Đệ quy để làm gì ? Với một business phức tạp và sử lý trên một cấu trúc cây đa cấp bạn sẽ mắc phải vấn đề rác rối về hiệu xuất của hệ thống khi quyết định sử lý tất cả trên tầng business. Chính vị vậy bạn cần sử lý một số các nghiệp vụ cụ thể trong DB nhằm tăng tốc cho hệ thống của mình. Đây chính là mảnh đất mà chúng ta khai thác...

Giả sử bạn có một cây đa cấp chông nó như thế này.


Khi đó trong DB bạn sẽ có một cấu trúc như thế này cho cái cây đó

và việc sử lý trên cây sẽ vô cùng rác rối với mỗi một node bạn phải kiểm tra xem nó là có con không ? cha nó là ai ? anh chị em nó là gì ? ....
ở đây tôi chỉ viết một hàm trong DB sql 2005, với mục đích nhận vào một node id và trả về môt bảng các node id con cháu nêu có.

code here.

IF EXISTS (SELECT * FROM sys.objects WHERE object_id = OBJECT_ID(N'[dbo].[udfNodeChirent]') AND type in (N'FN', N'IF', N'TF', N'FS', N'FT'))
DROP FUNCTION [dbo].[udfNodeChirent]
GO

CREATE FUNCTION [dbo].[udfNodeChirent]
--======================================
--created by : linhdkl
--created date : 16/03/2010
--======================================

(
@parentID int
)
RETURNS @tbl TABLE (id int,valu int)
WITH EXECUTE AS CALLER
AS
begin
if @parentID > 0
begin
declare @tempCount int
declare @count int
set @count = 0
select @count = count(id)from tree where parentNodeid = @parentID
if(@count > 0)
begin
insert @tbl(id,valu) select ROW_NUMBER() over( order by ID),id
from tree
where parentNodeid = @parentID
declare @row int
set @row = 1
while @row <= @count
begin
select @tempCount = count(id) from @tbl
select @parentID = valu from @tbl where id = @row
insert @tbl(id,valu) select ROW_NUMBER() over( order by ID) + @tempCount,valu
from dbo.udfNodeChirent(@parentID)
set @row = @row +1
end
end
end
return
end
GO


Ok như vậy mình đã có cái func này và đây là kết quả.

select * from dbo.udfNodeChirent(47)
nó sẽ có kết quả là :

id valu
----------- -----------
1 72
2 99
3 100
4 73
5 74
6 95
7 105
8 106
9 75
10 76
11 102
12 103
13 104
14 107
15 101

(15 row(s) affected)

cái id chính là số thứ tự và valu là id của các con, cháu, chắt của thằng node 47.

Tuy nhiên cũng xin nói thêm là đây chỉ là cách sử lý dựa trên hệ thống đã có sẵn, tức là việc này chỉ cải thiện tình trạng một cách miễn cưỡng. Nếu một hệ thống đc thiết kế tốt, việc sử lý này sẽ sử dụng một danh sách liên kết và sử lý phi tuyến tính sẽ nhanh hơn rất nhiều. Tuy nhiên giá trị của giải thuật đệ qui vẫn tồn tại trong bất kỳ trường hợp nào.

../..


3 comments:

  1. Sai chính tả kinh hoàng =)) =))

    ReplyDelete
  2. Mình có cách này các bạn xem có giúp được gì ko nhé


    with TT as
    (
    select id,
    parentnodeid,
    Caption,
    convert(varchar(30),case when len(id) = 2 then '0'+ convert(varchar(10),id) else convert(varchar(10),id) end) as [Path]
    from Tree
    where id = 47
    union all
    select Tree.id,
    Tree.parentnodeid,
    Tree.Caption,
    convert(varchar(30), convert(varchar(15),TT.[Path]) + '.' + convert(varchar(10),case when len(Tree.id) = 2 then '0'+ convert(varchar(10),Tree.id) else convert(varchar(10),Tree.id) end)) as [Path]
    from TT inner join Tree on TT.id = Tree.parentnodeid

    )
    select id,parentnodeid,Caption from TT order by [Path]

    ReplyDelete
  3. @Thuy`:

    Cách của bạn rất hay tiếc là đã lâu rồi nên tôi cũng không có thời gian để test code của bạn.
    Nhưng tôi đoán là code của bạn chạy đc.

    thanks
    ../..

    ReplyDelete

 
Bạn có thể dùng bài viết của tôi tùy ý bạn nhưng vui lòng ghi lại rõ nguồn cung cấp
The world in a click_
Copyright © 2008 linhdkl