Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ПОСЛІДОВНИЙ МЕТОД ДОСТУПУ ДО ФАЙЛІВ НА ЗОВНІШНІХ ЗАПАМ’ЯТОВУЮЧИХ ПРИСТРОЯХ.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Системи автоматизованого проектуваня
Інформація про роботу
Рік:
2002
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Організація баз даних і знань
Частина тексту файла (без зображень, графіків і формул):
МIНIСТЕРСТВО ОСВIТИ І НАУКИ УКРАЇНИ
Національний унiверситет "Львiвська полiтехнiка"
ПОСЛІДОВНИЙ МЕТОД ДОСТУПУ ДО ФАЙЛІВ НА ЗОВНІШНІХ ЗАПАМ’ЯТОВУЮЧИХ ПРИСТРОЯХ
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи N 1
з курсу "Організація баз даних і знань "
для студентiв базового напрямку 6.0804
"Комп’ютернi науки"
Затверджено на засiданнi кафедри Системи автоматизованого проектування"
Протокол N14 вiд 03.04.1997р.
Львiв 2002
ПОСЛІДОВНИЙ МЕТОД ДОСТУПУ ДО ФАЙЛІВ НА ЗОВНІШНІХ ЗАПАМ’ЯТОВУЮЧИХ ПРИСТРОЯХ: Методичні вказівки до лабораторної роботи N1 з курсу "Теорiя алгоритмiв i математичнi онови представлення знань" для студентiв базового напрямку "Комп’ютернi науки" / Укл. А.Б.Керницький, І.І.Мотика, Ю.В.Стех. - Львiв: НУЛП, 2002.-9с.
Укладачi: А.Б.Керницький, маг.техн.наук.
І.І.Мотика, канд.техн.наук,доц.,
Ю.В.Стех, канд.техн.наук, доц.
Вiдповiдальний за випуск С.П.Ткаченко, канд.техн.наук, доц.
Рецензенти: М.Б.Близнюк, канд.техн.наук, доц.
I.I.Чура, канд.техн.наук, доц.
1. МЕТА РОБОТИ
Розглянути органiзацiю i ведення файлiв послiдовного доступу; набути практичнi навички у програмуваннi алгоритмiв роботи з файлами послiдовного доступу.
2. ТЕОРЕТИЧНI ВIДОМОСТI
Будь-який обмiн даними передбачає присутнiсть джерела iнформацiї, каналу передачi та її приймача. У випадку обмiну даними мiж програмою i периферiйним пристроєм одним кiнцем каналу обмiну даними завжди є оперативна пам’ять ПЕОМ. Другий кiнець цього каналу у бiльшостi мов програмування визначений як файл.
Поняття файла достатньо широке. Це може бути комунiкацiйний порт, пристрiй друку. У данiй роботi розглядається файл даних.
Одним iз головних чинникiв, що впливає на продуктивнiсть програм, якi взаємодiють iз базою даних, є спосiб зберiгання i доступу до файлiв даних: послiдовний, iндексно-послiдовний, індексно-довiльний, прямий, хешування.
Усi методи розглядаються за двома критерiями:
1. Ефективнiсть доступу - величина, обернена середнiй кiлькостi фiзичних звертань, необхiдних для логiчного доступу, тобто запиту конкретного запису бази даних. Фiзичнi звертання забезпечують задоволення запиту. Наприклад, якщо для пошуку потрiбного запису система звертається до двох записiв, то ефективнiсть доступу дорiвнює 0,5.
2. Ефективнiсть зберiгання - величина, обернена середнiй кiлькостi байтiв поля вторинної пам’ятi, яка необхiдна для зберiгання одного байта вхiдних даних.
3
Крiм вхiдних даних, пам’ять займають таблицi, керуюча iнформацiя, вiльна пам’ять, яка резервується для розширень, i дiлянка, яка не використовується через фрагментацiю
2.1. ДОСТУП ДО ЗАПИСІВ
Записи у простому послiдовному файлi доступнi лише послiдовно один за одним. Наприклад, можна звернутися до n-го запису тiльки пiсля звертання до 1,2,...,n-1 записiв. Для того, щоб видалити запис з файла, необхiдно створити копiю файла, у якiй цей запис є вiдсутнiм; для того, щоб помiстити запис у файл, також необхiдно створити копiю файла, у яку цей новий запис входить. Щоб змiнити хоча б одне з полiв у записi, необхiдно створити копiю файла, який мiститиме модифiкований запис. При послiдовному методi доступу значення ключiв фiзичних записiв знаходяться у логiчнiй послiдовностi.
2.1.1. Ефективнiсть доступу. Нехай вибрано один фiзичний запис, i належить вибрати iнший з бiльшим значенням ключа. У найгiршому випадку для вибору потрiбного запису необхiдно переглянути всi записи бази даних, а у кращому достатньо вибрати наступний запис. Для того, щоб виявити необхiдний запис у послiдовному файлi, який складається з N записiв, необхiдно переглянути у середньому N/2 записiв. Це пояснюється так. Нехай здiйснюється достатньо багато випробовувань, пов’язаних iз пошуком у послiдовному файлi випадково вибраних значень ключа. Причому кожний пошук починається з першого запису файла. Тодi для виявлення шуканого запису потрiбно переглянути у середньому половину загальної кiлькостi записiв.
4
НАВЧАЛЬНЕ ВИДАННЯ
ПОСЛІДОВНИЙ МЕТОД ДОСТУПУ ДО ФАЙЛІВ НА ЗОВНІШНІХ ЗАПАМ'ЯТОВУЮЧИХ ПРИСТРОЯХ
Методичні вказівки до лабораторної роботи N1 з курсу "Теорiя алгоритмiв i математичнi онови представлення знань" для студентiв базового напрямку "Комп’ютернi науки"
Укладачi Керницький Андрій Богданович
Мотика Ігор Іванович
Стех Юрій Васильович
Редактор Черничевич О.
ІНДИВІДУАЛЬНЕ ЗАВДАННЯ
Додаток
1.Написати програму, яка реалiзує такi функцiї:
1.1. Друк бази даних.
1.2. Пошук запису за введеним ключем.
1.3. Видалення запису за введеним ключем.
1.4. Вставлення запису.
1.5. Модифiкацiя запису.
2.Написати програму групового оброблення файла даних, яка реалiзує наступнi функцiї:
2.1. Створення файла повiдомлень.
2.2. Друк бази даних.
2.3. Пошук запису за введеним ключем.
2.4. Видалення запису за введеним ключем.
2.5. Вставлення запису.
2.6. Модифiкацiя запису.
ЗМIСТ ЗВIТУ
1. Мета роботи.
2. Огляд послiдовного методу доступу.
3. Лабораторне завдання.
4. Результати виконання пунктiв завдання.
5. Аналiз помилок, допущених пiд час виконання роботи.
8
2.1.2. Ефективнiсть зберiгання. Ефективнiсть використання пам'ятi близька до 100%. Зберiгання фiзичних записiв у логiчнiй послiдовностi можна використовувати для прискорення доступу, якщо перед звертанням до власне записiв бази даних перевiряти значення ключiв.
2.1.3 Алгоритм вставляння запису
<зчитати номер запису, який потрiбно вставити><m>
<зчитати данi><str>
<вiдкрити два файли, файл А - для читання, файл B - для зберiгання модифiкованої iнформацiї>
i:=1
доки не кiнець файла А
якщо m<>i
тодi <зчитати з А, записати в B>
i:=i+1
iнакше <записати у В str>
якщо m>=i
тодi <записати в В str>
<закрити файли А, В>
<змiнити iм'я з В на А>
2.1.4. Алгоритм модифiкацiї записiв
<зчитати номер запису, який потрiбно модифiкувати><m>
<зчитати данi><str>
<вiдкрити два файли, файл А - для читання, файл B - для зберiгання модифiкованої iнформацiї>
i:=1
доки не кiнець файла А
якщо i=m
тодi <зчитати з А><sm>
5
<записати в B><str>
i:=i+1
iнакше <зчитати з А><sm>
<записати у В>< sm>
<закрити файли А, В>
<змiнити iм'я з В на А>
2.1.5. Алгоритм видалення запису
<зчитати номер запису, який потрiбно видалити><m>
<вiдкрити два файли, файл А - для читання, файл B - для зберiгання
модифiкованої iнформацiї>
i:=1
доки не кiнець файла А
якщо i=m
тодi <зчитати з А><sm>
<записати в B><sm>
2.2. ГРУПОВЕ ОБРОБЛЕННЯ ПОСЛІДОВНИХ ФАЙЛІВ
Якщо необхiдно органiзувати доступ до М записiв послiдовного файла, який складається з N записiв, то звичайно прагнуть не застосовувати методу лiнiйного пошуку. Адже тодi знадобиться застосовувати цей метод М разiв, починаючи кожного разу перегляд файла з першого запису. Всього потрiбно проаналiзувати MN/2 записiв; очевидно, що при великому N на це буде витрачено значний час.
Існує ефективнiший метод перегляду файла: лише один раз. Для того, щоб використати цей метод, необхiдно всi значення шуканих первинних ключiв вставити у новий файл. Цей файл звичайно називають файлом повiдомлень,
6
а файл, у якому здiйснюється пошук, головним файлом. Головний файл i файл повiдомлень повиннi бути впорядкованi за одним ключем.
Спершу з файла повiдомлень зчитується перше значення первинного ключа i за методом лiнiйного пошуку у головному файлi шукається запис, що йому вiдповiдає. Потiм зчитується друге значення первинного ключа, i пошук у головному файлi продовжується, починаючи з того запису, на якому вiн припинився. Цей процес послiдовно повторюється для всiх значень первинного ключа з файла повiдомлень.
3. КОНТРОЛЬНI ЗАПИТАННЯ
Що таке ефективнiсть доступу до файла на зовнiшньому носiї?
Як органiзовується доступ до файлiв послiдовного доступу?
Яка ефективнiсть зберiгання iнформацiї у файлах з послiдовним доступом?
Скільки записів необхідно переглянути, щоб виявити шуканий запис у файлі послідовного доступу.
Як всталяється новий елемент у файл з послiдовним доступом?
7
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора