К выполнению курсовой работы

Методические указания

К выполнению курсовой работы

по дисциплине

«Структуры и алгоритмы обработки данных»

 

Новочеркасск 2008

УДК 519.256 (076.5)

 

 

Рецензент канд. техн. наук, проф. Г. В. Сучков

 

 

Составитель Мясникова Н.А.

 

Методические указания к выполнению курсовой работы по дисциплине “Структуры и алгоритмы обработки данных”/Юж.-Рос. гос. техн. ун-т. – Новочеркасск: ЮРГТУ, 2008. – 39с.

 

В методических указаниях приведен перечень заданий на курсовую работу, даны пояснения к выполнению ее основных этапов.

Предназначены для студентов второго курса специальностей “Программное обеспечение вычислительной техники”, “Автоматизированных систем” и “Системы автоматизированного проектирования”.

 

 

© Южно-Российский государственный

                                        технический университет, 2008

                                              ©  Мясникова Н.А., 2008

Введение

Основными элементами современных информационных технологий являются базы данных (БД) и системы управления базами данных (СУБД), роль которых как единого средства хранения, обработки и доступа к большим объемам информации постоянно возрастает. При этом существенным является постоянное увеличение объемов информации, хранимой в БД, что влечёт за собой требование увеличения производительности таких систем.

Пакеты СУБД дают возможность пользователям осуществлять непосредственное управление данными, а программистам быстро разрабатывать более совершенные программные средства их обработки.

В данной курсовой работе студентам представляется возможность выступить в роли разработчика фрагмента СУБД, используя знания, полученные в процессе изучения курса «Структуры и алгоритмы обработки данных» (способы проектирования всевозможных структур данных и методы их обработки – сортировку, поиск, доступ). Дисциплина «Структуры и алгоритмы обработки данных» является обеспечивающей для последующего изучения дисциплины «Базы данных».

 

Цель и задачи проектирования

Цель курсового проектирования по дисциплине «Структуры и алгоритмы обработки данных» – развитие навыков самостоятельной творческой работы по анализу информационных потоков, конструированию рациональных структур данных, разработка, применение и программирования функциональных алгоритмов обработки данных.

Основные задачи: закрепление и улучшение теоретических знаний по проектированию разнообразных структур данных, алгоритмов поиска и сортировки данных, методов доступа к данным; дальнейшее развитие навыков программирования на языках высокого уровня; использование полученных знаний для создания фрагментов информационно-поисковых систем.

Курсовая работа выполняется в соответствии с заданием, в котором приводятся конкретные формы ввода-вывода информации в различных производственных системах, а также варианты алгоритмов поиска, сортировки данных, методов доступа, необходимых для организации файловой системы и её функционирования. Информационная система реализуется на ЭВМ в виде комплекса программ.

 

Задание к курсовой работе

Разработать структуру хранения информации во внешней памяти ПЭВМ, представленной в формах (см. Приложение). Разработать программы формирования полученных файлов и печати данных форм для заданной группы лиц. Предусмотреть возможность индексного (прямого и др.) доступа к файлам, сортировки и поиска записей файлов. Разработать программу ведения[1] индексных файлов (для индексного доступа). Реализовать три запроса к файловой системе. Предусмотреть типы отношений между записями файлов.

 

           В таблице 1 представлены варианты заданий.

                                                                                                   Таблица 1

Варианты заданий

                                                                                

Номер варианта	Формы ввода-вывода	Методы*
		доступа	поиска в индексе	хеширования	сортировки
1	О1,О2	1	3		16
2	О1,О3	2.1	7		4
3	О1,О4	2.2	9		10
4	О1,О5	3.1	13		11
5	О1,О6	3.2	2	4,13	5
6	О1,О7	4.1	1		8
7	О1,О8	4.2	3		6
8	О1,О9	3.1	4		9
9	Б1,Б2	4.2	1		3
10	Б1,Б3	3.2	2	5,14	2
11	Б1,Б4	2.2	8		13
12	Б1,Б5	2.1	12		1
13	Б1,Б6	4.1	2		12
14	Б1,Б7	1	11		15
15	Б1,Б8	4.2	1		14
16	Б1,Б9	4.1	3		7
17	Г1,Г2	3.2	2	6,11	4
18	О1,О8	3.1	4		6
19	О9	2.2	13		2
20	Б1,Б4	2.1	6		9
21	Б1,Б3	1	3		13
22	Б1,Б5	3.2	11	3,12	16
23	Б1,Б6	4.1	1		8
24	Б1,Б7	2.2	5		15
25	Г1,Г2	2.1	10		11

 

* Коды методов даны в приложении

Пояснения к работе

                

Методы доступа

В зависимости от способа хранения записей методы доступа можно объединить в следующие 4 группы:

1) последовательные методы;

2) индексные методы;

3) адресные методы;

4) мультисписковые методы.

Группа последовательных методов включает в себя физически последовательный метод доступа и связанную последовательную организацию. Отличие этих методов заключается в том, что с использованием первого метода возможно размещение файла в одном непрерывном участке памяти, а с использованием второго файл размещается в нескольких физически несмежных участках внешней памяти.

Группа индексных методов отличается тем, что кроме файла данных для выборки и занесения записей создается дополнительный, так называемый индексный файл.

В адресных методах доступа значение записи несет в себе физический адрес ее хранения, что позволяет достичь высокой скорости как занесения данных, так и выборки.

В четвертую группу объединяются мультисписковые и другие методы. Их особенность заключается в том, что они используют для хранения данные более одного служебного файла (или списков), как правило, базируются на методах доступа, включенных в первые три группы.

Зададим два основных критерия оценки методов организации данных:

Э_Д = 1\N, Э_Х = 1\k,

где Э_Д – эффективность доступа  –  величина, обратная среднему числу N обращений, необходимых для осуществления запроса конкретной записи БД. Например, если система для поиска нужной записи обращается к двум записям, то Э_Д = 0,5;

Э_Х – эффективность хранения – величина, обратная среднему числу k байтов поля вторичной памяти, требуемого для хранения одного байта исходных данных. Кроме исходных данных, память занимают таблицы, управляющая информация, свободная область, резервируемая для расширений, и область, не используемая из-за фрагментации.

 

Последовательные методы доступа

 

Наиболее эффективной для последовательной обработки больших объемов данных является физически последовательная структура. Последовательное смежное размещение записей допускает физическое блокирование, тем самым минимизируя время доступа к данным.

Обработка небольших объемов данных, особенно при высокой степени изменчивости, часто оказывается наиболее эффективной при структуре хранения в виде последовательно соединенных участков (связанная последовательная структура).

Физически последовательная и связанная последовательная структуры являются базовыми для очень большого класса методов доступа: индексно-последовательного, мультиспискового, инвертированного и различных механизмов поиска с использованием деревьев.

Физически последовательные структуры представляют собой простейший вид организации (рис. 1).

 

Иванов

Петров

Сидоров

Харламов

Мищенко

…

 

Рис. 1. Физически последовательная организация данных

 

Физически последовательный метод доступа предполагает хранение физических записей в логической последовательности.

При использовании магнитной ленты программист должен предоставить системе физические записи в логической последовательности. В том случае, когда носителем служит память прямого доступа, система связывает физические записи таким образом, что они образуют логическую последовательность, даже если они не передавались ей в этой последовательности (т.е. при использовании устройства прямого доступа каждой следующей представляемой физической записи система отводит следующий доступный участок физической памяти). Затем между записями базы данных организуются связи, обеспечивающие возможность логически последовательной выборки.

При необходимости вести последовательную обработку данных, которые расположены в физически несмежных участках памяти, используют модификацию данного метода, которая получила название связанной последовательной организации (рис. 2). Основное различие между связанной последовательной и физически последовательной организациями заключается в применении в первом случае специальных указателей вместо смежного размещения данных в памяти.

 

Блок 1			Блок 6			Блок 25			Блок 36
Иванов	Блок 6		Петров	Блок 7	…	Сидоров	Блок 36		Мищенко

 

          Рис. 2. Связанная последовательная организация данных

 

Эффективность доступа последовательного физического метода крайне низка. Для выборки нужной записи необходимо просмотреть все предшествующие ей записи. Чтобы включить запись, её необходимо поместить в последний блок, если в нем имеется место, либо получить новый блок. Удаления записей осуществляются установкой бита удаления в удаляемой записи.

 

  Индексные методы доступа

Структуры типа Б-дерева. Одним из наиболее важных и распространенных индексов является структура типа Б-дерева (B-tree). Хотя не существует универсальной структуры хранения, оптимальной для любых приложений, все же нет сомнений, что для использования в простых системах следует выбирать индекс бинарного типа. Благодаря тому, что бинарные индексы обла­дают в большинстве случаев сравнительно высокой производительностью, их использо­вание предусмотрено почти во всех СУБД, а некоторые СУБД работают только на осно­ве такого индекса.

Прежде чем дать описание структуры типа Б-дерева, следует разъяснить суть таких основных понятий, как многоуровневый или древовидный индекс.

Причина необходимости создания структуры типа Б-дерева заключается в желании избежать обязательного просмотра всего содержимого индексированного файла соглас­но его физической последовательности. Дело в том, что если индексированный файл имеет большой размер, то и его индекс также очень велик. Поэтому последовательный просмотр даже одного только индекса требует больших затрат времени. Разрешить эту проблему можно тем же способом, что и раньше: рассмотреть индексный файл как обычный хранимый файл и создать для него еще один индекс. Эту операцию можно осуществлять повторно нужное количество раз (обычно она применяется трижды, по­скольку создание большого количества иерархических уровней индексирования требует­ся для очень больших файлов). При этом индекс на каждом из уровней будет неплотным по отношению к нижнему индексируемому уровню (он обязательно должен быть не­плотным, иначе такая структура бессмысленна, так как уровень п содержал бы такое же количество записей, что и уровень п+ 1, а для просмотра потребовалось бы такое же дли­тельное время).

Согласно терминологии VSAM, в варианте Кнута индекс состоит из двух частей: на­бора последовательностей и набора индексов.

Набор последовательностей включает одноуровневый индекс для реальных данных, который обычно является плотным, но может быть и неплотным, если в индексиро­ванном файле проведена кластеризация на основе индекса. Записи внутри индекса сгруппированы по страницам, а страницы связаны в цепочку таким образом, чтобы логическое упорядочение на основе индекса осуществлялось внутри первой страницы, затем с помощью физической последовательности записей - внутри второй страницы этой последовательной цепочки и т.д. Таким образом, с помощью набора последовательностей можно организовать быстрый последовательный доступ к ин­дексированным данным.

Набор индексов, в свою очередь, обеспечивает быстрый непосредственный доступ к набору последовательностей (а значит, и к данным). По сути, набор индексов являет­ся древовидным индексным файлом для набора последовательностей или, строго говоря, индексом со структурой Б-дерева. Комбинация набора индексов и набора по­следовательностей называется структурой типа Б-плюс-дерева (B-plus tree или B^tree). На самом верхнем уровне такого индекса находится только один элемент структуры (страница, содержащая множество записей), который называется корневым (root).

Индексные Б–деревья. Верхний (первый) уровень индекса делит весь диапазон возможных значений ключа на m крупных интервалов (3).

Каждая ячейка 1–го уровня связана с блоком (страницей) ячеек 2–го уровня индекса. Каждая ячейка каждого блока 2–го уровня связана с блоком ячеек 3–го уровня и т. д.

Блок каждого уровня, лежащего ниже, делит соответствующий диапазон значений ключа на m более мелких интервалов. Ячейки самого нижнего уровня связаны указателями с записями основного массива. Все уровни индекса упорядочены по возрастанию значений ключа.

На рис. 3 изображено индексное дерево (3 уровня, построенные для упорядоченного основного массива, записи которого имеют диапазон значений ключа от 6 до 99).

Рис. 3. Пример структуры типа Б-дерева

 

Индексно-последовательная организация файла

Записи располагаются на внешнем запоминающем устройстве (ВЗУ) в конкретной физической последовательности. Последовательность расположения данных часто совпадает с последовательностью их обработки.

Например, еженедельная обработка счетов клиентов фирмы (или банка) в последовательности, соответствующей порядковым номерам обрабатываемых счетов.

Обработка данных усложняется, если последовательность записей файла не соответствует последовательности их обработки. При этом возникает необходимость сортировки записей, что требует значительных временных затрат (особенно когда данные хранятся на МЛ). Применение устройств с прямым доступом в совокупности с выбором наиболее приемлемой последовательности расположения записей файла существенно ускоряет процесс обработки данных.

Наиболее общий метод упорядочения записей заключается в размещении записей в соответствии с возрастанием их ключей (ключи используются для адресации записей). Если же ключи следуют не в строго определенном порядке, то прямая адресация затруднительна и для выполнения поиска какой-нибудь записи требуется специальный индекс, чтобы не просматривать весь файл (последовательно с самого начала).

Индекс представляет собой таблицу, в которой выполняются операции поиска.

Для работы с индексно-последовательным файлом можно использовать два режима обработки:

1. Последовательная обработка, при которой записи обрабатываются в последовательности их размещения в ВЗУ.

2. Произвольная обработка, при которой записи обрабатываются в произвольной последовательности, не связанной с физической организацией записей на внешнем устройстве.

В зависимости от того, какой режим обработки записей преобладает, выбирают ту или иную разновидность индексно-последовательной организации. Одни файлы используются в основном в режиме последовательной обработки записей, и только в редких случаях требуется произвольная обработка, для других файлов может преобладать режим произвольной обработки. Преобладание одного из режимов обработки отражается в используемых методах организации файлов. Для первого типа файлов записи организованы последовательно и имеется дополнительный индекс, позволяющий обращаться к записям в произвольном порядке. Для второго типа файлов стремятся максимизировать эффективность использования файла при произвольном обращении к записям, не заботясь об удобстве последовательной обработки записей.

Если записи упорядочены в соответствии с возрастанием их ключей, то затраты памяти на индекс для этих ключей могут быть существенно меньше, чем в случае, когда записи не упорядочены.

Индекс для непоследовательного (произвольного) файла более чем в N раз превышает индекс для последовательного файла (N – число элементов в каждом индексном блоке).

Ведение индексно-последовательного файла. Хотя последовательная организация данных (рис.3) требует меньший индекс, она более сложна для эксплуатации файла. При включении новых записей возникает необходимость либо пересортировки файла, либо внесения новых записей в отдельную область и организации указателей на эти записи. При включении новых записей в последовательный файл они помещаются в область переполнения. Недостаток хранения записей в области переполнения заключается в том, что при всяком обращении к этим записям требуются дополнительные операции чтения и, возможно, перемещение головок чтения-записи на внешнем устройстве. Поэтому файлы, имеющие область переполнения, периодически реорганизуются, т.е. записи файла заново сортируются и производятся соответствующие изменения в индексе. Эта операция называется ведением файла.

На рис. 4 показано включение новых записей в файл с последовательным расположением записей. Новые записи просто включаются в конец файла, и при этом не требуются указатели на область переполнения и выполнение специальных программ поддержки включения записей. Однако в данном случае возникает необходимость некоторой перегруппировки элементов индекса. Если файл очень большой или записи в него добавляются очень часто (изменчивый файл), то такой режим работы позволяет обойтись без сложных процедур ведения, и записи данных могут храниться в произвольном порядке.

При последовательном расположении записей можно избежать частого выполнения процедуры ведения, предусматривая в файле позиции с пустыми записями (рис. 4). Этот метод, основанный на включении пропусков в файле для ожидаемого включения новых элементов данных, называется методом распределения свободнойпамяти (distributed free space). Однако данный метод не позволяет полностью избежать выполнения процедуры ведения.

1	Анохин
2	Бунин	100
3	Васильев
4	Воробьева
5	Гаврилов
6	Денисов
7	Доценко	101
8	Егоров
9	Ершов
10	Коленов
11	Минаев	102
12	Орехов
13	Тарасов
14	Ушакова
15	Федоров
16	Юшина
17	Ященко	103
18

 

100	Анохин	101
101	Доценко
102	Коленов
103	Юшина

Анохин Коленов

Не использован

Коленов Тарасов Юшина

Анохин Воробьева Доценко

                                                                                                                                                                               

 

 

Указатель на область переполнения

 

 

                                                                                                                                               

 

 

 

Рис. 4. Индексно-последовательная организация файла. Ведение файла (использование области переполнения)

 

 

 

1. Бунин

2.

Анохин Васильев Гаврилов

Васильев Воробьева

Воробьева

3. Юшина

4. Минаев

5.

Гавриков Денисов

Ершов

6. Анохин

7. Доценко

8.

Анохин Доценко Тарасов

Доценко Егоров

Денисов

9. Ушакова

10. Ященко

11.

Ершов Каленов

Орехов

12. Тарасов

13.

Доценко Ершов Минаев

Минаев Орехов

Гаврилов

14. Васильев

15. Егоров

16.

Тарасов Ушакова

Каленов

17. Федоров

18.

Тарасов Федоров Ященко

Федоров Юшина

 Лунин

19.  Зуева

20.  Зинченко

21.

Ященко

 Морозова

 

 

Рис.5. Индексно-произвольная организация файла

 

В случае индексно-произвольной организации файла индексный аппарат более сложный по сравнению с индексно-последовательной организацией (рис. 5).

 

Поиск: Воробьева à А нохин - В асильев - В оробьева (последовательно)

(ближайшее максимальное значение меньше заданного).

 

Поиск. Поиск записи с определённым значением ключа начинается с просмотра верхнего уровня индекса. В блоке индекса ищется значение ключа, меньшее или равное искомому, причем предыдущая запись блока должна иметь меньший ключ. От найденной записи по указателю спускаются в порождённый блок второго уровня индекса и в нём отыскивают запись с меньшим или равным искомому значением ключа. От этой записи переходят в порождённый блок 3-го уровня и т. д., вплоть до нахождения нужной записи в основном массиве или до выработки сообщения об отсутствии нужной записи: 

 

 

Pi

Xi

Pi+1

Xi+1

Pi+2…

Pn-1

Xn-1

Pn

 

         

где  Xi – i-е значение индексируемого поля;   

Pi – указатель на вершину, создающую значение                     индексируемого поля, меньший или равный Xi;

Pi+1 – указатель на вершину, создающую значение                     индексируемого поля, больший Xi;  

Pn – указатель последнего поля.                                                         

                             

Адресные методы доступа

Суть прямого метода доступа состоит во взаимно однозначном соответствии между ключом записи и её физическим адресом. Физическое местоположение записи определяется непосредственно из значения ключа в том случае, если проектировщик БД в состоянии предусмотреть в памяти для каждой записи место, определяемое уникальным значением её первичного ключа. Тогда можно построить простую функцию преобразования ключа в адрес, обеспечивающую запоминание и выборку каждой записи в точности за один произвольный доступ к блоку. С этой целью каждой совокупности ключевых значений записей, расположенных в одном и том же физическом блоке, можно присвоить относительный номер блока (относительный физический адрес). На самом деле данные хранятся в соответствии с порядком ключей, но при этом им неявно последовательно присвоены относительные номера блоков.

       

 

 

Номер группы		Преобразование ключа в адрес		Файл данных
К01			1	К01
К02			2	К02
К03			3	К03
…			…	…
К10			10	К10
Л01			11	Л01
Л02			12	Л02
…			…	…
Л10			21	М01
М01			22	М02
М02			23	Пустая запись
Отсутствует			24	М04
М04			25	Пустая запись
Отсутствует			24	М04
М06			25	Пустая запись
…			…	…
М10			30	М10

 

 

Рис. 6. Организация хранения и выборки записей, данных файла “Группа” методом

        прямого доступа

 

 

На рис. 6 приведен простой пример организации записей файла “Группа” БД “Факультет”. При вычислении адреса хранения записи в этом примере используется следующий алгоритм: если предположить, что номера студенческих групп на факультете начинаются с буквы, то далее следует цифра не более 10.

У всех исходных ключей, начинающихся с литеры “К”, взять последние цифры, использовать их в качестве целевого ключа и адреса хранения;

у “Л”– взять цифры, прибавить 10 -> адрес;

у “М”- взять цифры, прибавить 20 -> адрес и т. д.

Если некоторые физические записи (например, с ключом М03 и М05) отсутствуют, то память для этих записей резервируется.

Эффективность доступа. Если между значением ключа и физическим адресом существует взаимно однозначное соответствие, то Э_д = 1 (всегда).

Эффективность хранения зависит от плотности ключей. При низкой плотности память расходуется нерационально, поскольку резервируются адреса, соответствующие отсутствующим ключам.

Этот метод отличается простотой, и если бы во всех приложениях существовала бы возможность управлять значениями ключей, то этот метод доступа был бы распространен значительно шире. Однако “неуправляемость” ключа является обычной проблемой, присущей большинству БД.

Произвольный метод доступа. Хеширование

Этот метод, как и прямой, основан на алгоритмическом определении адреса физической записи по значению её ключа. Различие состоит в том, что при прямом методе доступа имеет место взаимно однозначное отображение ключа в адрес, а метод доступа посредством хеширования допускает возможность отображения многих ключей в один адрес.

Идентификатор – атрибут, уникально определяющий запись.

Хеширование идентификатора – метод доступа, обеспечивающий прямую адресацию данных путем преобразования значения ключа в относительный или абсолютный физический адрес.

Алгоритм получения адреса называется функцией хеширования, или функцией преобразования ключа. При использовании хеш-функции возможно преобразование двух или более значений ключа в один и тот же физический адрес.

Коллизия – случай преобразования ключа в уже занятый собственный адрес.

Хешированием, хеш-адресацией или хеш-индексированием называется технология быстрого прямого доступа к хранимой записи на основе заданного значения некоторого поля. При этом необязательно, чтобы поле было ключевым. Ниже перечислены основ­ные черты этой технологии.

• Каждая хранимая запись базы данных размещается по адресу (RID-указателю или номеру страницы), который вычисляется с помощью специальной хеш-функции на основе значения некоторого поля данной записи, т.е. хеш-поля, или хеш-ключа. Вычисленный адрес называется хеш-адресом.

• Для сохранения записи в СУБД сначала вычисляется хеш-адрес новой записи, а затем диспетчер файлов помещает эту запись по вычисленному адресу.

• Для извлечения нужной записи по заданному значению хеш-поля в СУБД сначала вычисляется хеш-адрес, а затем диспетчеру файлов посылается запрос для извлечения записи по вычисленному адресу.

Пример: хеш-адрес (т.е. номер страницы) = остаток от деления на 13 числа, содержащегося в поле номера записи S#

Это простейший пример общего класса хеш-функций типа деление/остаток. В каче­стве делителя следует выбирать простое натуральное число. В этом примере номерами страниц для заданных записей будут 9, 5, 1, 10 и 6 соответственно.

Из вышеизложенного ясно, что хеширование отличается от индексирования тем, что в файле может быть любое количество индексов, но только одна структура хеширования или, иначе говоря, одно хеш-поле. (В этом замечании предполагается, что хеширование является прямым, однако в файле можно задать любое количество косвенных хеширова­ний.)

Кроме демонстрации принципа работы хеширования, в данном примере также по­казано, почему возникает необходимость использовать для хеш-функции специальную функцию. Теоретически можно было бы для определения адреса вместо функции ис­пользовать непосредственно значение ключевого поля (если это поле имеет числовой тип). Однако практически такой способ неприемлем, поскольку количество значений может быть большим. Таким образом, во избежание неэффективного ис­пользования дискового пространства следует найти такую хеш-функцию, чтобы можно было сузить диапазон, например от 000-999 до 0-9. Для того чтобы зарезервировать до­полнительное пространство (размером 20 % от исходной величины), диапазон 0-9 в дан­ном примере расширен до 0-12.

В этом примере также наглядно проявляется недостаток хеширования. Дело в том, что физическая последовательность записей внутри хранимого файла почти всегда отличается от последовательности ключевого поля, а также любой другой логически задан­ной последовательности.

Еще одним недостатком хеширования является возможность возникновения коллизий, т.е. ситуаций, когда две или более различных записи ("синонимы") имеют одинаковые адреса. Допустим, что файл поставщиков из предыдущего примера содержит также запись с номером S1400. При использовании хеш-функции типа "остаток от деления на 13" возникнет коллизия (по адресу 9) с запи­сью S100. Ясно, что такая хеш-функция неадекватна и для устранения коллизий необхо­димо ее исправить.