مقدمه
قبل از مطرح کردن مساله کاربردی نیاز
هست که کمی تحلیل ها و بررسی های ریاضیاتی راجب نظریه مجموعه ها داشته باشیم.
دو مجموعه A و
B را مساوی گویند و به شکل A = B
نشان خواهند داد اگر و تنها اگر تمام عناصر هر دو مجموعه با همدیگر برابر باشند.
بطور مثال دو مجموعه {1,1,2,3} برابر است با
{3,3,3,1,2}. باید توجه داشته باشید که در مجموعه تکرار و ترتیب
شناخته شده نیست. به این صورت که تمام عناصر تکراری تنها یک عنصر شناخته می شوند.
و اصل بدیهی تساوی را به این شکل است:
∀x
: x ∈ A <=>
x ∈ B
این به این معناست که به ازای هر عضوی
که در مجموعه A است در مجموعه B نیز
باشد و به ازای هر عضوی که در مجموعه B است در مجموعه ی
A نیز باشد.
در واقع اگر A
زیر مجموعه ی B و B زیر مجموعه ی
A باشد این دو مجموعه با همدیگر مساوی هستند. در نتیجه لازم
است که راجب زیر مجموعه بودن توضیحات مختصر و مفیدی داده شود تا به یک قانون کلی
برای بررسی و اثبات تساوی دو مجموعه برسیم.
اگر A زیر
مجموعه B باشد آن را به شکل A ⊆ B
نشان داده و اصل بدیهی آن در زیر دیده می شود:
∀x : x
∈ A => x ∈ B
این به این معناست که به ازای هر عضوی
که در مجموعه A قرار دارد در مجموعه ی B
نیز وجود داشته باشد.
یا به عبارت دیگر بر اساس سور وجودی، زیر مجموعه بودن
A به B را اینگونه تعریف می کنیم: "وجود
نداشته باشد عضوی از مجموعه A که در مجموعه ی
B وجود نداشته باشد". در حقیقت با
دوبار نقیض گیری به همان اصل بدیهی قبلی رسیدیم. بعدا متوجه خواهید شد که چرا در
اینجا از سور وجودی (EXISTS) استفاده شده است. چرا که در
زبان SQL سور وجودی FOR ALL
پشتیبانی نمی شود.
∃x: x ∈ A => x ∉ B
و اگر B زیر
مجموعه ی A باشد یعنی B ⊆ A انگاه
اصل بدیهی بصورت یکی از دو شکل زیر بیان می شود:
∀x : x
∈ B => x ∈ A
∃x: x ∈ B => x ∉ A
فرمول اول- در نتیجه دو مجموعه ی A
و B برابر اند اگر و تنها اگر A ⊆ B
و B ⊆ A:
(A ⊆ B) ∧ (B ⊆ A)
فرمول دوم- و با توجه به اصل بدیهی که با کمک
سور وجودی و دوبار نقیض گیری مطرح شد داریم:
(⌐∃x: x ∈ A => x ∉ B) ∧ (⌐∃x:
x ∈ B => x ∉ A)
فرمول سوم- اگر تفاضل مجموعه B
از A برابر باشد مجموعه تهی و تفاضل مجموعه A
از B نیز برابر باشد با مجموعه تهی (Empty Set)
می توانیم نتیجه بگیریم دو جدول با یکدیگر برابرند.
(A ∖ B) = ∅ ∧ (B ∖ A) = ∅
فرمول چهارم- اگر تعداد
عناصر حاصل از اشتراک دو مجموعه A و B
برابر باشد با تعداد عناصر یکی از دو مجموعه و تعداد عناصر دو مجموعه با یکدیگر
برابر باشند می توان نتیجه گرفت که دو مجموعه با همدیگر برابر هستند.
n
(A∩B) = n (A) ∧
n (A) = n (B)
یا تعداد عناصر
مشترک در دو مجموعه باربر باشد با تعداد عنصر جدولی که بیشترین عنصر را دارد. یعنی:
n (A∩B) = MAX (n (A), n (B))
یا به عبارتی دیگر
تعداد عناصر سه مجموعه ی A و B و
A∩B با هم برابر باشد یعنی:
n (A∩B) = n (A) = n (B)
مساله
بعد از طرح شدن
مقدمه ای نسبتا کامل ذهن شما بایستی آمادگی لازم را برای حل مساله توسط زبان مجموعه
گرای SQL پیدا کرده باشد.
فرض کنید جدولی
داریم که اطلاعات رانندگان را نگهداری می کند (به نام جدول Drivers)
و جدول دیگری داریم که مشخصات اتوبوس ها را ذخیره کرده است (به نام Buses)
و جدول سوم جدولی است که مشخص می کند چه راننده ای با چه اتوبوسی به سفر (Trip)
رفته است.
هدف ما پیدا کردن
رانندگانی است که دقیقا با تمام اتوبوس ها سفر کرده اند و با اتوبوسی خارج از
اتوبوس های جدول Buses سفری نداشته اند. این مساله به تقسیم
دقیق رابطه ای یا Exact Relational Division معروف است.
البته فکر می کنم به این عمل Image نیز گفته می شود.
داده های زیر اساس
ما برای پرس و جو گیری است.
CREATE
TABLE Drivers
(
driver_nbr INT
NOT NULL
PRIMARY KEY
);
CREATE
TABLE Buses
(
bus_nbr INT
NOT NULL
PRIMARY KEY
);
CREATE
TABLE Trips
(
driver_nbr INT
NOT NULL,
bus_nbr INT
NOT NULL,
UNIQUE(driver_id,
bus_id)
);
INSERT
INTO Drivers
VALUES
(1),
(2),
(3);
--Divisor
INSERT
INTO Buses
VALUES
(1),
(2),
(3);
INSERT
INTO Trips
(driver_nbr,
bus_nbr)
VALUES
(1,
1),
(1, 2),
(1,
3), --It's the
answer
(2,
1),
(2, 2),
(3,
1),
(3, 2),
(3,
3),
(3, 4);
در داده های نمونه ی ما جواب 1 هست. چرا که تنها راننده شماره 1
دقیقا با تمام اتوبوس ها سفر کرده است، راننده 2 با اتوبوس شماره 3 سفر نکرده و
راننده 3 با اتوبوسی خارج از اتوبوس های جدول Buses سفر
داشته است.
راه حل ها
راه حل اول: طبق فرمول سوم
SELECT
*
FROM Drivers D
WHERE NOT
EXISTS
(SELECT
bus_nbr
FROM Buses
EXCEPT
SELECT bus_nbr
FROM Trips
WHERE
driver_nbr = D.driver_nbr)
AND
NOT EXISTS
(SELECT
bus_nbr
FROM Trips
WHERE
driver_nbr = D.driver_nbr
EXCEPT
SELECT bus_nbr
FROM Buses);
راه حل دوم: طبق فرمول چهارم
SELECT
driver_nbr
FROM Drivers
AS D
WHERE (SELECT
COUNT(*)
FROM (
SELECT bus_nbr
FROM Buses
INTERSECT
SELECT bus_nbr
FROM Trips
WHERE driver_nbr
= D.driver_nbr
) AS D)
=
(SELECT
COUNT(*)
FROM Buses)
AND
(SELECT
COUNT(*)
FROM Buses)
=
(SELECT
COUNT(*)
FROM Trips
WHERE driver_nbr = D.driver_nbr);