صفحه 1:
صفحه 2:
فصل پنجم وابستگی تابعی
٩ همانطور که جبر رابطه ای مبنای ریاضی زبان -5001 بود. مفهوم ریاضی وابستگی
ها نیز مبنای GL) بحث نرمال سازی (که در فصل بعدی شرح می دهیم) می
باشد. وابستگی ها سه نوع می باشند. (-وابستگی تابع (۴0) که آنها را به طور
كامل در اين فصل شرح مى دهيم.
۲- وایستگی چند مقداری (۷۲) ۳- وابستگی ييوندى JD) .
٩ وابستگی های 9۷۲ حا[ را در فصل بعدی به صورت خلاصه بیان می کنیم
چرا که به صورت کمتر مورد استفاده قرار می گیرند. ۷۲ ها حللت کلی ۴۲۱
0 حطا[ ها حالت کلی ۷۷9 ها می باشند.
صفحه 3:
وابستگی تابعی (۲9>۲۱۱۱۲۱۵۱۱۸۵۱
(DEPENDENCY
© صفت خاصه ۲از رابطه ی O R صحفت خاصه 2 در رابطه ی ۳ ۰ دقیقا یک
مقدار ۷ از رابطه ی ۵ متناظر باشند. 2 و ۷ می توانند صفات مرکب
باشند . اصطلاها می گوییم صفت X cuold صفت ۷ ا تعیین می کند.
٩ مثال ۱ :در جدول زیر نام . تابعی از شماره است . جلی فامیلی تابعی از نام
نیست .
مسینی فامیلی | نام أشماره
f-\ مسیتی علی ۱ 11
كريد علی
9 | كريمى ) على | 22
تست
©@ -
شماره <--
22 11
صفحه 4:
٩ مثال ۲ :در جدول G Sname . Status . city ald claw jl Gy po. S صحفت خاصه 5* از همین
جدول وابستگی تابعی دارند زیرا به هر مقدار از ۶5 در این رابطه فقط یک مقدار از jade chy. SMAME
از 5لا5]3 ويك مقدار از لانأأء متناظر است . يعنى:
6 5.5# 5لاأ5.563-5.5# , لإأأه.5 ه , 5.5# > S. sname
S.S# > S.(sname , status , city) یا به طور خلاصه ٩
٩ مثال ۳ :در جدول 58 داریم: 5۴0۷ - (۳# , 5۳)5# یعتی (#S# , P) b Qty وابستکی تابعی
دارد.
© نکته : اکر لا کلید کاندید و به ویژه کلید اصلی رابطه * باشد. آنگاه هر صفت قاصه دیگر این رابطه الزاما
با باشد. آنگاه هر صفت خاصه دیگر این رابطه الزاما با 6( وابستگی تابعی دار چرا که طبق تعریف کلید
کاندید یکتایی مقداری دارد . البته در تعریف وابستکی تابعی الزامی ندارد که صفت خاصه ۱ کلید رابطه
89 ۰ به بیان دیگر لزومی ندارد که مقدار ۱ فقط در یک تاپل از رابطه 6 وجود داشته باشد.
صفحه 5:
*مثال ع : در جدول 5۳" زیر داریم : . 5۳۳ جه sp’ . S#
ststus
sP_ 6 P| Qty Status
eet
& pf | 300, 20
51 P2 | 200 20
0 ۱ 00 ۱ ۴3 51
۰0 200 | 4 51
20 100 ۱ ۴5 51
۰0 100 ۱ ۴6 51
مد 300 ۱ ۴1 52
10 400 ۱ ۳2 52
توجه کنید که در جدول 50"مقدار #5 تکرار شده است ولی برای هر #5 فقط
یک مقدار ly 9949 StatUS «
صفحه 6:
٩ با توجه به مثال فوق می توان تعریف زیر را نیز برای ۴۲ ارائه کرد:ء
© صفت خاصه ۷ از رابطه ۴ با صحفت خاصه 2 از رابطه ۲ وابستگی تابعی دارد
اكر و فقط اگر هر وقت در دو تاپل از ۰ یک مقدار 2 وجود داشته باشد ,
مقدار ۷ نیز در آن دو. تاپل یکسان باشد.
: تعریف فوق مشابه تعریف تابع در ریاضیات معمملی است که می گوید ٩
رابطه ای تابع است که به ازاء هر زوم مرتب که عضو اول یکسان دارند. عضو
: دوم آنها نیز یکسان باشد. مثلا
> R= {(a,b) رابطه رویرو تابع است اگر 0 باشد ([(ع,۵) ٩
صفحه 7:
. تعریف : به سمت چپ یک ۴0 . دترمینان و به سمت راست آن وابسته می گویند ٩
٩ مثْلا در 5 «- ۵ به ۸ دترمینان وبه 8 وابسته گفته می شود.
٩ نکته ۱: ۴0 ها در واقع ممدودیت جامعیت را نشان مى دهند و بنابر اين 081/15 بايد آنها را اعمال
كند . به عنوان مثال واقعيت لإأأء +- 5# بدين معناست كه هر عرضه كننده منحصرا در يك شهر قرار
دارد. ۲0 ها یک مفهوم ادراکی هستند.
٩ نکته ۲: اکر در رابطه ٩ داشته باشیم :8 <- ۸۵ لزوما ۸۵ - 8 برقرار نیست.
نکته ۳ : وابستگی تابعی بین صفات یک رابطه . یک مفهوم مستقل از زمان است یعنی فقط در مقدار
خاصی از متغییر رابطه ای و در لحظه خاصی وجود ندارند. بلکه این وابستگی ها . در صورت وجود , در
جمیع مقادیر ۴ و همیشه برقرارند .
cual ٩ که در آن ۲۷| مجموعه عنوان -< ۳/( باشد در این صورت R نکته ۴ : اگر 1 سوپر کلید رابطه ٩
© : در رایطه تمام کلید « بين اجزاء کلید « وابستگی تابعی ومود ندارد .
صفحه 8:
وابستقی of 4 کامل FFD= FULL FUNCTIONAL)
:(DEPENDENCY
0 صفت خاصه ۷ از رابطه ۶ با صحفت خاصه < از رابطه ۲ وایستگی کامل دارد
اکر ۷ با 2 وابستگی تابعی داشته باشد ملی با هیچ یک از زیر مجموعه های
وابستگی تابعی نداشته باشد . در این تعریف صفت © را مركب فرظ
کرده ایم اگر صفت خاصه 2 مرکب نباشد وایستگی حتما کامل خواهد بود .
٩ مثال ۵ : در رابطه 5 صفت خاصه Gaw & City خاصه مرکب S#,)
وابستگی دارد یعنی (50۵۳06 , 5#) + city ولی این
وابستگی کامل نیست زیرا 01۲۷ - 5# یعنی ۱۲۷ با یکی از زیر
سس های (5۳6۲۱6 , 6#) وابستگی تابعی دارد .
صفحه 9:
)#57# , 5( مثال ب : در رابطه 50 صفت خاصه 0۷ با صفت خاصه مرکب ٩
وابستگی تابعی کامل دارد زیرا (5 , 57# #) ه لإأأه و /ا0 با هيجيك
از دو جزء ۶5یا ۶۴ به تنهایی وایستگی ندارد.
۸ تعریف: اگر برای تمام صفت های ظ در چآداشته باشیم 8 - ۸۵ آنگاه ٩
باشد آنگاه ۸ کلید FFD را ابر کلید 5 می نامند و اگر این وابستگی از نوع
کاندید 5 است.
٩ تعریف: اگر 5 زیر مجموعه ای از ۸ باشد آنگاه همواره 8 + ث . اين
وابستگی تابعی را بدیهی (۲۲ اه ۲۱۷) می نامند.
صفحه 10:
مجموعه پوششی وابستکی(بستار وابستکی):
OY 29994 Slo هنگام طرامی یک یک بانک در قدم اول می بایست از همه وابستگی ٩
صفات خاصه مطلع شد . تعدادی از وابستگی ها ممکن است بدیهی بوده و شناسایی و
خهم آنها ساده باشد. همچنین ممکن است کلید ها از همان ابتدا مشخص و معین باشند.
aly ملی گاهی اوقات نیز بعضی از وابستگی ها مستتر بوده و ممکن است. در نگاه اول
بانک آنها را نبیند.
٩ نذا می بایست روش سیستماتیکی بنا نهاد که به کمک تن بتوانیم وابستگی های دیگری
by بدست آورده و یا بعضی ازآنها که حزف تازه ای نمی زنند | حذف کنیم . و همچنین
بتوان کلید کاندید را بدست آورد . در واقع وابستگی ها قواعد بانک را مشخص می سازند.
تعریف: اگر ۳ یک مجموعه از وابستگی های تابعی باشد آنگاه مجموعه تمام وابستگی
ای تابعی که از آن منتم می شود را مجموعه پوششی یا بستار (105۱1۲6) می نامیم و
با۳* نمایش می دهیم.
صفحه 11:
© آقاى آرمسترانگ در سال ۱۹۷۱۴ ثابت کرد که با اعمال مکرر سه قاعده زیر
می توان می توان به تمام وابستگی های منتج دست يافت و هيج وابستگی
اضافی نیز تولید نمی شود.
) بازتاب (۲6۲۱6۷۱) : اگر 5 زیر مجموعه ۸۵ باشد آنگاه 8 + A
۲) افزایش یا B 55k: (Augmentation) ois buy > 8 و © صفت باشد
آنگاه 8 د AC
CoA 2 B 551: (transitivity) 6303 & JEDI (PY > 9 آنگاهء جه جح
صفحه 12:
هرچند قاعده های فوق برای استخراج ۴* کفایت می کرد ولی اعمال آنها مشکل بود. بعد ها
دیگران قواعد دیگری را بیان کردند که کار را سهولت. بفشید و مهمترین آنها عبارتند از :
عا) اجتماع (11010انا) : اكر 8 > C 9 A > ۸ آنگاه A > BC
A> CoA > B ۵آنگاه > BC 351 :(decomposition) «jas (0
AC > BD 031 C > Dy A > B j5!: (Composition) a5) (¥
AA: (self-determination)c ines خود ۷
Dy A> B 55k: (pseudotransitivity) 6x05 au (A > 80 انكاه
ACD
9 اكر 8 + لك و © - ۸5 آنگاه © ج لم
() تماد كلى D 9 A 3B 551: (General GOINEaHON - 6 آنگاه
م8 ج (0-8)دام
صفحه 13:
٩ مثال ۷ : فرمول روبرو را اثبات کنید.
۸8 )۸۰ << + ۸8 5
٩ مل:
8 ۸ << ق ددم ه
9A>AB 0 ددم << + ۸۵8 9
٩ مثال ۸ : فرض کنید متغییر رابطه با صفات 2 و 8 و © و0 و ع و ۴ و ۴0 های زیر
مومودند:
F={A>BC, B>E,CD>EF} ©
٩ آیا وابستگی ۴ - ۸۵0 برای 2 برقرار است یا خیر؟
٩ مل: بله چرا که:
6 ۸ << 8ب 9
0ه مم <- 0د م ه6
EF > مم <ح ععه 00 , 00 + زم 6
AD ~EF => AD >F °
A > C9 AWB tim ABC) lD نتیجه می شود ولی در للت کلی از
C > 88 نمى توان نتيجه كرفت© ه له ويا © ه 8 .
صفحه 14:
نکته ۲ سه قانون اولیه آرمسترانک یعنی بازتاب. افزایش و تعدی . قوانین کامل هستند يعنى با توبه به مجموعه ۴ از
وابستگی ها و فقط با اعمال این سه قانون می توان ۶* را بدست آورد .از طرف دیگ این قواعد معتبر هم هستند یعنی
هیم ۴0 افنافی بر آنچه که قابل استنتاج است , تولید نمی شود.
نکته ۳ : دو مجموعه وابستگی های تابعی ۴ و 6 معادل و یا هم ارزند اکر ۴ * مساوی با 6* باشد.
امثال ٩ : فرض کنید داریم (6,۲,۱(,۷,۷۷) ع8 و {S 9 T, V> SW, T > U} <] وابستگی های تابعی دیگر را
بدست آورید.
لاد 5<ع لاب] , آمو 6
۷-۷ , و 2<۷ 5۷ ۷ 5
۷+۲ << ]بو ر, کب 0۷
لا-۷ <علابو , 6۱۷-5
پس داریم:
۷-۷ , لاب-۷ , ۷-۲ , ودلا
ی کلید کاندید است.
صفحه 15:
نمودار وابستگی تابعی 0۱۵6۴۵۷ ۴0):
٩ به کمک این نمودار وابستگی های تابعی یک بانک ترسیم می شود . در این
نمودار صفت ها در مستطیل قرار می گیرند و پیکانی از آنها به هر یک از
صفتهای وابسته به آن ترسیم می شود .
٩ مثال ۱۰ : نمودار وابستگی روابط 5 و ۴ و 5۳ به شکل زیر است (برای
سادگی در جدول 5 فیلد 503176 را حذف كرده ايم )
< تت
صفحه 16:
٩ تذکر : اغلب پیکان هایی که وابستگی به کلید اصلی را نشان می
دهند در بالال صقتها و سایر پیکانها زیر آنها کشیده می شوند.
مچنین معمبلا ابتدا مجموعه پوششی بهینه وابستگی ها را بدست
آورده و سپس نمودار وابستگی ترسیم می شود. مثلا نمودار ۲0
جدول 5 معمولا به صورت زیر رسم می شود:
|
صفحه 17:
مجموعه وابستگی بهینه و مجموعه وابستگی کهینه (کاهش ناپذیر):
0 با اعمال قواعد آ رمسترانگ وابستگی های زیادی به دست می آید که تعدادی
از آنها اضافی و تکراری هستند . در زیر روشی را برای حذف اینگونه وابستکی
slo زائد و رسیدن به مجموعه وابسته بهینه ارائه می کنیم.
٩ تعریف : دو مجموعه وابستگی تابعی ۳۰ و ۴2 معادل یا هم ارزند اگر
مجموعه پوششی آنها برابر هم باشند یعنی<۴ < Fit
7 با استفاده از قواعد سه گانه زیر می توان یک مجموعه وابستگی را به
مجموعه بهینه معادل آن تبدیل کرد :
صفحه 18:
(اسمت راست هر وایستگی فقط یک صفت باشد.
(لاهر صفتی که ۲۴۲ را تغییر نمی دهد از سمت چپ هذف شود.
(۳وابستگی های تکراری و اضافی حذف شود.
٩ بطور خلاصه باید گفت که که برای یاختن وابستگی های تابعی در یک بانک
ابتدا مجموعه پوششی وابستگی ها را تعیین کرده و سپس آنرا بهینه می
کنیم .
صفحه 19:
مثال۱۱ : در بانک اطلاعاتی زیر مجموعه وابستگی پوششی بهینه را بیابید.
R = {u,v,w,x,y,z} F = {u >xy , x >y, xy
>zy}
sda 2
Supxy , Xy> zy => U PZV =>uUPZ, UV
Surxy =>u> لا را
Oxy, XY 9 اج => X9 ZV => XPZ, XPV
={u> x, ue y, xX>y,x>Z, Xxev,u>Zz,uU> Vv}
OF,
opt
صفحه 20:
٩ توجه کنید با توجه به خاصیت انتقال دنا و 2دلا و ۷ جلا
بدست می آیند پس اگر از ما وابستكى كمينه (كهينه) را فواستند
جواتب به صورت زیر است:
6۳ الا , XP Y , XPZ ار
٩ مثال ۱۲ : در یک رابطه وابستگی ها به صورت زیر است:
A-K مادم °A>(B,C)
مج رع,8) مدق 9
صفحه 21:
نه (کمی
oy
0 مجمو:
سيس مج
بستگی را ترسیم
ار
نمودار
۰
ها Cw. اسم کنید.
»
بستکی نمودار آن را
5 ادار
5 آورده و
ابد
لك (! ب
ن واد
اين
4
(6
)
صفحه 22:
© الف ) (©,8) + 8 زائد است چمن تاد B > D => (B,D) پس فلش
() را حذف مى كنيم .
© ب) از (©,8) + م مى توان نتيجه كرفت 8 ه 8 , © +ه ۸۵ پس می
توان فلش (۲) را مذف کرد و به جاى كن دو فلش از ۸ به 8 و دیگری از ۸ به
) ترسیم کرد: 4(
صفحه 23:
٩ ه) فلش شماره ۴ زائد است چرا که ناب ۸ << 0 + 8 , 8 + لم
٩ د) فلش شماره ۲۲ زائد است چرا که ) - ۸ << ) با رک مه
© يس خلاصه . شکل کمینه وابستگی به صورت زیر است:
۴0 همانطور که مشاهده می کنید در شکل کمینه وایستگی ها می بایست : ۱- سمت راست هر ٩
باشد. ۷- سمت چپ هر ۴0 کاهش ناپذیر باشد. ۳- ۲0 زائدی وجود نداشته cabo Gy bad
به کمک ۴0 های دیگر بدست نیاید. FD شد يعنى هيج
7 نک : برای هر مجموعه از ۴۲0 ها . مداقل یک مجموعه هم ارز مجود دارد که کاهش ناپذیر است
صفحه 24:
بستار(ر 5۱1۴ 21۵)) مجموعه ای از صفات:
در این قسمت چکونگی محاسبه زیر مجموعه ای از بستار رانشان می دهیم. یعنی
زیر مجموعه ای که حاوی تمام ۴0 هایی است که مجموخه مشخص شده 2
از صفات . به عنوان بخش سمت چپ آنها تعیین شده است . به عبارتی دیگر
با توجه به متغییر رابطه . مجموعه > از صفات ۲ و مجموعه ۴ از ۲۱ ها
که برای ۲ برقرار است . می توانیم مجموعه ای از تمام صفات ۳ را پیدا کنیم
که از نظر تابعی ay 2 وابسته است و (بستار 2* از 2 تحت ]) نام دارد .
الگوریتم ساده زیر این کار را انجام می دهد:
2:2
Do
foreach XY in F do
if Z* then
222+ a: 3 ©
While (Z* did not change)
صفحه 25:
٩ مثال ۱۳ : 351 SW, T> U} 9 R=(S,T,U,V,W) جلا , 7 +5) -] باش
آنگاه:
٩ الف ) (۳15,۷وب) (۷)* را بدست آورید.
٩ مل الف)
OZ+={SV} , SeT => Z* = {SVT}
©Zt={SV,T} , V2 SW =>Zt={S,V,T,W}
°Z+= {S,V,T,W} , T> U => Zt= {S,V,T,W,U}
° {S,V}* = {S,V,T,W,U}
ووارچکرار الکوریتم دیکر 2* تغییری نمی کند پس از آنجا که 15,۷۱ تمام صفات 5 را
ee (15,۷ یک سوپر کلید رابطه 6 می باشد.
صفحه 26:
0 2*- 0 , So9T => Z*={v}
©Z*={V} , V>SW =>Z* ={V,S,W}
°Zt= {V,S,W} , T2U => Zt = {V,S,W}
حلقه 00-۷۱۱6 را دوباره اجرا می کنیم: ٩
°zt={v,s,w} , set => zt = {v,s,w,t}
© Z+= {V,S,W,T} , T2? U => Z* = {V,S,W,T,U}
© در نتیجه داریم: {V,.S.W,T,U} =*{V}
٩ یعنی ۷ نیز یک سوپر کلید است. با توجه به تعریف کلید کاندید در می یابیم که
,5 کلید کاندید نمی باشدو ۷ کلید کاندید است.
صفحه 27:
٩ بدست آوردن بستار مجموعه ای از صفات دو کاربرد اصلی دارد:
۱) با توجه به مجموعه ای از ۴۵ ها به نام ۴ می توانیم بگوییم که آیا دابستکی
خاصى مثل 6-7 از "ا ييروى مى كند(قابل استنتاج است) يا خير. XY Wy)
فقط و فقط وقتى برقرار است كه زير مجموعهاى از بستار 6ا* (تحت ) باشد.
نا) به كمك بدست آوردن (* می توان تعیین کرد که ایا ۱ سجپر کلید (فوق
کلید) است یا خیر؟
٩ به عبارت دیگر 6 یک فوق کلید است. اگر و فقط اگر بستار (* دقیقا مجموعه
ای از تمام صفات ۳ باشد و 2 یک کلید کاندید است اگر و فقط اگر یک سوپر
کلید کاهش ناپذیر باشد.
2 برای محاسبه بستار 2* بهتر است ابتدا ۴ ا بهینه کنیم.
صفحه 28:
بدست آوردن کلیدهای کاندیید:
٩ برای یافتن کلید های کاندید بهتر است ابتدا ۴ را بهینه کنیم سپس با توجه به
نکات زیر کلیدهای کاندید را بدست می آوریم:
۱) هر کلید کاندید شامل مجموعه ای از صفتهایی است که در سمت چپ پیکانها
هی آیند.
۲ کلید کاندید باید کمینه باشد یعنی زیر مجموعه ای از گن خاصیت کلیدی
نداشته باشد.
۳) ممکن است چند کاید کاندید وجود داشته باشد.
۴) کلید های کاندید ممکن, است در یک یا چند صفت مشترک باشند.
صفحه 29:
٩ مثال 1 :451 R=(S,T,U,V,W) 9 F={ST , V>SW , TU} باشد آنگاه
کلید کاندید این رابطه چیست؟
89 هل:
لاب 5<ع لاج+] , ۲ مب 65
۷-۷ , 5 +۷ << 5۷ ب 6۱۷
0 پس: ۷-۰۷ , 5 ۷ , لاد۲ , لاد 5 , آ+ ۴<)5
1 ج/ا<- 1ه و , ودلا 6
لاب-۷<< لاب] , OVRT
(للا جلا , لادلا , 1لا , ود ۷ , لاد , لاد 5 ر, آجد F={S ©
6 آنباین که ۷ همه صفتهای دیکر را میدهد پس کلید کاندید است.
صفحه 30:
F={AF>BE , FC>DE , FoCD , 9 R=(A,B,C,D,E,F,G) )51: 10 مثال ۲
DE , CoA} باشد کلید کاندید این رابطه چیست؟
© هل: ابتدا سمت سراست وابستگی ها را به یک صفت تبدیل می کنیم:
۱ CA}
© حال باید صفتهای اضافی را از سمت چپ حذف کنیم.
6 طم۲<ع , مدمع , ممع
9 ۴6, عدع<- عس۲
FSC, CoA مدع<-
6 مدع , AF> B =>F>B
© FA, AFSE => FoE
© پس:
© Fopp= {FA , FoB, FoC , FoD, FoE, DoE, C>A}
" درونتیجه ۳ همه صفت های دیگر بجز6) را می دهد. پس [),۳) کلید کاندید است.
sts مندسربه رد است زا میم سفق ۴و2 نمی دمدمن در هر كليد guts ید ١
اين دو صفت لازم هستند.
صفحه 31:
7" مثّال ۱۶: در رابطه زیر همه کلیدهای کاندید را بدست آورید.
R=(U,V,W,X,Y,Z,0,P,Q) ©
F={U>VXQ , UVP3O , OQYZ , UP>XY} ©
a © ابتدا مجموه بهینه ۴ را پیدا می کنیم:
4دلا, (بلا , لاجدلا< ع كا/اجد/ا 6
OQYZ =>0Q> Y , 00-72 ©
U-V , UVO-0 =>UP-0 ©
UP=XY =>UP—>X , UP-Y ©
,ولا را قبلا شته لیم پس(-۳لا زنتدلست
Fopr={UV , UX , UQ, UP30 , OQ9Y , OQZ, UPY} um ©
صفحه 32:
حال مجموعه صفتهای وابسته به تمام مجموعه صفتهای چپ پیکانها | می یابیم:
(0,,/ا,لا) <ع كاج لا , لادلا , {U}* , UeV ©
00-2 , لادملا , 0هملا , 0لا , كاهلا , لاملا , +[(صرلا)4 ه
=>{U,P,V,X,Q,0,Y,Z}
{0.Q}* , OQY , OQ9Z =>{0,Q,Y,Z} ©
© نتيجه می گیریم که بیشترین صفتها )1 *{U,P} 0( دهد. تنها صفتی که وابسته (۱,۳)*
نیست ۷۷ می باشد پس (۱(,۳,۷۷) کلید کاندید است.
٩ کلید کاندید دیگری بدست نمی آید زیرا از 90 ۵ نمی توان به ۷۷ و لاو ۴ رسید پس ابر
الأ ايه حلت بيد (0,0,۴,۱(,۷۷) باشد که کلید کاندید نیست چرا که زیر مجموعه
آن یعنی ۳,۷(,۷۷۱! كليد كانديد است.