مفاهیم پایگاه داده های رابطه ای و نرمال سازی

ما در فصل2 جبر رابطه ای را ارائه کردیم که اشکال پایه ای در بسیاری از مواردی هستند که در زبان SQL Query استفاده می شوند جزئیات بیشتر در فصل های 3 و 4 ارائه شد در این فصل ابتدا دوزبانی را که بیشتر رسمیت دارند را مطالعه می کنیم یکی حساب رابطه ای چندتایی و یکی حساب رابطه ای حوزه که این دو زبان رسمی زبان هایی هستند بر پایة پرس و جو1 و مبتنی بر منطق

دسته بندی	ریاضی
فرمت فایل	doc
حجم فایل	1210 کیلو بایت
تعداد صفحات فایل	283

دریافت فایل

فروشنده فایل

کد کاربری 8044

تمام فایل ها

فهرست مطالب

عنوان صفحه

فصل پنجم - دیگر زبانهای رابطه ای ............................................................................................................................... 1

5-1- حساب رابطه ای چند تایی ......................................................................................................................................... 3

5-1-1- طرح مثال ............................................................................................................................................................. 4

5-1-2- تعاریف رسمی ....................................................................................................................................................... 9

5-1-3- اطمینان در بیان ...................................................................................................................................................... 11

5-1-4- زبان های توانای پر معنی ....................................................................................................................................... 12

5-2- قلمرو حساب رابطه ای ............................................................................................................................................. 13

5-2-1- تعریف رسمی ..................................................................................................................................................... 13

5-2-2- پرس وجوهای نمونه ............................................................................................................................................. 14

5-2-3- ایمنی عبارات ....................................................................................................................................................... 16

5-2-4- قدرت بیانی زبان .................................................................................................................................................. 18

5-3- پرس وجو از طریق مثال ............................................................................................................................................ 19

5-3-1-جدول های ساختمان ............................................................................................................................................. 20

5-3-2- پرس وجو هایی روی یک رابطه ........................................................................................................................... 20

5-3-3- پرس وجو روی رابطه های جداگانه ..................................................................................................................... 25

5-3-4- جعبه وضعیت ...................................................................................................................................................... 27

5-3-5- رابطه نتیجه .......................................................................................................................................................... 30

5-3-6- QBEدر مایکروسافت اکسس ............................................................................................................................. 32

5-4- دیتالوگ ................................................................................................................................................................. 35

5-4-1- ساختار اساسی ..................................................................................................................................................... 35

5-4-2- ترکیب دستورات دیتالوگ .................................................................................................................................. 38

5-4-3- ترکیب های معنایی دیتالوگ غیر بازگشتی .......................................................................................................... 42

5-4-3-1- ترکیب های معنایی یک دستور ........................................................................................................................ 42

5-4-3-2- ترکیب معنایی برنامه ........................................................................................................................................ 44

5-4-4- ایمنی .................................................................................................................................................................. 47

5-4-5- عملیاتهای رابطه ای در دیتالوگ .......................................................................................................................... 49

5-4-6- بازگشتی در دیتالوگ .......................................................................................................................................... 51

5-4-7- قدرت بازگشتی .................................................................................................................................................. 56

5-5- خلاصه ................................................................................................................................................................... 59

مرور اصطلاحات ............................................................................................................................................................ 60

تمرین مهارت .................................................................................................................................................................. 61

تمرین ها ......................................................................................................................................................................... 63

نکاتی مربوط به فهرست کتاب .......................................................................................................................................... 66

ابزارها ............................................................................................................................................................................. 67

بخش دوم :طراحی پایگاه داده ....................................................................................................................................... 68

فصل ششم: طراحی پایگاه داده مدل E-R .................................................................................................................. 70

6-1- مفهوم کلی فرایند طراحی ....................................................................................................................................... 71

6-1-1- مراحل طراحی ................................................................................................................................................. 72

6-1-2- طراحی جایگزین ها .......................................................................................................................................... 74

6-2- مدل موجودیت رابطه ........................................................................................................................................... 75

6-2-1- گروه موجودیت ............................................................................................................................................. 76

6-2-2- گروه رابطه ها .................................................................................................................................................. 78

6-2-3- صفات ............................................................................................................................................................. 83

6-3- محدودیت ها ........................................................................................................................................................ 87

6-3-1- ترسیم کاردینالیتی ............................................................................................................................................ 87

6-3-2- کلیدها ............................................................................................................................................................. 89

6-3-2-1- گروه موجودیت ها ...................................................................................................................................... 90

6-3-2-2- گروه رابطه ها .............................................................................................................................................. 91

6-3-3- مشارکت محدودیت ها .................................................................................................................................. 93

6-4- نمودارهای موجودیت – رابطه ............................................................................................................................ 93

6-5- نتایج طراحی موجودیت – رابطه ......................................................................................................................... 102

6-5-1- استفاده از گروه موجودیت ها در مقابل صفات ............................................................................................... 102

6-5-2- استفاده از گروه موجودیت ها به جای گروه رابطه ها ...................................................................................... 105

6-5-3- گروه رابطه های n-ary در مقایل دوگانه ...................................................................................................... 106

6-5-4- جایگاه صفات رابطه ..................................................................................................................................... 109

6-6- گروه موجودیت ضعیف .................................................................................................................................... 111

6-7- ویژگیهای E-R گسترده .................................................................................................................................. 114

6-7-1- ویژه کاری .................................................................................................................................................... 115

6-7-2 – عمومی سازی .............................................................................................................................................. 118

6-7-3- صفات وراثتی ............................................................................................................................................... 120

6-7-4- محدودیت ها در عمومی سازی ..................................................................................................................... 121

6-7-5- ترکیب ......................................................................................................................................................... 125

6-7-6- نمادهای E-R جایگزین ............................................................................................................................... 128

6-8- طراحی پایگاه داده برای پروژه بانکداری ........................................................................................................... 130

6-8-1- جایگزین های طرح E-R .............................................................................................................................. 131

6-8-2- الزامات داده برای پایگاه داده بانک ................................................................................................................ 132

6-8-3- گروه های موجودیت برای پایگاه داده بانک ................................................................................................. 134

6-8-4- گروه های رابطه برای پایگاه داده بانک .......................................................................................................... 135

6-8-5- نمودار E-R برای پایگاه داده بانک .............................................................................................................. 136

6-9- تبدیل شدن به الگوی رابطه ای .......................................................................................................................... 136

6-9-1- ارائه گروه های موجودیت قوی ..................................................................................................................... 138

6-9-2- ارائه گروه های موجودیت ضعیف ................................................................................................................ 139

6-9-3 – ارائه گروه های رابطه .................................................................................................................................. 140

6-9-3-1- الگوهای زائد ............................................................................................................................................ 142

6-9-3-2- ترکیب الگوها ........................................................................................................................................... 142

6-9-4- صفات ترکیبی و چند مقداری ....................................................................................................................... 144

6-9-5- ارائه روش عمومی سازی ............................................................................................................................. 145

6-9-6- ارائه دادن ترکیب ......................................................................................................................................... 147

6-9-7- الگوی رابطه برای پروژه بانکداری ................................................................................................................ 148

6-10- جنبه های دیگر طراحی پایگاه داده ................................................................................................................. 149

6-10-1- محدودیت داده ها وطراحی پایگاه داده رابطه ای ........................................................................................ 150

6-10-2- الزامات کاربردی : پرس وجوها ، کارایی .................................................................................................... 151

6-10-3- الزامات کنترل ........................................................................................................................................... 153

6-10-4- جریان داده ها ............................................................................................................................................ 153

6-10-5- موضوعات دیگر در طراحی پایگاه داده ..................................................................................................... 154

6-11- زبان مدل سازی یکپارچه UML .................................................................................................................. 156

6-12- خلاصه ........................................................................................................................................................... 160

مروری بر اصطلاحات ................................................................................................................................................. 163

تمرین مهارت ............................................................................................................................................................. 165

تمرینات ...................................................................................................................................................................... 170

منابع ........................................................................................................................................................................... 173

ابزارها ......................................................................................................................................................................... 173

فصل هفتم: طراحی پایگاه داده رابطه ای .......................................................................................... 175

7-1- ویژگی های طراحی های رابطه ای خوب ......................................................................................................... 176

7-1-1- طراحی جایگزین : الگوهای بزرگتر .............................................................................................................. 177

7-1-2- طراحی جایگزین : الگوهای کوچکتر ........................................................................................................... 181

7-2- محدوده های غیر قابل تجزیه واولین شکل نرمال ............................................................................................... 185

7-3- تجزیه با استفاده از وابستگی های عملیاتی ....................................................................................................... 188

7-3-1- کلیدها و وابستگی های عملیاتی ................................................................................................................... 188

7-3-2- شکل نرمال Boyce-codd ...................................................................................................................... 192

7-3-3- BCNF و حفاظت وابستگی ..................................................................................................................... 193

7-3-4- سومین شکل نرمال .................................................................................................................................... 197

7-3-5- شکل های نرمال بیشتر ................................................................................................................................. 200

7-4- تئوری وابستگی عملیاتی .................................................................................................................................. 201

7-4-1- بستار مجموعه وابستگی های عملیاتی .......................................................................................................... 201

7-4-2- بستار گروه های صفات ............................................................................................................................. 205

7-4-3- پوشش استاندارد ....................................................................................................................................... 208

7-4-4- تجزیه بی نقص .......................................................................................................................................... 213

7-4-5- حفاظت وابستگی ........................................................................................................................................ 214

7-5- تجزیه با استفاده از وابستگی های عملیاتی ........................................................................................................ 217

7-5-1- تجزیه BCNF .......................................................................................................................................... 217

7-5-1-1- آزمون BCNF .................................................................................................................................... 218

......................................................................................................................... 220

7-5-2- تجزیه 3NF .............................................................................................................................................. 222

7-5-3- مقایسه BCNF و 3NF ............................................................................................................................. 225

7-6- تجزیه با استفاده از وابستگی های چند مقداری ................................................................................................. 226

7-6-1- وابستگی های چند مقداری ......................................................................................................................... 227

7-6-2- شکل نرمال چهارم ..................................................................................................................................... 230

7-6-3- تجزیه 4NF ............................................................................................................................................... 232

7-7- دیگر شکل های نرمال ..................................................................................................................................... 234

7-8- فرایند طراحی پایگاه داده ............................................................................................................................... 234

7-8-1- مدل E-R و نرمال سازی ............................................................................................................................ 235

7-8-2- نام گذاری صفات و رابطه ها ........................................................................................................................ 237

7-8-3- از نرمال درآوردن برای کارایی ................................................................................................................... 239

7-8-4- دیگر مباحث طراحی ................................................................................................................................... 240

7-9- مدل سازی داده های موقتی ............................................................................................................................. 241

7-10- خلاصه .......................................................................................................................................................... 245

مرور اصطلاحات ........................................................................................................................................................ 246

تمرین مهارت ............................................................................................................................................................ 248

تمرین ...................................................................................................................................................................... 250

واژه نامه ..................................................................................................................................................................... 254

فهرست شکل ها

عنوان صفحه

شکل 5-1- اسامی همه مشتریانی که یک وام در شاخه perryridge دارند ................................................................... 5

شکل 5-2- جدول های ساختمان برای مثال بانک ........................................................................................................ 22

شکل 5-3- نمونه پرس و جو در Microsoft access QBE .................................................................................... 32

شکل 5-4- یک پرس و جو تراکمی در Microsoft access QBE ....................................................................... 34

شکل 5-5- نمونه حساب رابطه ای .............................................................................................................................. 37

شکل 5-6- رابطه V₁ .................................................................................................................................................. 37

شکل 5-7- برنامه دیتالوگ سود حساب های perryridge ......................................................................................... 41

شکل 5-8- برنامه دیتالوگ بازگشتی .......................................................................................................................... 42

شکل 5-9- نتیجه Infer(R,I) .................................................................................................................................... 44

شکل 5-10- لایه بندی رابطه ها .................................................................................................................................. 46

شکل 5-11- رویه datalog-fixpoint ..................................................................................................................... 52

شکل 5- 12- رابطه manager ................................................................................................................................. 53

شکل 5-13- کارکنان جونز در تکرار رویه datalog- fixpoint ............................................................................... 54

شکل 5-14- پایگاه داده کارکنان .............................................................................................................................. 62

شکل 5-15- پایگاه داده بیمه ..................................................................................................................................... 65

شکل 6-1- گروه موجودیت loan,customer ....................................................................................................... 78

شکل 6-2- گروه رابطه borrower ........................................................................................................................... 79

شکل 6-3- Accwss-date به عنوان صفتی برای گروه رابطه depositor .............................................................. 81

شکل 6-4- صفات مرکب نام مشتری وآدرس مشتری ................................................................................................. 83

شکل 6-5- نقشه کاردینالیتی ها a,b ............................................................................................................................ 87

شکل 6-6- نقشه کاردینالیتی ها a,b ............................................................................................................................ 89

شکل 6-7- نمودار E-R مربوط به loans,customers ........................................................................................... 94

شکل 6-8- روابط c,b,a ........................................................................................................................................... 96

شکل 6-9- نمودار E-R با یک صفت که به یک رابطه اضافه شده است ..................................................................... 96

شکل 6-10- نمودار E-R با صفات مرکب ، چند مقداری و مشتق شده .................................................................... 97

شکل 6-11- نمودار E-R با نمایشگر نقش .......................................................................................................... 99

شکل 6-12- نمودار E-R با یک رابطه سه گانه ........................................................................................................ 99

شکل 6-13- مشارکت کلی یک گروه موجودیت در یک گروه رابطه ...................................................................... 100

شکل 6-14- محدودیت های کاردینالیتی روی گروه رابطه ....................................................................................... 101

شکل 6-15- جانشین هائی برای telephone,employee ..................................................................................... 103

شکل 6-16- loan به عنوان یک گروه رابطه .................................................................................................... 105

شکل 6-17- رابطه سه گانه در مقابل سه رابطه دوگانه .............................................................................................. 108

شکل 6-18- access-date به عنوان صفتی برای گروه موجودیت account ...................................................... 110

شکل 6-19- نمودار E-R برای یک گروه موجودیت ضعیف ............................................................................... 114

شکل 6-20- عمومی سازی و ویژه کاری ............................................................................................................... 117

شکل 6-21- نمودار E-R با رابطه های زائد ......................................................................................................... 126

شکل 6-22- نمودار E-R ترکیب ....................................................................................................................... 127

شکل 6-23- نمادهای مورد استفاده در E-R ......................................................................................................... 129

شکل 6-24- نمادهای جایگزین در E-R ........................................................................................................ 130

شکل 6-25- نمودار E-R برای پروژه بانکداری .................................................................................................. 137

شکل 6-26- چند گانه loan ................................................................................................................................. 138

شکل 6-27- نمودار E-R ...................................................................................................................................... 143

شکل 6-28- نمادهای مورد استفاده در طراحی نمودار کلاس UML .................................................................... 159

شکل 6-29- نمودار E-R برای تمرین مهارت 6-9و6-22 .................................................................................. 168

شکل 6-30- نمودار E-R برای تمرین 6-11 ................................................................................................... 169

شکل 6-31- نمودار E-R برای تمرین 6-21 ................................................................................................... 171

شکل 7-1- الگوهای بانکداری برای بخش 6-9-7 ........................................................................................... 177

شکل 7-2- بخشی از چند گانه ها در رابطه های bor- loan,borrower,loan ............................................. 179

شکل 7-3- چندگانه ها در رابطه های loan-amt-br,loan-branch,loan .................................................. 181

شکل 7-4- از بین رفتن اطلاعات در یک تجزیه نامناسب ................................................................................. 185

شکل 7-5- رابطه نمونه r ................................................................................................................................. 191

شکل 7-6- گروه های رابطه Works-in,cust-banker ................................................................................ 195

شکل 7-7- گروه رابطه cust-banker-branch ........................................................................................... 196

شکل 7-8- یک روال برای محاسبه F⁺ .......................................................................................................... 205

شکل 7-9- یک الگوریتم برای محاسبه X⁺ ، بستار X تحت F ........................................................................... 207

شکل 7-10- محاسبه پوشش استاندارد ............................................................................................................ 211

شکل 7-11- آزمون برای حفاظت وابستگی ................................................................................................... 215

شکل 7-12- الگوریتم تجزیه BCNF ............................................................................................................ 219

شکل 7-13- حفاظت وابستگی ، تجزیه بی نقص در 3NF ............................................................................ 222

شکل 7-14- نمایش جدولی از XàB ...................................................................................................... 228

شکل 7-15- یک مثال از افزونگی در رابطه روی الگوی BCNF .................................................................. 229

شکل 7-16- یک رابطه R₂ غیر مجاز ............................................................................................................ 229

شکل 7-17- الگوریتم تجزیه 4NF .............................................................................................................. 231

شکل 7-18- رابطه تمرین 7-2 ................................................................................................................. 248

شکل 7-19- الگوریتمی برای محاسبه X⁺ ....................................................................................................... 252

7-5-1-2- الگوریتم تجزیه BCNF ...........................

ما در فصل2 جبر رابطه ای را ارائه کردیم که اشکال پایه ای در بسیاری از مواردی هستند که در زبان SQL Query استفاده می شوند . جزئیات بیشتر در فصل های 3 و 4 ارائه شد . در این فصل ابتدا دوزبانی را که بیشتر رسمیت دارند را مطالعه می کنیم یکی حساب رابطه ای چندتایی و یکی حساب رابطه ای حوزه . که این دو زبان رسمی زبان هایی هستند بر پایة پرس و جو[1] و مبتنی بر منطق ریاضی ، و این دو زبان رسمی شکل پایه ای برای دو یا بیشتر زبان های دوستانه هستند ، که بعداً در این فصل QBE[2] و Datalog را مطالعه می کنیم .

بر خلاف SQL و QBE یک زبان گرافیکی به گونه ای به شکل جداول می باشد .QBE و جایگزینش خیلی مورد استفاده قرار می گیرند در سیستمهای پایگاه داده در کامپیوترهای شخصی . Datalog یک نمونه ترکیبی بعد از زبان Prolog دارد . هر چند در حال حاضر به صورت تجاری از این دست آورد استفاده نمی شود . Datalog بیشتر در جستجوی سیستم های پایگاه داده ای مورد استفاده قرار می گیرد .

برای QBE و Datalog ، ما ساختارها و مفاهیم بنیادی را سریع تر از یک کتاب راهنمای جامع کاربران برای این زبان ها به دست می آوریم ، عقیده بر این است که شخص یکی از این زبان ها را انتخاب کند ، ممکن است در جزئیات متفاوت باشند یا ممکن است تنها یک زیر مجموعه از تمام زبان ها را تأیید کند .

5-1 حساب رابطه ای چندتایی

وقتی که ما یک عبارت جبری رابطه ای را می نویسم . ما یک روالی را که جوابهایی برای پرس و جو به وجود می آورند را مهیا می کنیم . در مقام مقایسه حساب رابطه ای چندتایی یک زبان تحقیقی غیر رویه ای اطلاعات خوبی را بدون دادن یک روال ویژه برای به دست آوردن آن اطلاعات ارائه می دهد . یک پرس و جو در حساب رابطه ای چندتایی که مثل { t | p (t ) } بیان می شود منظور این است که آن یک مجموعه ای از همه متغییرهائی چون t می باشد به گونه ای که p ( t ) مبتنی بر آن درست باشد به ازاء همه t ها. در دنباله مطالبمان ، ما از t [A] برای مشخص کردن مقدار متغییر t بر روی صفت A استفاده می کنیم و ما از r t برای مشخص کردن یک متغییر t که در رابطه با r می باشد ، استفاده می نماییم.

قبل از این که ما یک تعریف رسمی از حساب رابطه ای چندتایی ارائه بدهیم ، ما به بعضی از پرس و جو ها که در جملات جبری رابطه ای در بخش 2-2 نوشته ایم برمی گردیم . به یاد آورید که پرس و جو ها از الگوی های زیر پیروی می کنند :

شاخه ( نام شاخه ـ شهر شاخه ـ موجودی ( دارائی ) )

خریدار ـ مشتری ( نام مشتری و جبر مشتری ، شهر مشتری )

وام ( شماره وام ـ نام شاخه ـ مقدار )

وام گیرنده ( نام مشتری ـ شماره وام )

حساب ( شماره حساب ـ نام شاخه ـ موجودی )

سپرده گذار ( نام مشتری ـ شماره حساب )

5- 1- 1- طرح مثال

پیدا کردن نام شاخه ، شماره وام ، مبلغ وام برای وام های بیشتر از 1200 دلار :

{loam ^ t [ amount ]> 1200 t½ t }

فرض کنید که ما خواسته باشیم فقط صفت ( شماره وام ) ، بیشتر از همه صفات رابطه وام باشد . برای نوشتن این پرس و جو در حساب رابطه ای چندتایی ما به نوشتن یک توضیح نیاز داریم . برای یک رابطه در این طرح یا مدل ( شماره وام ) ما به چندتایی ها بر روی شماره وام نیاز داریم هم چنانکه یک چندتایی در وام به وسیله یک صفت, مقداری بزرگتر از 1200 وجود دارد . برای بیان این تقاضا ما به ساختار وجود داشتن از مطلق ریاضی نیاز داریم . نکته :

r ( Q (t) ) t

وجود یک متغییر t متعلق به r به گونه ای که Q (t) درست باشد . از این نکات استفاده می کنیم ، تا بتوانیم پرس و جو را بنویسیم همچون ، پیدا کردن شماره وام برای هر یک از وام ها به گونه ای که مبلغ بزرگ تر از 1200 دلار باشد . همچون :

loan ( t [ loan - number] = S [loan-number]^S [amount]>1200}S t½}

در انگلیسی ، ما می خوانیم جمله یا توضیحی قبلی به عنوان ” دسته ای از همه متغیرهایی همچون t که وجود دارد یک متغیر ( چندتایی) S متعلق به loan برای هر مقدار t و s متعلق به loan-number که مساوی هستند و مقدار S برای صفت amount بزرگ تر از 1200 دلار هستند .

متغیر چندتایی t تنها در نشانه های loan-number تعریف می شود از این که تنها صفتی از بودن یک حالت ویژه برای t وجود دارد . نتیجه این است که یک ارتباط روی loan – number وجود دارد .

نتیجه پرس و جو پیدا کردن اسامی همه مشتری ها که یک وام از شاخة Perryridge دارند . این پرس و جو اندکی پیچیده تر از تحقیقات قبلی است. بعد از درگیر کردن دو رابطه : قرض کننده و وام . ما باید همه درخواست ها را مشاهده کنیم . بنابراین ، ما دو شرط « وجود داشتن » در عبارت حساب رابطه ای چندتایی داریم که به وسیله ( ^ ) and متصل شده اند . ما پرس و جو را به شکل زیر می نویسیم:

{ t½ s borrower ( t [ customer-name] = S [Customer-name]^ u loan
( u [ loan – number] = S [ loan- number] ^ u [ branch –name ] = “ perryridge” )) }

customer – name

Adams Hayes

شکل 5-1 اسامی همه مشتری هایی که یک وام در شاخه Perryridge دارند .

در انگلیسی ، این مطلب به صورت همه متغیرهائی ( customer – name ) برای هر مشتری که یک وام از یک شاخه Perryridge دارد ، بیان می گردد . متغیرهای چندتایی u این اطمینان را می دهند که مشتری یک قرض کنند از شاخه Perryridge می باشد . متغیرهای چندتایی S در شماره وام یکسان مثل S محصور شده اند . شکل 1- 5 نتیجه این پرس و جو را نشان می دهد .

برای یافتن همه مشتری هایی که یک وام دارند و یک موجودی و یا هر دو را در بانک دارند ، ما عملوند مشترک در روابط جبری به کار می بریم . در جبر رابطه ای چندتایی ما به دو شرط « وجود داشتن » نیاز داریم که به وسیله ( v ) یا متصل می شوند :

{ t½ s borrower ( t [ customer-name] = S [Customer-name] ) v u depositor ( t [ customer – name] = u [ customer- name] ) }

این توضیح جمله همه اسامی مشتری های چندتایی را برای نگهداری آن به یکی از روشهای زیر را می دهد .

l نام مشتری در بعضی چندتایی ها از رابطه قرض کننده نوشته می شود همچون قرض کننده از بانک

l نام مشتری در بعضی چندتایی ها از رابطه امانت گذار نوشته می شود همچون امانت گذار در بانک .

اگر بعضی از مشتری ها هر دو ، یک وام و یک حساب در بانک را داشته باشند، مشتری فقط یکبار در نتیجه ظاهر می شود . چرا که در تعریف ریاضی در یک مجموعه اجازه داده نمی شود که از عناصر نسخه برداری شود .

نتیجه این تحقیق در شکل 11-2 نشان داده شده است.

اکنون اگر تنها آن مشتری هایی را که هر دو یک حساب و یک وام بانک دارند را خواسته باشیم، نیاز داریم به اینکه ( v ) or را به ( ^ ) and در جمله قبلی تغییر دهیم.

{ t½ S borrower ( t [ customer-name] = S [Customer-name] ) ^ u depositor ( t [ customer – name] = u [ customer- name] ) }

نتیجه این پرس و جو در شکل 19- 2 نشان داده شده ا ست .

حال پرس و جوی یافتن همه مشتری هایی که یک حساب بانکی دارند اما یک وام از بانک ندارند را ملاحظه کنید. بیان ریاضی رابطه ای برای این پرس و جو مانند بیان هایی که ما ارائه کردیم می باشد . بجز آنهایی که ما از علامت ~)) not استفاده کردیم .

{ t½ u depositor ( t [ customer-name] = u [Customer-name] ) ^ ~S borrower ( t [ customer – name] = S [ customer- name] ) }

این بیان ریاضی رابطه ای چندتایی از depositor ( ...)u استفاده می کند . با شرط آن که نیاز است به این که مشتری یک حساب در بانک داشته باشد و از
borrower ( ...) S ~ استفاده می شود با شرط این که آن مشتری ها که پیدا می شوند متعلق به بعضی از متغیر رابطه ای وام گیرنده ای که یک وام از بانک دارند ,نباشد .

نتایج این پرس و جو در شکل 12 – 2 نشان داده شده است .

در پرس و جو ما بایستی از جهت نشان دادن نتیجه و دلالت استفاده کنیم . شکلQ p به معنی p " آن گاه "Q است . که آن « اگر p درست باشد آن گاه Q باید درست باشد » می باشد . نکته این که Q P منطقاً مساوی است با ~ PVQ . استفاده از استدلال سریع تر از not و or اغلب به یک بیان بیشتر یک پرس و جو در انگلیسی اشاره می کند .

پرس و جویی را که ما در بخش 3-3-2 استفاده کرده ایم ملاحظه نمائید. برای توضیح بخش عمل : « یافتن همه مشتری هائی که یک حساب در همه شاخه های که معلوم شده در Brooklyn دارند . نوشتن این پرس و جو در حساب رابطه ای چندتایی ، « برای همه » ساختار مشخص شده ای را به وسیله ایجاد می کنیم .

توجه :

به معنی ” Q برای همه متغیرهای t در رابطه با r درست است “ و ما توضیحی برای پرس و جو خود به شکل زیر می نویسیم:

{ t½r customer ( r [ customer-name] = t [Customer-name] ) ^ ( branch ( u [branch – city ] = “ Brooklyn” DEPOSITOR ( t [ customer-name] = S [ customer – name ] ^ w account ( w [ account – number ] = S [ account – number ] ^ w [ branch –name ] = u [ branch – name] )))) }

در انگلیسی ، ما این جمله را این گونه بیان می کنیم « همه مشتری هایی که در آن
( customer- name ) متغیر t هست . برای همه متغیرهای u در رابطة branch و اگر مقدار u به عنوان یک صفت branch-city مساوی Brooklyn باشد آن گاه مشتری یک حساب در شاخه ای که نام آن ظاهر شده است در صفت name - branch متغیر u داشته باشد» .

نکته ظریفی در بالای این پرس و جو وجود دارد این است که : اگر هیچ شعبه ای درBrooklyn وجود نداشته باشد و نام همه مشتری هائی که در این شرط برقرارند وجود نداشته باشد .

خط اول توضیح پرس و جو در این حالت بحرانی است ـ بدون شرط

customer ( r [customer-name ] = t [ customer-name ] )

اگر هیچ شاخه ای در Brooklyn وجود نداشته باشد ، هیچ مقدار t ( به انضمام مقادیری که نام مشتری در رابطه customer نیستند . ) محدود شود .

5-1-2 تعاریف رسمی

حالا ما برای بیان تعاریف رسمی آماده هستیم. یک منطق رابطه ای چندتایی به شکل زیر بیان می شود:

{ t½ p ( t ) }

هرکجا که p به عنوان فرمول ظاهر شود ، ممکن است چندین متغیر چندتایی در یک فرمول ظاهر شود . یک متغیر چندتایی به یک متغیر آزاد که بیان می شود به وسیله یک یا گفته می شود . بنابراین ، در

{ t loan ^ customer ( t [ branch-name] = S [branch-name] )

t یک متغیر آزاد می باشد . متغیر چندتایی S گفته می شود که یک متغیر ناگزیر می باشد . یک شکل منطق رابطه ای چندتایی از عناصر خارجی ساخته می شود. یک عنصر به یکی از اشکال زیر می باشد :

l rS ، هنگامی که S یک متغیر چندتایی هست و r یک رابطه می باشد . ( ما از عمل به شکل استفاده نمی کنیم)

l s[n](-)u[y] و هنگامی که S و U متغیرهای چندتایی هستند و x یک صفت برای زمانی که S تعریف شده است می باشد و y یک صفت برای زمانی u تعریف شده است می باشد و (- ) یک عملگر مقایسه ای است . () ، نیازمند هستیم که متغیرهای x و y بتوانند عضو مجموعه ای باشند که بتوانند به وسیله عملگر (- ) مقایسه شوند .

l S [x](-)c ، هنگامی که S یک متغیر چندتایی هست ، x یک صفت که توسط s تعریف می شود ، است . (- ) یک عملگر مقایسه ای است و c یک مقدار ثابت در مکانی.

l ( حوزه ) از صفت x است . ما فرمولی از عناصری که از قوانین زیر پیروی می کنند
می سازیم :

l یک اتم ، یک فرمول است .

l اگر P₁ یک فرمول باشد ، آنگاه ~P₁ و ( P₁ ) فرمول هستند .

l اگر P₁ و P₂ فرمول باشند ، آنگاه P₁VP₂ و P₁^P₂ و P₂ P₁ فرمول هستند.

l اگر P₁ (S) یک فرمول باشد متشکل از یک متغیر چندتایی آزاد s و r یک رابطه هست ، آنگاه

r( P₁ (S) ( P₁ (S) ) and

نیز فرمول هستند .

همچنین ما می توانیم برای روابط جبری عبارت های معادلی را که در ظاهر هم مشکل نباشند را بنویسیم .

در جبر رابطه ای چندتایی ، این عبارت ها شامل 3 قانون زیر می باشند :

1. P₁P₂ is equivalent to ~ ( ~ ( P₁ ) ~ ( P₂ )) .

2. ( P₁ (t)) is equivalent to ~ tr ( ~ P₁ (t) )

3. P₁P₂ is equivalent to ~ ( P₁ ) P₂.

5-1-3 اطمینان در بیان

یک نتیجه پایانی برای آدرس داده وجود دارد . یک بیان جبر رابطه ای چندتایی ممکن یک رابط نامحدود عمومی می باشد . که ما این عبارت را این گونه می نویسیم :

loan ) } { t | ~ ( t

به طور نامحدود چندتایی های زیادی که در loan نیستند ، وجود دارد . بیشتر این چندتایی ها شامل مقادیری هستند که هرگز در پایگاه داده ظاهر نمی شوند .

بدون شک ما امید چندانی برای پذیرش این چنین عبارت هائی را نداریم . برای یاری ما محدودیت در جبر رابطه ای چندتایی را تعریف می کنند. ما حیطه یک فرمول رابطه ای چندتایی را معرفی می کنیم و p به طور حسی ، مکان p به شکل دامنه ( p ) مشخص می شود ، همه مقادیر ارجاع شده به وسیلة p در آن هست. آنها شامل مقادیر نام برده شده در خود p هستند به همان خوبی مقادیری که در یک رابطة چندتایی ذکر شده در p ظاهر می شوند . بدین ترتیب ، موقعیت p هست همه مقادیری که صریحاً در p ظاهر می شوند یا این که در یک یا بیشتر روابطی که اسامی آنها را به وجود می آورند در p ، پدیدار می شوند . برای مثال دامنه (t [ amount] > 1200 loan t ) مجموعه ای شامل 1200 مجموعه همه مقادیر ظاهر شده در loan است .

همچنین دامنه loan ) ) ( ~ ( t مجموعه از همه مقادیر پدید آمده در loan است زمانی که رابطه loan در عبارت نامبرده شده .

ما گفتیم که یک عبارت { t | p ( t ) } درست است اگر همه مقادیر که به وجود می آیند در مجموعه مقادیر از دامنه ( P ) عبارت loan ) } { t | ~ ( t مجموعه از همه مقادیری که در loan وجود دارند بنابراین ، این امکان وجود دارد که داشته باشد یک چندتایی t که در loan نیست و شامل مقادیری که وجود ندارد در loan . به طور مثال عبارت هایی از حساب رابطه ای چندتایی که ما در این قسمت می نویسیم درست هستند .

5-1-4 زبانهای توانای پرمعنی

حساب رابطه ای چندتایی محصور شده با عبارتهای درست که در روابط قوی جبری پایه برابر هستند با (عملگرهای p , u , - , x , اما بدون عملگرهای رابطه ای عمومی چون g و عملگرهای رابطه ای خارجی) بنابراین برای هر جمله جبری رابطه ای فقط عملگر پایه به کار می رود و یک جمله ( توضیح ) معادل در حساب رابطه ای چندتایی است و برای هر جمله رابطه ای چندتایی یک حساب رابطه ای چندتایی برابر آن وجود دارد .

ما اینجا این تحقیق را اثبات نخواهیم کرد ؛ نکات مربوط به فهرست کتب شامل مراجعه به دلایل می باشد . برخی قسمتهای این دلایل شامل تمرین ها است .

ما توجه خواهیم کرد به حساب رابطه ای چندتایی که هیچ معادلی برای عملگرهای به هم پیوسته ندارند و آن می تواند به پشتیانی تراکم بسط داده شود و ادامه دادن حساب رابطه ای چندتایی به طور دستی بیان علم حساب که درست می باشد.

5-2 قلمرو حساب رابطه ای

شکل دوم حساب رابطه ای، که قلمرو حساب رابطه ای نامیده می شود، از متغیرهای سد[3] استفاده می کند. این متغیرها به جای استفاده از مقادیر یا چندگانه کلی از متغیرهای برگرفته از مقادیری استفاده می کند که برخواسته از قلمرو خصوصیات اند. البته قلمرو حساب رابطه ای به طور دقیقی به حساب رابطه ای چندگانه مربوط می شود.

قلمرو حساب رابطه ای به عنوان تئوری بنیادین بسیاری از مفاهیم مورد استفاده زبان، بکار میرود. درست شبیه جبر رابطه ای که به عنوان پایه ای برای زبان SQL بکار میرود.

5-2-1 تعریف رسمی

یک عبارت در قلمرو حساب رابطه ای به صورت:

{ < x₁ ,x₂ ,….,x_n > | P(x₁ ,x₂ ,….,x_n) }

است بطوریکه x₁ ,x₂ ,….,x_n متغیرهای قلمرو را بیان می کند. P بیانگر یک فرمول ترکیب اتم هاست، همانگونه که در حساب رابطه ای چند تایی بود. اتم در قلمرو حساب رابطه ای یکی از شکلهای زیر را داراست:

• · r < x₁ ,x₂ ,….,x_n > بطوریکه r رابطه ای است روی n خصوصیت و x₁ ,x₂ ,….,x_n متغیرها یا ثابت های قلمرو هستند.
• · ، بطوریکه xوy متغیرهای قلمرو و عملگرهای مقایسه ای (> ، ≥ ، = ، ≠ ، < ، ≤) است. لازم است که خصوصیاتx و y دارای قلمروهایی باشند که بوسیله مقایسه شده اند.
• · ، بطوریکه x یک متغیر قلمرو، یک عملگر مقایسه ای، و c یک ثابت در قلمروی خصوصیات برای هر x متعلق به قلمرو است.

ما با استفاده از قواعد زیر یک فرمول از اتم ها ایجاد کرده ایم:

• · هر اتم یک فرمول است.
• · اگر P₁ یک فرمول است، بنابراین ⌐P₁ و (P₁) هم فرمول هستند.
• · اگر P₁ و P₂ فرمول هستند، بنابراین نیز فرمول هستند.
• · اگر P₁(X) یک فرمول از x است، بطوریکه x یک متغیر قلمروی مستقل است، آنگاه

نیز یک فرمول است.

برای نمایش خلاصه تر می نویسیم:

5-2-2 پرس وجوهای نمونه

اکنون پرس وجوهایی از قلمرو چندگانه رابطه ای برای نمونه هایی که قبلاً توضیح دادیم ارائه می دهیم. به شباهت این عبارات و عبارات مشابه قلمرو چندگانه رابطه ای توجه نمایید.

• · یافتن شماره وام، نام شعبه و مبلغ وامهای بیشتر از 1200دلار:

{ < l , b , a > | < l , b , a > loan a > 1200 }

• · یافتن همه شماره وامها برای وامهای با مبلغ بیشتر از 1200دلار:

{ < l > | b , a ( < l , b , a > loan a > 1200 }

اگرچه پرس و جوی دوم مانند آن مورد که برای چندگانه حساب رابطه ای نوشتیم، به نظر میرسد، اما با هم یک تفاوت مهم دارند. درحساب چندگانه، وقتی می نوشتیم برای بعضی متغیر چندگانه s، بلافاصله آنرا با نوشتن یک به یک رابطه متصل می کردیم. اگر چه، وقتی در قلمرو حساب می نویسیم ، b به یک چندگانه اشاره نمی کند، اما بلکه به مقدار یک قلمرو اشاره دارد. بنابراین، دامنه متغیر b تا وقتی که زیر فرمول loan< l , b , a > متغیر b را به نامهای شعبه که در رابطه دیده می شوند محدود می کند، نا محدود است.

اکنون ما چندین مثال از پرس و جوها در قلمرو حساب رابطه ای بیان می کنیم.

• · یافتن نام همه مشتریانی که از شعبه Perryridge وام دریافت کرده اند و یافتن مبلغ آن:

{ < c,a > | l ( borrower

b( < l,b,a>loan b="Perryridge"))}

• · یافتن نام همه مشتریانی که یک وام،یک شماره حساب، یا هر دو را در شعبه Perryridge داشته اند:

{ < c > | l ( < c,l > borrower b , a ( loan b = "Perryridge")) a( depositor b,n ( account b="Perryridge"))}

• · نام همه مشتریانی که در تمام شعبات واقع در بروکلین شماره حساب دارند:

{ < c > | s,t ( < c,s,t > customer x,y,z ( branch y = "Brooklyn" a,b ( account depositor))}

در زبان انگلیسی این عبارت را اینگونه تفسیر می کنیم: "مجموعه همه متغییرهای c (نام مشتری) که در آن برای همه متغییرهای های x,y,z (نام شعبه، شهر شعبه، موجودی) اگر شهر شعبه بروکلین است، آنگاه این عبارات همواره درست است:

• oدر رابطه account با شماره حساب a، نام شعبه x وجود دارد.
• oدر رابطه depositor یک چندگانه با نام مشتری c وشماره حساب a وجود دارد.

5-2-3 ایمنی عبارات

یادآور می شویم که در حساب چندگانه رابطه ای (بخش 5-1)، می توان عباراتی نوشت که بی نهایت رابطه تولید کند. این موضوع ما را به تعریف ایمنی برای عبارات حساب چندگانه رابطه ای سوق می دهد. برای قلمروی حساب رابطه ای نیز وضعیت مشابهی رخ می دهد. یک عبارت مانند

{ < l,b,a > | ⌐ ( < l,b,a > loan)}

نا ایمن است. زیرا مقادیری از نتیجه را که در قلمروی عبارت نیستند را پذیرش می کند.

در قلمروی حسابهای رابطه ای نیز باید نگران شکل فرمول در شرطهای "There exist" و "For all" باشیم. به عبارت

{ < x > |y (< x,y > r) z (⌐ ( < x,z > r ) P(x,z))}

وقتی p شامل بعضی فرمولهای شامل x یا z است توجه نمایید. می توانیم قسمت اول فرمول را r) y (< x,y > فقط با مقدار داخل r مورد ارزیابی قرار دهیم. اگرچه برای تست کردن قسمت دوم فرمول،

P(x,z)) r ) z(⌐ ( < x,z >

باید مقادیری برای z که در r ظاهر نشده اند را مورد توجه قرار دهیم. بنابراین در حالت کلی تست کردن قسمت دوم فرمول بدون ملاحظه کردن تعداد نامتناهی از مقادیر بالقوه برای z ، امکانپذیر نیست. در عوض برای ممنوع کردن عبارات مانند آنچه قبلاً ذکر شد، محدودیتهایی را اضافه کردیم.

در حساب چندگانه رابطه ای، هر متغیر وجودی تعیین شده را به یک دامنه مشخص رابطه محدود می کنیم. چون در قلمروی حساب اینکار را نمی کنیم، برای کار با موارد مشابه مثالمان، قواعدی را به تعریف ایمنی اضافه می کنیم. عبارت:

{ < x₁ ,x₂ ,….,x_n > | P(x₁ ,x₂ ,….,x_n) }

را ایمن گوییم هرگاه همه موارد زیر را داشته باشیم:

1. همه مقادیری که در چندگانه عبارت ظاهر می شوند مقادیری از [4]dam(p) هستند.
2. برای هر زیر فرمول "there exist" از شکل x (P₁(x))، زیر فرمول درست است اگر و تنها اگر یک مقدار x در dam(P₁) وجود داشته باشد که به ازای آن P₁(x) درست است.
3. برای هر زیر فرمول ّ"For all" از شکل (P₁(x)) x، زیر فرمول درست است اگر و تنها اگر برای هر مقدار x از dam(P₁) P₁(x) درست باشد..

هدف از قواعد اضافی این است که مطمئن شویم که می توانیم "There exist" و "For all" را تست کنیم بدون آنکه مجبور باشیم بینهایت حالت ممکن را تست کنیم. به قاعده دوم در تعریف ایمنی توجه کنید. برای آنکه x (P₁(x)) برقرار باشد، نیاز به این داریم که فقط یک x پیدا کنیم که P₁(x) برقرار باشد. در حالت کلی، باید تعداد خیلی زیاد از مقادیر برای تست وجود داشته باشد. اگرچه اگر عبارت ایمن باشد، می توانیم توجه مان را به مقادیری از dam(P₁) محدود کنیم. این محدودیت چندگانه هایی که باید مورد توجه قرار دهیم را به تعداد محدودی کاهش می دهد.

این وضعیت برای زیرفرمول به شکل (P₁(x)) x ، به همین شکل است. برای اثبات درستی (P₁(x)) x، بایدکلاٌ، همه مقادیر ممکن را تست کنیم، بنابراین باید بسیاری از مقادیر را تا بی نهایت آزمایش کنیم. همانند قبل اگر بدانیم که عبارت ایمن است همین برای ما کافیست که P₁(x) را برای این مقادیر برگرفته از dam(P₁) تست کنیم. تمام قلمرو عبارتهای حساب رابطه ای که ما در پرس و جو های مثال این بخش آورده ایم؛ ایمن هستند.

ترسیم کاردینالیتیالگوریتم تجزیهالگوریتم