Конспект лекций для специальности «Прикладная информатика в экономике»
| Вид материала | Конспект |
- Учебно-методический комплекс для студентов заочного обучения специальности Прикладная, 81.9kb.
- Конспект лекций для специальности «Прикладная информатика в экономике», 535.22kb.
- Конспект лекций для студентов специальности Прикладная информатика (в экономике), 3204.37kb.
- Учебно-методический комплекс для студентов заочного обучения специальности Прикладная, 172.73kb.
- Рабочая учебная программа по Правоведению Для специальности- «Прикладная информатика, 388.83kb.
- Учебно-методический комплекс для студентов заочного обучения специальности Прикладная, 88.44kb.
- Программа по курсу "Математика. Алгебра и геометрия" для специальности 080801 (351400), 143.45kb.
- Учебно-методический комплекс Для специальности 080801 Прикладная информатика (в экономике), 296.07kb.
- Учебно-методический комплекс Для специальности 080801 Прикладная информатика (в экономике), 610.8kb.
- Рабочая программа по дисциплине «Исследование операций в экономике» для специальности, 137.37kb.
3.4.2. Методы физического проектирования для иерархических моделей
Традиционными способами организации хранения иерархических моделей являются: множественные ссылки на порожденные записи, ссылки на порожденные и подобные записи; кольцевые структуры; справочники, битовые отображения.
3.4.2.1. Множественные ссылки на порожденные записи
Для хранения подобных записей в иерархических структурах используются реляционные структуры. Записи файлов могут иметь одно или несколько полей, среди которых можно выделять первичные и вторичные ключи. Для указания связей, которые образуют иерархические структуры, применяют систему ссылок. В случае, когда это ссылки на порожденные записи, каждая из них ссылается на некоторую порожденную запись. Количество таких ссылок соответствует числу порожденных записей. Поскольку у записей, соответствующих элементам максимального уровня иерархии дерева, нет порожденных записей, у них отсутствуют какие-либо ссылки.
Рассмотрим данную организацию хранения элементов для дерева, описывающего состав кафедр некоторого факультета:
Поскольку в этом дереве есть два множества подобных элементов (кафедры и сотрудники), сформируем для них таблицы:
сотрудник кафедра
| ФИО | ученая степень | научное звание | контактные данные | | название | шифр в вузе |
| Иванов И.И. | к.т.н. | доцент | 234567 | | СУиВТ | 239 |
| Петров П.П. | к.т.н. | нет | 456789 | | ТАМ | 145 |
| Сидоров С.С. | нет | нет | 123456 | | | |
| Яковлев Я.Я. | д.т.н. | профессор | 345678 | | | |
Теперь надо показать связи между элементами, указанные в дереве. Для этого, в соответствии с рассматриваемым способом, сформируем у таблицы, описывающей кафедры, дополнительное поле ссылки, в котором и зафиксируем требуемые связи. Получим таблицу:
| название | шифр в вузе | ссылки |
| СУиВТ | 239 | 1, 3 |
| ТАМ | 145 | 2, 4 |
В таком дереве «хорошо» решаются задачи поиска записей в направлении от корня к терминальным вершинам.
Пусть надо сформировать список сотрудников кафедры СУиВТ (эта задача подобна задаче поиска по вторичному ключу для линейных списков), т.е. Кдоступ = <название (кафедры) = СУиВТ>. Задача решается следующим образом:
- по файлу с названиями кафедр находят требуемую кафедру (для решения этой задачи применимы методы поиска, рассмотренные ранее для последовательной организации данных) – это запись с номером 1;
- выбирают ссылки – это множество {1, 3};
- по линейному списку с фамилиями сотрудников обращаются к элементам с номерами 1и 3. Получают список сотрудников: Иванов И.И., Сидоров С.С. Алгоритм заканчивает работу.
3.4.2.2. Ссылки на подобные и порожденные записи
Аналогично предыдущему методу подобные записи описываются в реляционных структурах. Для указания связей применяют два вида ссылок: одна фиксирует связь с первой порожденной записью, вторая – с подобной. Причем с помощью подобия показывается, каким родительским записям принадлежат порожденные. Для записей, соответствующих максимальному уровню иерархии, поддерживается только одна ссылка (на подобные записи), поскольку они не имеют порожденных записей; для записей первого уровня иерархии также поддерживается одна ссылка (на порожденные записи), поскольку все они имеют одного родителя – корень. Для остальных записей поддерживается две ссылки.
Рассмотрим данную организацию хранения элементов для дерева:
Для уровня кафедр (нулевого уровня дерева) устанавливаются только ссылки на порожденные записи, поскольку все кафедры принадлежат одному факультету, т.е. подобны по этому признаку. Для уровня сотрудников поддерживается ссылка на подобные элементы, с помощью которой показывается цепочка сотрудников одной кафедры:
сотрудник кафедра
| ФИО | ученая степень | научное звание | контактные данные | ссылки | | название | шифр в вузе | ссылки |
| Иванов И.И. | к.т.н. | доцент | 234567 | 3 | | СУиВТ | 239 | 1 |
| Петров П.П. | к.т.н. | нет | 456789 | 4 | | ТАМ | 145 | 2 |
| Сидоров С.С. | нет | нет | 123456 | - | | | | |
| Яковлев Я.Я. | д.т.н. | профессор | 345678 | - | | | | |
Преимущество этого метода организации хранения иерархических моделей состоит в однотипности списков ссылок: они всегда содержат по одной ссылке (пустой, если цепочка закончена).
3.4.2.3. Кольцевые структуры
В отличие от предыдущих методов позволяют от порожденных записей переходить к родительским. Для этого в структуре записей поддерживаются специальные ссылки на «родителей».
Представим данным методом дерево:
Его описание сведем в таблицы:
сотрудник кафедра
| ФИО | ученая степень | научное звание | контактные данные | ссылки на подобные | ссылки на родительские | | название | шифр в вузе | ссылки |
| Иванов И.И. | к.т.н. | доцент | 234567 | 3 | 1 | | СУиВТ | 239 | 1 |
| Петров П.П. | к.т.н. | нет | 456789 | 4 | 2 | | ТАМ | 145 | 2 |
| Сидоров С.С. | нет | нет | 123456 | 1 | 1 | | | | |
| Яковлев Я.Я. | д.т.н. | профессор | 345678 | 4 | 2 | | | | |
Как видно, в таблице сотрудников отсутствуют пустые ссылки. Это означает, что конечные записи в цепочках подобных записей ссылаются на первые записи в этих цепочках. Так получаются «горизонтальные» кольца. Наличие таких колец позволяет решать задачи, требующие многократного просмотра записей от начала к концу. Подобная задача, например, имеет место при сортировке файла некоторыми методами. Например, когда требуется отсортировать список сотрудников кафедры СУиВТ по возрастанию значений ключа, а кафедры ТАМ – по убыванию. В то же время совокупность ссылок на порожденные и родительские записи формирует «вертикальные» кольца. Они позволяют переходить от порожденных записей к родительским, чего не было в предыдущих методах.
3.4.2.4. Справочники
Связи между записями дерева формируют отдельное описание в виде файла-справочника.
Пусть исходное дерево имеет вид:
Описание сотрудников и кафедр располагается в таблицах:
сотрудник кафедра
| ФИО | ученая степень | научное звание | контактные данные | | название | шифр в вузе |
| Иванов И.И. | к.т.н. | доцент | 234567 | | СУиВТ | 239 |
| Петров П.П. | к.т.н. | нет | 456789 | | ТАМ | 145 |
| Сидоров С.С. | нет | нет | 123456 | | | |
| Яковлев Я.Я. | д.т.н. | профессор | 345678 | | | |
Сформируем для дерева справочник:
| обозначение поля | элемент дерева | родительская запись | порожденная запись |
| название (кафедры) | СУиВТ | - | 3, 5 |
| название (кафедры) | ТАМ | - | 4, 6 |
| ФИО | Иванов И.И. | 1 | - |
| ФИО | Петров П.П. | 2 | - |
| ФИО | Сидоров С.С. | 1 | - |
| ФИО | Яковлев Я.Я. | 2 | - |
3.4.2.5. Битовые отображения
Структура дерева представляется бинарной матрицей. Вначале формируются обозначения столбцов и строк матрицы следующим образом:
- выписываются обозначения столбцов, начиная с первого столбца, - им соответствуют обозначения элементов первого уровня иерархии дерева;
- затем выписываются обозначения элементов второго уровня иерархии в качестве обозначений строк;
- процесс выписывания обозначений столбцов и строк продолжается, чередуясь, пока ни будут выбраны все уровни иерархии дерева.
Затем в ячейках матрицы на пересечении обозначений столбцов и строк проставляются единицы, если между ними есть связи в дереве, и нули в противном случае.
Так, для дерева из примера битовое отображение будет соответствовать таблице:
| Обозначения строк | Обозначения столбцов | |
| СУиВТ | ТАМ | |
| Иванов И.И.. | 1 | 0 |
| Петров П.П. | 0 | 1 |
| Сидоров С.С. | 1 | 0 |
| Яковлев Я.Я. | 0 | 1 |
3.4.3. Методы физического проектирования для сетевых моделей
Для организации хранения сетей и доступа к их элементам используют методы: множественные ссылки на порожденные записи; ссылки на порожденные и подобные записи; кольцевые структуры; справочники; битовые отображения. Следует отметить, что рассматриваемые далее способы аналогичны тем, которые приводились ранее для деревьев.
3.4.3.1. Множественные ссылки на порожденные записи
Пусть исходная сеть имеет вид:
Тогда ее описание задано в таблицах:
сотрудник кафедра должность
| ФИО | ученая степень | научное звание | контактные данные | | название | шифр в вузе | ссылки | | название | образование | ссылки |
| Иванов И.И. | к.т.н. | доцент | 234567 | | СУиВТ | 239 | 1, 3 | | ассистент | высшее | 3 |
| Петров П.П. | к.т.н. | нет | 456789 | | ТАМ | 145 | 2, 4 | | доцент | высшее | 1, 2 |
| Сидоров С.С. | нет | нет | 123456 | | | | | | профессор | высшее | 4 |
| Яковлев Я.Я. | д.т.н. | профессор | 345678 | | | | | | | | |
3.4.3.2. Ссылки на подобные и порожденные записи
Пусть сеть имеет вид:
Тогда ее описание задано в таблицах:
сотрудник кафедра должность
| ФИО | ученая степень | научное звание | контактные данные | ссылки для цепи кафедр | ссылки для цепи должностей | | название | шифр в вузе | ссылки | | название | образование | ссылки |
| Иванов И.И. | к.т.н. | доцент | 234567 | 3 | 2 | | СУиВТ | 239 | 1 | | ассистент | высшее | 3 |
| Петров П.П. | к.т.н. | нет | 456789 | 4 | - | | ТАМ | 145 | 2 | | доцент | высшее | 1 |
| Сидоров С.С. | нет | нет | 123456 | - | - | | | | | | профессор | высшее | 4 |
| Яковлев Я.Я. | д.т.н. | профессор | 345678 | - | - | | | | | | | | |
3.4.3.3. Кольцевые структуры
Пусть сеть имеет вид:
Описание элементов сети задано в таблицах:
сотрудник
| ФИО | ученая степень | научное звание | контактные данные | ссылки на подобные для цепи кафедр | ссылки на родительские для цепи кафедр | ссылки на подобные для цепи должностей | ссылки на родительские для цепи должностей |
| Иванов И.И. | к.т.н. | доцент | 234567 | 3 | 1 | 2 | 2 |
| Петров П.П. | к.т.н. | нет | 456789 | 4 | 2 | 1 | 2 |
| Сидоров С.С. | нет | нет | 123456 | 1 | 1 | 3 | 1 |
| Яковлев Я.Я. | д.т.н. | профессор | 345678 | 2 | 2 | 4 | 4 |
кафедра должность
| название | шифр в вузе | ссылки | | название | образование | ссылки |
| СУиВТ | 239 | 1 | | ассистент | высшее | 3 |
| ТАМ | 145 | 2 | | доцент | высшее | 1 |
| | | | | профессор | высшее | 4 |
3.4.3.5. Справочники
Пусть сеть имеет вид:
Описание элементов сети задано в таблицах:
сотрудник кафедра должность
| ФИО | ученая степень | научное звание | контактные данные | | название | шифр в вузе | | название | образование |
| Иванов И.И. | к.т.н. | доцент | 234567 | | СУиВТ | 239 | | ассистент | высшее |
| Петров П.П. | к.т.н. | нет | 456789 | | ТАМ | 145 | | доцент | высшее |
| Сидоров С.С. | нет | нет | 123456 | | | | | профессор | высшее |
| Яковлев Я.Я. | д.т.н. | профессор | 345678 | | | | | | |
Описание связей между элементами сети задано таблицей:
| обозначение поля | элемент сети | родительская запись | порожденная запись |
| название (кафедры) | СУиВТ | - | 6, 8 |
| название (кафедры) | ТАМ | - | 7, 9 |
| название (должности) | ассистент | - | 8 |
| название (должности) | доцент | - | 6, 7 |
| название (должности) | профессор | - | 9 |
| ФИО | Иванов И.И. | 1 | - |
| ФИО | Петров П.П. | 2 | - |
| ФИО | Сидоров С.С. | 1 | - |
| ФИО | Яковлев Я.Я. | 2 | - |
3.4.3.6. Битовые отображения
Пусть исходная сеть соответствует последнему примеру. Описание элементов сети задано в таблицах:
сотрудник кафедра должность
| ФИО | ученая степень | научное звание | контактные данные | | название | шифр в вузе | | название | образование |
| Иванов И.И. | к.т.н. | доцент | 234567 | | СУиВТ | 239 | | ассистент | высшее |
| Петров П.П. | к.т.н. | нет | 456789 | | ТАМ | 145 | | доцент | высшее |
| Сидоров С.С. | нет | нет | 123456 | | | | | профессор | высшее |
| Яковлев Я.Я. | д.т.н. | профессор | 345678 | | | | | | |
Связи между элементами сети показаны в таблице:
| Обозначение строк | Обозначение столбцов | |||||
| название (кафедры) | название (должности) | |||||
| СУиВТ | ТАМ | ассистент | доцент | профессор | ||
| ФИО | Иванов И.И. | 0 | 1 | 0 | 0 | 1 |
| Петров П.П. | 0 | 0 | 0 | 1 | 0 | |
| Сидоров С.С. | 0 | 1 | 0 | 0 | 0 | |
| Яковлев Я.Я. | 0 | 1 | 0 | 0 | 0 | |