پیمایش recursive relation

[titbasoft]

سلام خدمت همه دوستان
من یک table دارم که یک recursive relation داره. به عبارتی دیگر یک FK داره که parent اش خود همون جدوله. برای واضح تر شدن مطلب این اسکریپت رو فرض کنید.

http://www.titbasoft.com/script.jpg

حالا فرض کنید می خواهیم تمام کسانی که مثلا اقای احمدی رئیسشان هست رو پیدا کنیم
برای توضیح بیشتر اینکه آقای احمدی به 2 طریق رئیس یک کارمند میشه:
1) مستقیما boss او آقای احمدی باشه
2) boss کسی باشه که رئیسش آقای احمدی هست. و یا چند لایه بیشتر...

یک query می خوام که تمام کسانی که زیر دست احمدی کار میکنند رو برام لیست کنه :گیج:

با تشکر فراوان!!! :)

[hmm]

باور کن یه نیم ساعتی فکر کردم ولی شرمنده ....
این query خیلی پیچیدهه
فکر کنم تنها راهش برنامه نویسیه

[titbasoft]

ممنون :flower:

[AminSobati]

دوست عزیزم،
برای کنترل Chartهای سازمانی، دو روش معروف وجود داره:
Adjacency List Model: یعنی همون ساختار جدولی که مثال زدین. در این روش، وقتی نیاز به پیدا کردن تمام زیر مجموعه های یک فرد دارید، میبایست جدول موقتی در حافظه ایجاد کنین (توسط Declare) و در طی یک Loop، تمام زیر مجموعه ها رو تا انتها مرتبا بخونین و وارد جدول موقتی کنین. یعنی در Query اول، تمام کارمندان مستقیم آقای احمدی رو وارد جدول کنین، دفعه بعد، این جدول موقتی رو Join میکنین با جدول اصلی با این شرط که همه کارمندانی رو برگردونه که Boss اونها برابر با EmployeeID در جدول موقتی باشه. نتیجه این Query دوباره در جدول موقتی وارد میشه و باز Join تکرار میشه. ولی به یاد داشته باشید که یک فیلد خاص در جدول موقتی نیاز دارین که هر وقت زیر مجموعه های یک عده از کارمندان رو آوردین، این فیلد مثلا از 0 به 1 تغییر میکنه تا در Join بعدی دوباره اون زیر مجموعه های تکراری برگردونده نشن و به این ترتیب فیلتر انجام بدین. و اما روش دوم:

Nested Set: به این شکله که ما بالاترین کارمند رو در نظر میگیریم(به شکل درخت تجسم کنید) و از سمت چپ اون شروع به شمارش میکنیم و پایین میایم، هر وقت که به کارمندی میرسیم، یکی به شمارشمون اضافه میکنیم. زمانیکه کارمندی زیر مجموعه نداشت، جهت حرکات ما از سمت راست اون کارمند به بالا ادامه پیدا میکنه و مرتبا با رسیدن به هر کارمند، یکی به شمارش اضافه میشه. مثل اینکه با مداد دور شاخه های این درخت داریم خط میکشیم. پس هر کارمند یک فیلد Left داره و یک فیلد Rigth. وقتی میخواهیم زیر مجموعه های یک کارمند رو بدست بیاریم، در شرط Query قید میکنیم: کارمندهایی را بدست بیاور که Left آنها از Left این کارمند، بزرگتر و Right آنها از Right این کارمند، کوچکتر باشد.

این دو روش هر کدوم مزایا و معایب خاص خودشون رو دارند. آقای Joe Celko یکی از کسانیه که پازلها و معماهای جالبی رو در دنیای TSQL طرح کرده(که عمدتا نوعی سرگرمی ریاضی هستند) و در کتاب معروفش به اونها جواب داده. بحث Tree یا همین Chart سازمانی یکی از اونهاست. اگر اسم ایشون رو بعلاوه اسم دو روش مذکور Search کنین، مقالات جالبی در این زمینه پیدا میکنین.
فایلی که براتون فرستادم، قسمت برگزیده ای از اون کتاب هست. همچنین یک راه حل برای روش اول وجود داره که Davidson نوشته.
موفق باشید

[M.GhanaatPisheh]

ببخشید جناب ثباتی عزیز
کتاب کامل رو چجوری میشه تهیه کرد؟
شدیدا علاقمندم بخونمش. :flower:

[N_D]

سلام دوست عزیز
من این کد رو بروش بازگشتی نوشتم ولی تکمیل نیست(آخه الان ساعت 3 نصف شبه و من مخم بزور کار میکنه)
در این کد
1- تست اینکه شخصی رپیس خودش هم باشه صورت نگرفته .(این کار بعهده خودت)
2- اگه تعداد تورفتگی درخت از 32 سطح بیشتر بشه خطا میده
روش کار کن .. البته برای رفع این مشکلات هم راه حلهای زیادی هست.
برای فراخوانی EXEC process 2


insert into employees(BOSS,LNAME) values(1,'akbari')
insert into employees(BOSS,LNAME) values( 1,'sajaddi')
insert into employees(BOSS,LNAME) values( 2,'mehrdadi')
insert into employees(BOSS,LNAME) values( 2,'karimi')
insert into employees(BOSS,LNAME) values( 2,'farshidi')
insert into employees(BOSS,LNAME) values( 3,'fatemi')
insert into employees(BOSS,LNAME) values( 6,'masoudi')
insert into employees(BOSS,LNAME) values( 6,'ahmadi')
insert into employees(BOSS,LNAME) values( 8,'ferdosi')
insert into employees(BOSS,LNAME) values( 8,'naderi')
-----------------------------------------------------------------------------
Create proc process(@boss int) as
begin
declare @i int ,@bs int, @Row int ,@lname char(10)
declare @Temp Table(empID int,LName char(10), ID_Num int identity)
Insert @Temp
SELECT empID,LName FROM EMPLOYEES where boss =@boss
set @Row= @@rowcount
if @@ROWCOUNT = 0 Return
Set @i =1
while @i <= @ROW
begin
select @bs=empID,@lname = LName From @Temp where ID_NUM = @i
print @LName
EXEC process @bs
Set @i=@i+1
end
end
-----------------------------------------------------------

[AminSobati]

کتاب کامل رو چجوری میشه تهیه کرد؟
دوست عزیزم، در Amazon یقینا پیدا میشه، ولی در ایران ندیدم این کتاب رو (و من هم ندارم)

[N_D]

این هم برای تست اینکه کسی رییس خودش هم باشه


create proc process(@boss int) as
begin
declare @i int ,@bs int, @Row int ,@lname char(10)
declare @Temp Table(empID int,LName char(10), ID_Num int identity)
Insert @Temp
SELECT empID,LName FROM EMPLOYEES where boss =@boss
set @Row= @@ROWCOUNT
if @@ROWCOUNT = 0 Return
Set @i =1
while @i <= @ROW
begin
select @bs=empID,@lname = LName From @Temp where ID_NUM = @i
print @LName
if @bs <> @boss
EXEC process @bs
Set @i=@i+1
end
end

بهتر اینه که این پروسه رو تبدیل به یه تابع کنی که خروجی اون empID همه فرزندان باشه که از طریق یک رشته با جداکننده ویر گول برگردونده بشه

[titbasoft]

با تشکر از آقای ثباتی و آقای N_D
حتما در اولین فرصت نظرم رو میدم
بازم از توجه شما ممنونم. :wink:

[titbasoft]

سلام

الگوریتم اول: Adjacency List Model از آقای ثباتی



DECLARE @managerId int
SET @managerId = 2

DECLARE @outTable table (employeeId int, boss int, treeLevel int)

DECLARE @treeLevel as int
SET @treelevel = 1

INSERT into @outTable
SELECT employeeId, boss, @treelevel as treelevel
FROM dbo.employees as employee
WHERE (employee.boss = @managerId)


WHILE (1 = 1)
BEGIN

INSERT INTO @outTable
SELECT employee.employeeId, employee.boss, treelevel + 1 as treelevel
FROM employees as employee JOIN @outTable as ht ON employee.boss = ht.employeeId

WHERE EXISTS( SELECT *
FROM @outTable AS holdTree
WHERE treelevel = @treelevel
AND employee.boss = holdtree.employeeId)


IF @@rowcount = 0
BEGIN
BREAK
END

SET @treelevel = @treelevel + 1
END
----------------------------
SELECT Employee.EmployeeId, Employee.name
FROM dbo.employees as Employee
join @outTable as ot
on employee.employeeId = ot.employeeId

که به زبان ساده تر و با در نظر گرفتن همین الگوریتم می توان آن را به صورت زیر نوشت:



declare @t table (employeeid int)
insert into @t select employeeid from employees where boss =2

while @@rowcount!=0
begin
insert into @t select employeeid from employees where boss in (select employeeid from @t) and employeeid not in (select employeeid from @t)
end
-----------------
select * from @t


نکات

الگوریتم دوم: recursive function از جناب N_D (با تصرف و تخلص)



create function f2 (@boss int)
returns @f2 table (
employeeid int , name varchar(30)
)
as
begin
declare @bs int ,@name char(10)
declare @i int ,@Row int
declare @Temp Table(employeeID int,Name char(10), ID_Num int identity)

Insert @Temp SELECT employeeID,Name FROM EMPLOYEES where boss =@boss

set @Row = @@rowcount
if @Row = 0 Return
Set @i =1
while @i <= @ROW
begin
select @bs=employeeID,@name = Name From @Temp where ID_NUM = @i
insert @f2 select @bs,@name
insert @f2 select * from f2(@bs)
Set @i=@i+1
end
return
end
-----------
select * from f2(2)


من هر دوی این الگوریتم ها رو روی حدود فقط 8000 رکورد تست کردم
نتیجه این شد که الگوریتم اول حدود 15 ثانیه و الگوریتم دوم حدود 42 ثانیه طول کشید
حالا من که با حدود 200000 هزار رکورد سر و کار دارم باید چی کار کنم؟

اما یه راه حلی خودم به نظرم رسیده که گرچه خیلی ناشیانه است ولی فکر کنم جواب بده و اونم اینه که بیام یه trigger بزارم روی این جدول که هر رکودی که وارد شد تمام کسانی که رئیسش هستند رو در یک جدول دیگه نگه داری کنه بعد از جدول دومی برای جستجو استفاده کنم
حالا نظر بدین این کار چطوره؟ :گیج:

از هم از همه کسانی که وقت میذارن ممنونم :موفق:

[titbasoft]

جناب ثباتی عزیز
الان اومدم دنبال اون فایلی که قبلا ضمیمه کرده بودید که گفتم یه نگاهی دوباره به پست شما بندازم. تنها چیزی که می تونم بگم اینکه اون موقع واقعا به عظمت Nested Set پی نبرده بودم و الان تازه فهمیدم چی کار میکنه اما هنوز درست متوجه نشدم فیلدهای راست و چپ چطوری بدست میان؟
Nested Set از نظر performance ی query رو دست نداره چون فقط یک select ساده نیاز داره ولی به نظر میاد حجم update اش خیلی بالاست.
میشه لطف کنید در مورد اینکه راست و چپ هرکسی چطوری ساخته میشه بیشتر توضیح بدید؟

[titbasoft]

یه مشکل مهمتری که Nested Set داره اینه که نمی شه مثلا child ها رو در عمق یک (یک لایه پایین تر) بدست آورد. همین طوره؟

[AminSobati]

برای بدست آوردن اعداد، فرض کنین یک نفر در سازمان دارای دو نفر زیر مجموعه هستش. هر کدوم از این افراد هم رو نفر زیر مجموعه دارند. پس کل افراد سازمان هفت نفر هستند. از سمت چپ نفر اول شروع میکنیم با عدد 1، یک پله به پایین حرکت میکنیم، یعنی میرسیم به سمت چپ نفر بعد، عدد 2 رو در سمت چپش ثبت میکنیم. این فرد چون زیر مجموعه داره، مجددا یک پله به پایین میریم و عدد سه رو به سمت چپ نفر پایین میدیم. این فرد زیر مجموعه نداره، پس به سمت راست میایم و عدد 4 رو میدیم. یک نفر دیگه در همین Level قرار داره. به سمت چپ اون میریم با عدد 5. این فرد زیر مجموعه نداره پس به سمت راستش عدد 6 میدیم. همچنین فرد دیگه ای در این Level قرار نداره پس یک سطح میریم بالا و عدد 7 رو به سمت راست بالایی میدیم. فرد دیگه ای در این سطح قرار داره. به سمت چپش عدد 8 رو اضافه میکنیم و به همین ترتیب، زیر مجموعه های این فرد رو هم دور میزنیم.
یعنی دقیقا شما با یک قلم، تمام شاخه ها رو دور میزنین و به هر جا که میرسین، یک عدد اضافه میکنین.
همونطور که گفتین بدست آوردن یک Level پایین تر یا سطح بخصوصی، راحت نیست و ویرایش این درخت در هنگام ورود Nodeهای جدید یا حذف اونها، کمی زحمت داره. اما در کل من روش Adjacency List رو ترجیح میدم چون در SQL Server 2005 شما به کمک CTE میتونین با یک Query تمام زیر شاخه ها یا سطح بخصوصی رو بدست بیارین و مثل نسخه 2000 نیاز به جدول موقتی و غیره ندارین.
در ضمن ویرایش اون هم بسیار راحته.
موفق باشید

[titbasoft]

خیلی ممنون. من هم زمان طراحی از همون Adjacency List استفاده کرده بودم و خوشبختانه نیازم رو الان که موقع پیاده سازیه رفع کرده و در کل من هم احساس می کنم قدرت کنترل این الگوریتم خیلی بالاتره. چیزی که به وفور توی سیستم کنونی که روش کار میکنم اتفاق میافته برداشت یک node و انتقال او زیر یک node دیگه است که مطمئنا روش nested set جوابگو نیست!

همونطور که پیشنهاد کرده بودید کتاب
J O E C E L K O ’ S
T R E E S A N D
HIERARCHIES IN
SQL FOR SMART I E S
رو بالاخره همین امروز موفق شدم download کنم. یه کتاب دیگه هم که فکر کنم کتاب خوبی هست هم به نام Joe Celko's Data and Databases: Concepts in Practice دانلود کردم. تصویر زیر هم از همون کتاب اول در تکمیل فرمایشات شماست!
http://www.titbasoft.com/barnamenevis/nested.gif


چون در SQL Server 2005 شما به کمک CTE میتونین با یک Query تمام زیر شاخه ها یا سطح بخصوصی رو بدست بیارین و مثل نسخه 2000 نیاز به جدول موقتی و غیره ندارین.از این بهتر نمیشه. واقعا که نیاز کاربر رو بهتر از خودش می فهمند و برآورده میکنن!

[AminSobati]

هاشم جان اگر لینک رو در اختیار عموم قرار بدین ممنون میشم. چون اکثر برنامه نویسان سیستمهای اتوماسیون به این مباحث نیاز دارند.
در ضمن حالا که صحبت از ebook شد، این موارد رو هم سری بزنین:
http://www.5000books.com/Computers_and_Internet/
http://ebook.irdesigner.com/index.php?cat=1

[titbasoft]

نمی دونم چرا الان به این 2 تا سایت دسترسی ندارم اما مطمئنا سایت های بدرد بخوری هستند. ممنون



هاشم جان اگر لینک رو در اختیار عموم قرار بدین ممنون میشم. چون اکثر برنامه نویسان سیستمهای اتوماسیون به این مباحث نیاز دارند. حتما همین طوره. حتی اگر اینطور هم نبود بازم ارزش دانلود کردن رو داشتند. من اون کتابها رو با استفاده از e-mule گرفتم. اونها رو روی سایت خودم گذاشتم تا اگر کسی نیاز داشت ازشون استفاده کنه: http://www.titbasoft.com/barnamenevis/Celko.zip

[مطهر]

با سلام
خیلی ممنون از این تاپیک بسیار مفید
اگر شما یک کارمند داشته باشید چطور رئیس را تشخیص می دید.
یه جور دیگه:
اگر یه Node داشته باشید چطور Root را بدست می آورید
ممنونم

[مطهر]

من این را نوشتم. به نظر شما خوبه؟


CREATE FUNCTION FindRoot(@g smallint)
RETURNS SMALLINT
--returns @t TABLE(goodsId smallint,GoodsName nvarchar(50),ParentId smallint)
AS
BEGIN
--declare @g smallint
declare @t TABLE(goodsId smallint,GoodsName nvarchar(50),ParentId smallint)
--SET @g=84
INSERT INTO @t SELECT Goods_id,Goods_Name,Parent_Id FROM GOODS
WHERE Goods_id=@g
Declare @p smallint
set @p=(SELECT parentId FROM @t)
WHILE( @p<>0)
BEGIN
delete from @t
INSERT INTO @t SELECT Goods_id,Goods_Name,Parent_Id FROM GOODS
WHERE goods_id=@p
set @p=(SELECT parentId FROM @t)
END
declare @gid smallint
set @gid=(select goodsid from @t)
RETURN (@p)
END

[AminSobati]

پیدا کردن Root بسیار راحته. مثلا رده بالای رکورد مورد نظرتون رو از طریق فیلد ParentID بدست میارید. حالا این رکورد(Parent) رو از جدول بخوانید و ParentID اون رو بدست بیارید. مجددا Parent رو بخوانید و....
این کار در یک حلقه انجام میشه

[مطهر]

ممنون از استاد ثباتی عزیز

این کار در یک حلقه انجام میشه
پس از این چیزی که من نوشتم درسته

[AminSobati]

ممنون از استاد ثباتی عزیز

پس از این چیزی که من نوشتم درسته
من جداول شما رو ندارم تا تست کنم، اما در ظاهر که درسته!