Lecture 11 ساختارهای ایندکس ثانوی، پردازش همزمان داده ها Secondary Index structures, Co-sequential processing (Sections 7.7-7.9, 8.1-8.2)
In the Name of God
File Structure
ساختارهای ایندکس ثانوی، پردازش همزمان داده ها
چگونه ایندکس های ثانوی جهت ایجاد مسیری ترکیبی استفاده میگردند؟
ترکیب چند ایندکس ثانوی چگونه انجام میشود؟
روشهای بهینه سازی ساختار ایندکس ثانوی کدامند؟
چگونه از لیست های معکوس در ساختار ایندکس استفاده میگردد؟
چگونه میتوان از ایندکس ها جهت دسته بندی اطلاعات استفاده نمود؟
انواع روشهای اتصال ایندکس ها به داده ها کدامند؟
منظوراز پردازش همزمان داده ها چیست؟
الگوریتم مقایسه یا ادغام داده ها چگونه است؟
File Structure
ساختارهای ایندکس ثانوی (Secondary Index structures)
چگونه ایندکس های ثانوی جهت ایجاد مسیری ترکیبی استفاده میگردند؟
ترکیب چند ایندکس ثانوی چگونه انجام میشود؟ (combination)
مثال :
فایل اطلاعات مربوط به آهنگ ها در نظر میگیریم.
می خواهیم تمام آهنگ های BEETHOVEN با تیتر symphony No. 9 را پیدا کنیم.
جدول زیر با ترکیب دو ایندکس composer و title این نتیجه را به ما خواهد داد.
با استفاده از لیست نهایی (mached list) و با کمک ایندکس اصلی رکوردها را میخوانیم.
File Structure
ساختارهای ایندکس ثانوی
چه اشکالاتی در ساختار اولیه ایندکس ثانوی وجود دارد؟
برای هر کلید جدید (حتی با مقدار تکراری) بایستی ایندکس دوباره مرتب شود.
مقادیر تکراری کلید ثانوی فضایی را اشغال می کنند که می توانستیم صرفه جویی نماییم.
مثال:
File Structure
ساختارهای ایندکس ثانوی
چه اشکالاتی در ساختار اولیه ایندکس ثانوی وجود دارد؟
روشهای بهینه سازی ساختار ایندکس ثانوی کدامند؟
راه حل اول: استفاده از یک ماتریس که برای آن چند ستون پیش بینی شده باشد.
مثال:
معایب این راه حل کدامند؟
تعداد ستون ها ممکن است کافی نباشد.
فضای اضافی رزرو شده به هدر میرود.
File Structure
ساختارهای ایندکس ثانوی
روشهای بهینه سازی ساختار ایندکس ثانوی کدامند؟
راه حل دوم : استفاده از لیست های معکوس ( inverted lists):
در ایندکس ثانوی فقط یک مکان برای هرمقدار کلید رزرو می شود.
از آنجا بکمک یک اشاره گر به لیست جداگانه ای از کلیدهای اصلی اشاره می شود.
مثال:
File Structure
ساختارهای ایندکس ثانوی
روشهای بهینه سازی ساختار ایندکس ثانوی کدامند؟
مزایا و معایب راه حل استفاده از لیست های معکوس کدامند؟
مزایا:
هنگام ایجاد کلید تکراری عمل مرتب سازی ایندکس لازم نمی باشد. (چرا؟)
هنگام حذف رکوردها کافیست از یک علامت مانند ” 1-” در محل اشاره گر استفاده شود.
مرتب سازی ایندکس سریعتر می باشد چون اندازه آن کوچکتر است. (چرا؟)
فضای کمتری برای مرتب سازی (حتی روی دیسک ) لازم می شود.
لیست معکوس نیازی به مرتب سازی ندارد و فضای آن براحتی قابل بازیابی می باشد. (چرا؟)
معایب:
پراکندگی کلیدها در لیست معکوس. (منظور؟)
(راه حل : استفاده از مکانیسم paging )
File Structure
ساختارهای ایندکس ثانوی
چگونه میتوان از ایندکس ها جهت دسته بندی اطلاعات استفاده نمود؟
یکی دیگر از موارد استفاده ایندکس ها دسته بندی افقی اطلاعات در فایل های بزرگ میباشد.
(Selective indexes)
مثال:
فایل اطلاعات مربوط به آهنگ ها در نظر میگیریم.
یک ایندکس می تواند فقط شامل اطلاعات مربوط به قبل از سال 1970 باشد
ایندکسی دیگر نیز شامل اطلاعات بعد از این تاریخ باشد.
File Structure
ساختارهای ایندکس ثانوی
انواع روشهای اتصال ایندکس ها به داده ها کدامند؟
اتصال ایندکس با محل فیزیکی رکورد (Byte Offset) را binding می گویند.
در مورد ایندکس اصلی عمل اتصال هنگام ایجاد کلید در ایندکس انجام می شود.
(Tight Binding )
در مورد ایندکس ثانوی عمل اتصال هنگام استفاده از کلید ایندکس انجام می شود.
(Postponing Binding )
File Structure
ساختارهای ایندکس ثانوی
مزایا و معایب روشهای اتصال ایندکس ها به داده ها کدامند؟
مزایای postponing binding
عملیات لازم هنگام ایجاد یا حذف رکورد ها ساده تر و سریعتر انجام می شوند. (چرا؟)
این روش مطمئن تر است زیرا تغییرات مهم فقط در یک محل اعمال می شوند. (کدام؟)
معایب postponing binding
دسترسی به فایل از طریق کلید ثانوی کندتر می شود. (چرا؟)
موارد استفاده postponing binding
فایل هایی که در آن ها اعمال ایجاد حذف یا به روز کردن دائما انجام می شود. (چرا؟)
موارد استفاده tight binding
فایل هایی که داده های آنها ثابت هستند یا زیاد تغییر نمی کنند. (چرا؟)
فایل هایی که سرعت خواندن آنها مهم است (فایل های روی CD-ROM). (چرا؟)
File Structure
پردازش همزمان داده ها Co-sequential Processing
منظوراز پردازش همزمان داده ها چیست؟
اجرای عملیات همزمان (مثلا خواندن) بطور سری روی دو لیست (یا فایل) مرتب شده.
(Co-sequential processing)
موارد استفاده پردازش همزمان داده ها کدامند؟
مقایسه اعضای دو لیست (یا فایل) (Matching)
ادغام اعضای دو لیست (یا فایل) (Merging)
مثال 1:
مقایسه حسابهای دو فایل accounts و transaction در یک سیستم بانکی
Accounts (account number, person name, account balance)
Transactions (account number, credit debit info)
File Structure
پردازش همزمان داده ها
موارد استفاده پردازش همزمان داده ها کدامند؟
مثال 2:
ادغام ((Merging لیست اسامی دانشجویان در دو کلاس:
List1 List2 Matched list Merged list
Adams Adams Adams Adams
Carter Bech Carter Bech
Chin Burns Davis Burns
Davis Carter Carter
Miller Davis Chin
Reston Peters Davis
Rosewald Miller
Schmit Peters
Willis Reston
Rosewald
Schmit
Willis
File Structure
پردازش همزمان داده ها
الگوریتم مقایسه یا ادغام داده ها چگونه است؟
item(1) = current item from list 1
item(2) = current item from list 2
if( item(1) < item(2) )
[output item(1) to output list] (توضیح؟)
Get next item from list(1)
if( item(1) > item(2) )
[output item(2) to output list] (توضیح؟)
Get next item from list(2)
if( item(1) = item(2) )
output the item to output list
Get next item from list(2) and list(1)
(صفحه 298 کتاب شکل 5-8)
File Structure
پردازش همزمان داده ها
موارد استفاده پردازش همزمان داده ها کدامند؟
مثال کاربردی:
در یک سیستم حسابداری بانکی دو فایل زیر را در نظر می گیریم:
: Master File شامل موجودی ماهانه حسابها.
: Transaction File شامل عملیات انجام شده در یک ماه.
بایستی برنامه ای بنویسیم که:
عملیات انجام شده روی هر حساب را در Master File منعکس نماید.
گزارشی از عملیات هر حساب را نیز ارائه دهد. (Report)
File Structure
پردازش همزمان داده ها
(صفحه 301 – شکل 8.6 )
: Master File شامل موجودی ماهانه حسابها.
File Structure
پردازش همزمان داده ها
(صفحه 302 – شکل 8.7)
: Transaction File شامل عملیات انجام شده در یک ماه.
File Structure
پردازش همزمان داده ها
101 Checking account #1
1271 04/02/97 Auto expense -78.70
1272 04/02/97 Rent -500.00
1273 04/04/97 Advertising -87.50
1274 04/02/97 Auto expense -31.83
Prev. bal: 5219.23 New bal : 4521.20
102 Checking account #2
670 04/02/97 Office expense -32.78
Prev. bal: 1321.20 New bal : 1288.42
505 Advertising expense
1273 04/04/97 Newspaper ad re: new product 87.50
Prev. bal: 25.00 New bal: 112.50
510 Auto expenses
1271 04/02/97 Tune-up and minor repair 78.70
1274 04/09/97 Oil change 31.83
Prev. bal: 501.12 New bal : 611.65
(صفحه 302 – شکل 8.8)
گزارشی از عملیات هر حساب. (Report)
File Structure
پردازش همزمان داده ها
مثال کاربردی (ادامه…):
بایستی برنامه ای بنویسیم که:
عملیات انجام شده روی هر حساب را در Master File منعکس نماید.
روش کارچگونه است؟
شماره حساب به عنوان کلید مشترک بین دو فایل انتخاب می شود.
Transaction File بایستی مرتب شود (بر حسب شماره حساب و سپس تاریخ) (چرا؟)
الگوریتم پردازش همزمان انجام می شود.
File Structure
پردازش همزمان داده ها
Item(1): always stores the current master record
Item(2): always stores the current transactions record
– Read first master record
– Print title line for first account
– Read first transactions record
While (there are more masters or there are more transactions) {
if item(1) < item(2) then {
Finish this master record:
– Print account balances, update master record
– Read next master record
– If read successful, then print title line for new account
}
(صفحه 307 – شکل 8.13)
الگوریتم پردازش همزمان چگونه است؟
File Structure
پردازش همزمان داده ها
if item(1) = item(2) {
Transaction matches master:
– Add transaction amount to the account balance for new month
– Print description of transaction
– Read next transaction record
}
if item(1) > item(2) {
Transaction with no master:
– Print error message
– Read next transaction record
}
}
(صفحه 307 – شکل 8.13)
الگوریتم پردازش همزمان چگونه است؟