Lim,fan va innovatsiyalar vazirligi muhammad al-xorazimiy nomidagi toshkent axborot texnologiyalari universiteti

OLIY TA’LIM,FAN VA INNOVATSIYALAR VAZIRLIGI

MUHAMMAD AL-XORAZIMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

“Kompyuter arxitekturasi” fanidan

Mustaqil ish
Mavzu: Algoritmlarda dekompozitsiyalash usullari
Bajardi: 042-20 guruh talabasi
_________________________
Tekshirdi: _________________

Toshkent 2023

Reja:
Kirish

1. 
   BCNF ga parchalanish
   
2. 
   3NF ga parchalanish
   
3. 
   Dekompozitsiya va abstraktsiya
   

Xulosa
Foydalanilgan adabiyotlar

Dekompozitsiya algoritmlari
Haqiqiy dunyoda ma'lumotlar bazasi sxemasi ishlov berish uchun juda keng. Shunday qilib, u tegishli ma'lumotlar bazalarini yaratishi mumkin bo'lgan algoritmlarni talab qiladi.Bu erda biz ikki xil normal shakllar uchun funktsional bog'liqliklardan foydalangan holda parchalanish algoritmlari bilan tanishamiz, ular:

• 
  BCNF ga parchalanish
  
• 
  3NF ga parchalanish
  

Funktsional bog'liqliklardan foydalangan holda parchalanish qaramlikni saqlash va yo'qotishsiz parchalanishga qaratilgan.
BCNF ga parchalanish
Berilgan munosabatga BCNF dekompozitsiya algoritmini qo'llashdan oldin, bu munosabat Boyce-Codd Oddiy ko'rinishda ekanligini tekshirish kerak. Sinovdan so'ng, agar berilgan munosabat BCNFda emasligi aniqlansa, biz BCNFda munosabatlarni yaratish uchun uni yanada parchalashimiz mumkin.
Agar berilgan munosabat sxemasi R BCNF qoidasiga javob bersa, quyidagi holatlar tekshirilishi kerak:
1-holat: Tekshiring va sinab ko'ring, agar a -> b bo'lmagan bog'liqlik BCNF qoidasini buzsa, a + ni, ya'ni a atributining yopilishini baholang va hisoblang. Shuningdek, a+ berilgan R munosabatining barcha atributlarini o'z ichiga olganligini tekshiring. Bu R munosabatining yuqori kaliti bo'lishi kerakligini anglatadi.
2-holat: Agar berilgan R munosabati BCNF da bo'lsa, F + dagi barcha bog'liqliklarni sinab ko'rish shart emas . Bu faqat BCNF testi uchun taqdim etilgan F bog'liqlik to'plamidagi bog'liqliklarni aniqlash va tekshirishni talab qiladi. Buning sababi shundaki, agar F ga bog'liqlik BCNF buzilishiga olib kelmasa, demak, F + bog'liqliklarining hech biri BCNF buzilishiga olib kelmaydi.
Eslatma: Agar munosabatlar buzilgan bo'lsa, Case2 ishlamaydi. Bu shuni anglatadiki, berilgan R munosabatini sinovdan o'tkazishda biz F ning BCNF buzilishi sababiga bog'liqligini tekshira olmaymiz.
BCNF parchalanish algoritmi
Agar berilgan R munosabati R 1 , R 2 ,..., R n bir nechta munosabatlarda parchalangan bo'lsa, bu algoritm qo'llaniladi, chunki u BCNFda mavjud emas edi. Shunday qilib,R i munosabatidagi atributlarning har bir a kichik to‘plami uchun a + (F ostida a atributining yopilishi) R i munosabatining barcha atributlarini o‘z ichiga olishini yoki R i -a atributining yo‘qligini tekshirishimiz kerak .
natija={R};
bajarildi = noto'g'ri;
F + ni hisoblash ;
holbuki (bajarilmagan) bajaring, agar (natijada BCNFda boʻlmagan Ri sxemasi mavjud boʻlsa), u holda a->b R i ni ushlab turadigan notrivial funksional bogʻliqlik boʻlsin , a->R i F + da boʻlmaydi. , va a gae b= ø;
natija=(natija-R i ) U (R i -b) U (a,b);
end
else done=true;
Eslatma: Ri dagi ayrim a atributlar to plami algoritmda belgilangan shartni buzsa, bunday holda a->( a+ - a) gae R i funksional bog liqligini ko rib chiqamiz . Bunday qaramlik F + bog'liqligida mavjud bo'lishi mumkin.
Bu algoritm berilgan R munosabatini uning bir nechta parchalovchilariga ajratish uchun ishlatiladi. Bu algoritm R munosabatining parchalanishini bajarish uchun BCNF buzilishini ko'rsatadigan bog'liqliklardan foydalanadi. Shunday qilib, bunday algoritm BCNFda R munosabatining parchalanuvchilarini hosil qilibgina qolmay, balki yo'qotishsiz parchalanish ham hisoblanadi. Bu shuni anglatadiki, berilgan R munosabatini R 1 , R 2 ga va hokazolarga ajratishda ma'lumotlar yo'qolmaydi ...
BCNF dekompozitsiya algoritmi dastlabki munosabat sxemasi R hajmida eksponensial vaqtni oladi. Bu bilan ushbu algoritmning kamchiliklari shundaki, u berilgan R munosabatini keraksiz ravishda parchalashi, ya'ni munosabatni haddan tashqari normallashtirishi mumkin. BCNF va 4NF uchun parchalanish algoritmlari o'xshash bo'lsa-da, farq bundan mustasno. To'rtinchi normal shakl ko'p qiymatli bog'liqliklarda ishlaydi, BCNF esa funktsional bog'liqliklarga qaratilgan . Ko'p qiymatli bog'liqliklar ma'lumotlarning takrorlanishining ba'zi shakllarini kamaytirishga yordam beradi, bu funktsional bog'liqliklar nuqtai nazaridan tushunarsizdir.
Ko'p qiymatli bog'liqlik va funktsional bog'liqlik o'rtasidagi farq
Ikkala bog'liqlik o'rtasidagi farq shundaki, funktsional bog'liqlik muayyan kortejlarni aloqada bo'lishdan chiqarib tashlaydi, lekin ko'p qiymatli bog'liqlik buni qilmaydi. Bu shuni anglatadiki, ko'p qiymatli qaramlik ma'lum kortejlarni chiqarib tashlamaydi yoki istisno qilmaydi. Aksincha, u muayyan shakllarning boshqa kortejlari bilan bog'liq holda mavjud bo'lishini talab qiladi. Bunday farq tufayli ko'p qiymatli bog'liqlik kortej hosil qiluvchi bog'liqlik, funktsional bog'liqlik esa tenglikni hosil qiluvchi bog'liqlik deb ataladi.
3NF ga parchalanish
3NF uchun dekompozitsiya algoritmi kanonik qopqoqdagi har bir qaramlik uchun sxemani aniq qurish orqali bog'liqliklarning saqlanishini ta'minlaydi. Bu kamida bitta sxemada parchalanayotgani uchun nomzod kaliti bo'lishi kerakligini kafolatlaydi, bu esa o'z navbatida hosil bo'lgan parchalanishning yo'qotishsiz parchalanishini ta'minlaydi.
3NF parchalanish algoritmi
Fc F uchun kanonik qopqoq bo'lsin;
i=0;
har bir funksional bog’liqlik uchun a->b da F c
i = i+1;
R = ab; Agar R j , j=1,2,…I
sxemalaridan hech biri bo'lmasa, R uchun nomzod kaliti bo'lsa
, i = i+1;
R i = R uchun istalgan nomzod kaliti;
/* Majburiy emas, takrorlanuvchi munosabatlarni olib tashlang*/
Takrorlash
Agar boshqa sxemada R j sxemasi mavjud bo'lsa Rk
Keyin
/* O'chirish R j */
R j = R i ;
i = i-1;
Rj-larni o'chirib bo'lmaguncha
qaytaring (R 1 , R 2, . . . ,R i )
Bu erda R - berilgan munosabat, F - berilgan funktsional bog'liqlik to'plami, F c kanonik qoplamani saqlaydi. R 1 , R 2 ,. . . , R i - berilgan R munosabatining parchalangan qismlari. Shunday qilib, bu algoritm R munosabatining yo'qotishsiz parchalanishini hosil qilish bilan bir qatorda bog'liqlikni ham saqlaydi.
3NF algoritmi 3NF sintez algoritmi sifatida ham tanilgan. Oddiy shakl bog'liqlik to'plamida ishlashi va dastlabki sxemani qayta-qayta parchalash o'rniga, bir vaqtning o'zida bitta sxemani qo'shib qo'ygani uchun shunday nomlanadi.