وابستگی تابعی
اسلاید 1: فصل پنجموابستگیتابعی)FDوابستگی تابعی (وابستگی تابعی کاملمجموعه پوششی وابستگی نمودار وابستگی تابعی مجموعه وابستگی کمینهمجموعه وابستگی بهینه بستار مجموعه ای از صفاتبه دست اوردن کلید های کاندید
اسلاید 2: فصل پنجم وابستگی تابعی:همانطور که جبر رابطه ای مبنای ریاضی زبان SQL بود، مفهوم ریاضی وابستگی ها نیز مبنای ریاضی بحث نرمال سازی (که در فصل بعدی شرح می دهیم) می باشد. وابستگی ها سه نوع می باشند. 1-وابستگی تابع (FD) که آنها را به طور کامل در این فصل شرح می دهیم. 2- وابستگی چند مقداری (MVD) 3- وابستگی پیوندی (JD) .وابستگی های MVD و JD را در فصل بعدی به صورت خلاصه بیان می کنیم چرا که به صورت کمتر مورد استفاده قرار می گیرند. MVD ها حالت کلی FD ها و JD ها حالت کلی MVD ها می باشند.
اسلاید 3: وابستگی تابعی (FD=Functional Dependency):صفت خاصه Yاز رابطه ی R با صفت خاصه X در رابطه ی R ، دقیقا یک مقدار Y از رابطه ی R متناظر باشند. X و Y می توانند صفات مرکب باشند . اصطلاحا می گوییم صفت خاصه X صفت Y را تعیین می کند.مثال 1 :در جدول زیر نام ، تابعی از شماره است ، ولی فامیلی تابعی از نام نیست .شمارهنامفامیلیعلیعلیحسینیکریمی2211شمارهعلی1122نامحسینیکریمیعلی
اسلاید 4: مثال 2 :در جدول S ، هر یک از صفات خاصه Sname ، status ، city با صفت خاصه S# از همین جدول وابستگی تابعی دارند زیرا به هر مقدار از S# در این رابطه فقط یک مقدار از Sname ، یک مقدار از Status و یک مقدار از city متناظر است . یعنی:S.S# → S.city , S.S#→S.Status , S.S# → S. snameیا به طور خلاصه S.S# → S.(sname , status , city)مثال 3 :در جدولSP داریم: SP.(S# , P#) → SP.Qty یعنی Qty با (S# , P#) وابستگی تابعی دارد.نکته : اگر X کلید کاندید و به ویژه کلید اصلی رابطه R باشد، آنگاه هر صفت خاصه دیگر این رابطه الزاما با باشد، آنگاه هر صفت خاصه دیگر این رابطه الزاما با X وابستگی تابعی دارد چرا که طبق تعریف کلید کاندید یکتایی مقداری دارد . البته در تعریف وابستگی تابعی الزامی ندارد که صفت خاصه X کلید رابطه R باشد ، به بیان دیگر لزومی ندارد که مقدار X فقط در یک تاپل از رابطه R وجود داشته باشد.
اسلاید 5: مثال 4 : در جدول SP’ زیر داریم : sp’ . S# → SP’ . ststus SP’S#P#QtyStatusS1S1S1S1S1S1S2S2P2P1P6P5P4P2P3P14003001004003002002001002020202020201010توجه کنید که در جدول sp’مقدار S# تکرار شده است ولی برای هر S# فقط یک مقدار status وجود دارد .
اسلاید 6: با توجه به مثال فوق می توان تعریف زیر را نیز برای FD ارائه کرد:صفت خاصه Y از رابطه R با صفت خاصه X از رابطه R وابستگی تابعی دارد اگر و فقط اگر هر وقت در دو تاپل ازR ، یک مقدار X وجود داشته باشد ، مقدار Y نیز در آن دو. تاپل یکسان باشد.تعریف فوق مشابه تعریف تابع در ریاضیات معمولی است که می گوید : رابطه ای تابع است که به ازاء هر زوج مرتب که عضو اول یکسان دارند، عضو دوم آنها نیز یکسان باشد. مثلا :رابطه روبرو تابع است اگر b=c باشدR = {(a,b) (a,c)} →
اسلاید 7: تعریف : به سمت چپ یک FD ، دترمینان و به سمت راست آن وابسته می گویند .مثلا در A → B، به A دترمینان وبه B وابسته گفته می شود.نکته 1 : FD ها در واقع محدودیت جامعیت را نشان می دهند و بنابر این DBMS باید آنها را اعمال کند . به عنوان مثال واقعیت S# → city بدین معناست که هر عرضه کننده منحصرا در یک شهر قرار دارد. FD ها یک مفهوم ادراکی هستند.نکته 2 : اگر در رابطه R داشته باشیم :A → B لزوما B → A برقرار نیست. نکته 3 : وابستگی تابعی بین صفات یک رابطه ، یک مفهوم مستقل از زمان است یعنی فقط در مقدار خاصی از متغییر رابطه ای Rو در لحظه خاصی وجود ندارند، بلکه این وابستگی ها ، در صورت وجود ، در جمیع مقادیر R و همیشه برقرارند .نکته 4 : اگر K سوپر کلید رابطه R باشد در این صورت K → R(H) که در آن H مجموعه عنوان R است .نکته 5 : در رابطه تمام کلید ، بین اجزاء کلید ، وابستگی تابعی وجود ندارد .
اسلاید 8: وابستگی تابعی کامل (FFD= Full Functional Dependency) :صفت خاصه Y از رابطه R با صفت خاصه X از رابطه R وابستگی کامل دارد اگر Y با X وابستگی تابعی داشته باشد ولی با هیچ یک از زیر مجموعه های X وابستگی تابعی نداشته باشد . در این تعریف صفت X را مرکب فرض کرده ایم اگر صفت خاصه X مرکب نباشد وابستگی حتما کامل خواهد بود .مثال 5 : در رابطه S صفت خاصه city با صفت خاصه مرکب (S#, Sname) وابستگی دارد یعنی (S# , Sname) → city ولی این وابستگی کامل نیست زیرا S# → CITY یعنی CITY با یکی از زیر مجموعه های (S# , Sname) وابستگی تابعی دارد .
اسلاید 9: مثال 6 : در رابطه sp صفت خاصه Qty با صفت خاصه مرکب (S# , P#) وابستگی تابعی کامل دارد زیرا (S# , P#) → city و Qty با هیچیک از دو جزء S# یا P# به تنهایی وابستگی ندارد.تعریف: اگر برای تمام صفت های B در Rداشته باشیم A → B آنگاه A را ابر کلید B می نامند و اگر این وابستگی از نوع FFD باشد آنگاه A کلید کاندید B است.تعریف: اگر B زیر مجموعه ای از A باشد آنگاه همواره A → B . این وابستگی تابعی را بدیهی (trivial FD) می نامند.
اسلاید 10: مجموعه پوششی وابستگی(بستار وابستگی):هنگام طراحی یک یک بانک در قدم اول می بایست از همه وابستگی های موجود بین صفات خاصه مطلع شد . تعدادی از وابستگی ها ممکن است بدیهی بوده و شناسایی و فهم آنها ساده باشد. همچنین ممکن است کلید ها از همان ابتدا مشخص و معین باشند. ولی گاهی اوقات نیز بعضی از وابستگی ها مستتر بوده و ممکن است در نگاه اول طراح بانک آنها را نبیند.لذا می بایست روش سیستماتیکی بنا نهاد که به کمک آن بتوانیم وابستگی های دیگری را بدست آورده و یا بعضی ازآنها که حزف تازه ای نمی زنند را حذف کنیم . و همچنین بتوان کلید کاندید را بدست آورد . در واقع وابستگی ها قواعد بانک را مشخص می سازند.تعریف: اگر F یک مجموعه از وابستگی های تابعی باشد آنگاه مجموعه تمام وابستگی های تابعی که از آن منتج می شود را مجموعه پوششی یا بستار (closure) می نامیم و باF⁺ نمایش می دهیم.
اسلاید 11: آقای آرمسترانگ در سال 1974 ثابت کرد که با اعمال مکرر سه قاعده زیر می توان می توان به تمام وابستگی های منتج دست یافت و هیچ وابستگی اضافی نیز تولید نمی شود.1) بازتاب (reflexivity) : اگر B زیر مجموعه A باشد آنگاه A → B2) افزایش یا بسط پذیری (augmentation) :اگر A → B و C صفت باشد آنگاه AC → BC 3) انتقال یا تعدی (transitivity) : اگر A → B و b → c آنگاه a → c
اسلاید 12: هرچند قاعده های فوق برای استخراجF⁺ کفایت می کرد ولی اعمال آنها مشکل بود. بعد ها دیگران قواعد دیگری را بیان کردند که کار را سهولت بخشید و مهمترین آنها عبارتند از : 4) اجتماع (union) : اگر A → B و A → C آنگاه A → BC5) تجزیه (decomposition): اگر A → BCآنگاه A → B و A → C 6) ترکیب (Composition) : اگر A → B و C → D آنگاه AC → BD 7) خود تعیینی(self-determination) : A → A 8) شبه تعدی (pseudotransitivity) :اگر A → B و BC → D انگاه AC → D9) اگر A → B و AB → C آنگاه A → C 10) اتحاد کلی (General unification) :اگر A →B و C → D آنگاه Aυ(C-B) → BD
اسلاید 13: مثال 7 : فرمول روبرو را اثبات کنید. AB → C => A → C و A →Bحل:A → B => A → ABAB → C => A → C و A → ABمثال 8 : فرض کنید متغییر رابطه R با صفات A و B و C و D و E و F و FD های زیر موجودند:F={A → BC , B → E , CD → EF } آیا وابستگی AD → F برای R برقرار است یا خیر؟حل: بله چرا که:A→BC => A → CA →C => AD →CDAD → CD , CD →EF => AD → EF AD →EF => AD →Fنکته 1 : از A → BC دو وابستگی A → B و A → C نتیجه می شود ولی در حالت کلی از AB → C نمی توان نتیجه گرفتA → C و یا B → C .
اسلاید 14: نکته 2 : سه قانون اولیه آرمسترانگ یعنی بازتاب، افزایش و تعدی ، قوانین کامل هستند یعنی با توجه به مجموعه F از وابستگی ها و فقط با اعمال این سه قانون می توان F⁺ را بدست آورد . از طرف دیگر این قواعد معتبر هم هستند یعنی هیچ FD اضافی بر آنچه که قابل استنتاج است ، تولید نمی شود.نکته 3 : دو مجموعه وابستگی های تابعی F و G معادل و یا هم ارزند اگر F⁺ مساوی با G⁺ باشد.مثال 9 : فرض کنید داریم (S,T,U,V,W) =R و F= {S → T , V → SW , T → U} وابستگی های تابعی دیگر را بدست آورید.S→T , T→U =>S →U V →SW =>V →S , V→WV →S , S→T => V→TV→S , S→U=> V→Uپس داریم: V→S , V→T , V→U , V→W یعنی V کلید کاندید است.
اسلاید 15: نمودار وابستگی تابعی (FD Diagram) :به کمک این نمودار وابستگی های تابعی یک بانک ترسیم می شود . در این نمودار صفت ها در مستطیل قرار می گیرند و پیکانی از آنها به هر یک از صفتهای وابسته به آن ترسیم می شود .مثال 10 : نمودار وابستگی روابط S و P و SP به شکل زیر است (برای سادگی در جدول S فیلد Sname را حذف کرده ایم )S#P#QtypnameP#cityweightcolorS#statuscity
اسلاید 16: تذکر : اغلب پیکان هایی که وابستگی به کلید اصلی را نشان می دهند در بالای صفتها و سایر پیکانها زیر آنها کشیده می شوند. مچنین معمولا ابتدا مجموعه پوششی بهینه وابستگی ها را بدست آورده و سپس نمودار وابستگی ترسیم می شود. مثلا نمودار FD جدول S معمولا به صورت زیر رسم می شود:S#statuscity
اسلاید 17: مجموعه وابستگی بهینه و مجموعه وابستگی کهینه (کاهش ناپذیر): با اعمال قواعد آرمسترانگ وابستگی های زیادی به دست می آید که تعدادی از آنها اضافی و تکراری هستند . در زیر روشی را برای حذف اینگونه وابستگی های زائد و رسیدن به مجموعه وابسته بهینه ارائه می کنیم.تعریف : دو مجموعه وابستگی تابعی F₁ و F₂ معادل یا هم ارزند اگر مجموعه پوششی آنها برابر هم باشند یعنیF₁⁺ = F₂⁺ .با استفاده از قواعد سه گانه زیر می توان یک مجموعه وابستگی را به مجموعه بهینه معادل آن تبدیل کرد :
اسلاید 18: (1سمت راست هر وابستگی فقط یک صفت باشد. (2هر صفتی که F⁺ را تغییر نمی دهد از سمت چپ حذف شود. (3وابستگی های تکراری و اضافی حذف شود.بطور خلاصه باید گفت که که برای یافتن وابستگی های تابعی در یک بانک ابتدا مجموعه پوششی وابستگی ها را تعیین کرده و سپس آنرا بهینه می کنیم .
اسلاید 19: مثال11 : در بانک اطلاعاتی زیر مجموعه وابستگی پوششی بهینه را بیابید.R = {u,v,w,x,y,z} F = {u →xy , x →y , xy →zy} حل:u→xy , xy→ zy => u →zv =>u→z , u → vu→xy =>u→ x , u→yx → y , xy → zv => x→ zv => x→z , x→ vپس:Fopt ={u→ x, u→ y , x→ y , x→ z, x→v , u→ z , u→ v}
اسلاید 20: توجه کنید با توجه به خاصیت انتقال u→y و u→z و u→ v بدست می آیند پس اگر از ما وابستگی کمینه (کهینه) را خواستند جوانب به صورت زیر است:Fmin={u→x , x→ y , x→z ,x→v} مثال 12 : در یک رابطه وابستگی ها به صورت زیر است:A→(B,C) A→D A→KK→C B→D (B,C) →D
اسلاید 21: نمودار وابستگی را ترسیم کنید. سپس مجموعه کهینه (کمینه) این وابستگی ها را بدست آورده و نمودار آن را رسم کنید.AKDBC (1)(2)(3)(6)(5)(4)
اسلاید 22: الف ) (B,C) → D زائد است چون B → D => (B,D) →D پس فلش (6) را حذف می کنیم .ب) از A → (B,C) می توان نتیجه گرفت A → C , A → B پس می توان فلش (2) را حذف کرد و به جای آن دو فلش از A به B و دیگری از A به C ترسیم کرد:AKDBC (1)(21)(3)(22)(5)(4)
اسلاید 23: ج) فلش شماره 4 زائد است چرا که A → B , B → D => A →D د ) فلش شماره 22 زائد است چرا که A→ K , K → C => A → C پس خلاصه ، شکل کمینه وابستگی به صورت زیر است:همانطور که مشاهده می کنید در شکل کمینه وابستگی ها می بایست : 1- سمت راست هر FD فقط یک صفت باشد. 2- سمت چپ هر FD کاهش ناپذیر باشد. 3- FD زائدی وجود نداشته باشد یعنی هیچ FD به کمک FD های دیگر بدست نیاید.نکته : برای هر مجموعه از FD ها ، حداقل یک مجموعه هم ارز وجود دارد که کاهش ناپذیر است ADBCK
اسلاید 24: بستار(Closure) مجموعه ای از صفات: در این قسمت چگونگی محاسبه زیر مجموعه ای از بستار رانشان می دهیم. یعنی زیر مجموعه ای که حاوی تمام fd هایی است که مجموخه مشخص شده Z از صفات ، به عنوان بخش سمت چپ آنها تعیین شده است . به عبارتی دیگر با توجه به متغییر رابطه R ، مجموعه Z از صفات R و مجموعه F از FD ها که برای R برقرار است ، می توانیم مجموعه ای از تمام صفات R را پیدا کنیم که از نظر تابعی به Z وابسته است و (بستار Z⁺ از Z تحت F) نام دارد . الگوریتم ساده زیر این کار را انجام می دهد:Z⁺:Z;Do for each X→Y in F do if X Z⁺ then Z⁺:=Z⁺ YWhile (Z⁺ did not change)
اسلاید 25: مثال 13 : اگر R=(S,T,U,V,W) و F={S→ T , V→ SW , T→ U} باشد، آنگاه:الف ) {S,V}⁺و ب) {V}⁺ را بدست آورید.حل الف)Z⁺={S,V} , S→ T => Z⁺ = {S,V,T} Z⁺={S,V,T} , V→ SW =>Z⁺={S,V,T,W} Z⁺= {S,V,T,W} , T→ U => Z⁺= {S,V,T,W,U} {S,V}⁺ = {S,V,T,W,U} با تکرار الگوریتم دیگر Z⁺ تغییری نمی کند پس از آنجا که {S,V} تمام صفات R را می دهند پس {S,V} یک سوپر کلید رابطه R می باشد.
اسلاید 26: ب) Z⁺= {V} , S→ T => Z⁺={v} Z⁺={V} , V→ SW =>Z⁺ ={V,S,W} Z⁺= {V,S,W} , T→ U => Z⁺ = {V,S,W} حلقه do-while را دوباره اجرا می کنیم:z⁺={v,s,w} , s→ t => z⁺ = {v,s,w,t} Z⁺= {V,S,W,T} , T→ U => Z⁺ = {V,S,W,T,U} در نتیجه داریم: {V}⁺={V,S,W,T,U}یعنی V نیز یک سوپر کلید است. با توجه به تعریف کلید کاندید در می یابیم که {S,V} کلید کاندید نمی باشدو V کلید کاندید است.
اسلاید 27: بدست آوردن بستار مجموعه ای از صفات دو کاربرد اصلی دارد:1) با توجه به مجموعه ای از FD ها به نام F می توانیم بگوییم که آیا وابستگی خاصی مثل X→Y از F پیروی می کند(قابل استنتاج است) یا خیر. زیرا X→Y فقط و فقط وقتی برقرار است که Y زیر مجموعهای از بستار X⁺ (تحتF) باشد.2) به کمک بدست آوردن X⁺ می توان تعیین کرد که ایا X سوپر کلید (فوق کلید) است یا خیر؟به عبارت دیگر X یک فوق کلید است، اگر و فقط اگر بستار X⁺ دقیقا مجموعه ای از تمام صفات R باشد و X یک کلید کاندید است اگر و فقط اگر یک سوپر کلید کاهش ناپذیر باشد. تذکر: برای محاسبه بستار Z⁺ بهتر است ابتدا F را بهینه کنیم.
اسلاید 28: بدست آوردن کلیدهای کاندیید: برای یافتن کلید های کاندید بهتر است ابتدا F را بهینه کنیم سپس با توجه به نکات زیر کلیدهای کاندید را بدست می آوریم:1) هر کلید کاندید شامل مجموعه ای از صفتهایی است که در سمت چپ پیکانها می آیند.2) کلید کاندید باید کمینه باشد یعنی زیر مجموعه ای از آن خاصیت کلیدی نداشته باشد.3) ممکن است چند کاید کاندید وجود داشته باشد.4) کلید های کاندید ممکن است در یک یا چند صفت مشترک باشند.
اسلاید 29: مثال 14 : اگر F={S→T , V→SW , T→U} و R=(S,T,U,V,W) باشد آنگاه کلید کاندید این رابطه چیست؟حل:S → T , T→ U =>S →U V → SW => V→ S , V→W پس: F={S →T , S →U , T→U , V →S , V→W}V→S , S →T =>V→TV→T , T→U =>V→UF={S →T , S →U , T→U , V →S , V→T , V→U , V→ W} از آنجایی که V همه صفتهای دیگر را میدهد پس کلید کاندید است.
اسلاید 30: مثال 15 : اگر R=(A,B,C,D,E,F,G) و F={AF→BE , FC→DE , F→CD , D→E , C→A} باشد کلید کاندید این رابطه چیست؟حل: ابتدا سمت سراست وابستگی ها را به یک صفت تبدیل می کنیم:F={AF→B , AF→E , FC→D , FC→E, F→C , F→D , D→E , C→A}حال باید صفتهای اضافی را از سمت چپ حذف کنیم.F→C , FC→D , =>F→DF→C , FC→E =>F→EF→C , C→A =>F→AF→A , AF→ B =>F→BF→A , AF→E => F→Eپس:FOPT={F→A , F→B , F→C , F→D , F→E , D→E , C→A}در نتیجه F همه صفت های دیگر بجزG را می دهد. پس{F,G} کلید کاندید است.این کلید کاندید منحصر به فرد است زیرا هیچ صفتی F وG را نمی دهدیعنی در هر کلید کاندید این دو صفت لازم هستند.
اسلاید 31: مثال 16 : در رابطه زیر همه کلیدهای کاندید را بدست آورید.R=(U,V,W,X,Y,Z,O,P,Q)F={U→VXQ , UVP→O , OQ→YZ , UP→XY}حل: ابتدا مجموه بهینه F را پیدا می کنیم:V→VXQ =>U→V , U→X , U→QOQ→YZ =>OQ→ Y , OQ→ZU→V , UVO→O =>UP→OUP→XY =>UP→X , UP→YU→X را قبلا داشته ایم پس UP→X زائد است.پس FOPT={U→V , U→X , U→Q , UP→O , OQ→Y , OQ→Z, UP→Y}
اسلاید 32: حال مجموعه صفتهای وابسته به تمام مجموعه صفتهای چپ پیکانها را می یابیم:{U}⁺ , U→V , U→X , U→X => {U,V,X,Q}{U,P}⁺ , U→V , U→X , U→Q , UP→O , UP→Y , OQ→Z =>{U,P,V,X,Q,O,Y,Z}{O.Q}⁺ , OQ→Y , OQ→Z =>{O,Q,Y,Z}نتیجه می گیریم که بیشترین صفتها را {U,P}⁺ می دهد. تنها صفتی که وابسته {U,P}⁺ نیست W می باشد پس {U,P,W} کلید کاندید است.کلید کاندید دیگری بدست نمی آید زیرا از Oو Q نمی توان به W و U و P رسید پس ابر کلید در این حالت باید {O,Q,P,U,W} باشد که کلید کاندید نیست چرا که زیر مجموعه آن یعنی {P,U,W} کلید کاندید است.