استخراج برگ های (leaf) یک رابطه سلسله مرتبی در SQL

در این پست نحوه لیست کردن برگ های یک سلسه مراتب یا بهتره بگیم یک رابطه parent و child رو در SQL بررسی می کنیم. leaf در یک ساختار درختی به اون node گفته میشه که زیرمجموعه یا child نداره. به طور مثال در تصویر زیر 2، 5، 7 و 8 leaf هستند.

برای این که با استفاده از کوئری این مقادیر رو استخراج کنیم، لازمه مقادیری از فیلد (ستون) child رو که هیچ گونه ردی در فیلد parent ندارند رو جدا کنیم. مثال تصویر بالا رو در صورتی که به صورت ستون های parent و child پیاده کنیم خواهیم داشت:

DECLARE @t TABLE (id INT NOT NULL, REFID int NULL);

INSERT @t VALUES 
	(1, NULL), 
	(2, 1),  
	(3, 1),  
	(4, 3), 
	(5, 3),
    (6, 4), 
	(7, 4), 
	(8, 6);

SELECT * FROM @t

توضیح خروجی بالا: برای پر کردن جدول بالا همه شمارها رو از تصویر بالا در ستون id که همون child هست قرار میدیم و در صورتی که id  مورد نظر parent و عددی بالای اون داشت در ستون refid قرار میدیم و البته  برای id شماره 1 که هیچ گونه parent نداره NULL قرار میدیم.

روش اول

استفاده از LEFT OUTER JOIN هستش که جدول رو با خودش JOIN می زنیم (بین ستون id از اولی و refid ازدومی) و در صورتی که در رکوردی از جدول دوم NULL پیدا شد یعنی اون id هیچ گونه child یا زیرمجموعه ای نداره! و leaf  هستش

SELECT 
	t1.*	
FROM
	@t AS t1
LEFT OUTER JOIN
	@t AS t2
ON
	t1.id = t2.refid
WHERE
	t2.id IS NULL

روش دوم

استفاده از SUB QUERY در WHERE هستش که تمامی مقادیر id رو به ستون refid در قسمت شرط پاس میدیم و در صورتی که مقداری برگشتی وجود نداشت (با استفاده از NOT EXISTS چک می کنیم) اون id  leaf خواهد بود

SELECT 
	id,
    refid
FROM   
	@t AS t_out
WHERE  
	NOT EXISTS (SELECT t_in.refid FROM  @t AS t_in WHERE t_in.refid = t_out.id) 

خروجی در هر دو حالت به صورت زیر خواهد بود: