Презентация на тему: Методы организации данных и ЭИС

Методы организации данных и ЭИС
Введение
Повестка дня
Обзор
Словарь терминов
Анализ алгоритмов и структур данных.
Анализ алгоритмов и структур данных.
Анализ алгоритмов и структур данных.
Анализ алгоритмов и структур данных.
Анализ алгоритмов и структур данных.
Анализ алгоритмов и структур данных.
Анализ алгоритмов и структур данных.
Анализ алгоритмов и структур данных.
Анализ алгоритмов и структур данных.
Анализ алгоритмов и структур данных.
Методы ускорения доступа к данным
Методы ускорения доступа к данным
Методы ускорения доступа к данным
Методы организации данных и ЭИС
Организация данных во внешней памяти ЭВМ
Организация данных во внешней памяти ЭВМ
Организация данных во внешней памяти ЭВМ
Организация данных во внешней памяти ЭВМ
ВЫВОДЫ
1/24
Средняя оценка: 4.4/5 (всего оценок: 89)
Код скопирован в буфер обмена
Скачать (440 Кб)
1

Первый слайд презентации: Методы организации данных и ЭИС

Кафедра Информационных технологий и управляющих систем Предмет «Информационное обеспечение, базы данных, сети ЭВМ» Лекция Доцент Стрельцова Г. А.

Изображение слайда
2

Слайд 2: Введение

Организация значений данных – относительно устойчивый порядок расположения записей данных в памяти ЭВМ и способ обеспечения связей между ними. Область применения методов организации данных - базы и банки данных. Необходимые знания: понимание процессов, происходящих при представлении информации в ЭИС.

Изображение слайда
3

Слайд 3: Повестка дня

Список изучаемых разделов: Анализ алгоритмов и структур данных. Методы ускорения доступа к данным. Организация данных во внешней памяти ЭВМ. Время, отводимое на каждый раздел: 15-20 минут.

Изображение слайда
4

Слайд 4: Обзор

Разделы лекции Анализ алгоритмов и структур данных Методы ускорения доступа к данным Организация данных во внешней памяти ЭВМ

Изображение слайда
5

Слайд 5: Словарь терминов

СЕИ - набор из атрибутов или других составных единиц информации (СЕИ). ЗАПИСЬ – отдельное значение СЕИ, находящееся в памяти ЭВМ. КЛЮЧЕВОЙ АТРИБУТ (атрибут-признак) –атрибут, имя которого одинаково во всех записях ПОИСК –процедура выделения некоторых записей, удовлетворяющих заранее поставленному условию. СОРТИРОВКА – процедура, осуществляющая перестановку СЕИ с целю упорядочения значений некоторого ключевого атрибута КОРРЕКТИРОВКА – процедура включения, исключения, изменения значений отдельных неключевых атрибутов в записях. СПИСОК – множество записей, занимающих произвольные участки памяти, последовательность обработки которых задается с помощью адресов связи. ИНДЕКС – набор ключей и адресов записи, которые выбираются из основного массива по определенному закону.

Изображение слайда
6

Слайд 6: Анализ алгоритмов и структур данных

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

Изображение слайда
7

Слайд 7: Анализ алгоритмов и структур данных

Линейные методы организации данных. Различаются способами указания предыдущей и последующей записи по отношению к данной записи. Разделяются на последовательную и цепную (списковую) организацию данных. Делятся на записи фиксированной, переменной и неопределенной длины. Длина переменных записей указывается в самой записи (специальным символом-разделителем). Записи переменной и неопределенной длины занимают меньший объем памяти, но обрабатываются большее время.

Изображение слайда
8

Слайд 8: Анализ алгоритмов и структур данных

Формула адреса промежуточной записи фиксированной длины: A(i) =A(1) + (i-1) *L, где A(1) - начальный адрес первой записи, A(i) - начальный адрес i -той записи, L – длина одной записи. Последовательная организация данных Условие упорядоченности: p(i)<= p(i+1) - упорядоченность по возрастанию; p(i)>= p(i+1) упорядоченность по убыванию. p(1) p(2) p(i) … p(M) 1 2 i M …. Номера записей ключ

Изображение слайда
9

Слайд 9: Анализ алгоритмов и структур данных

Алгоритмы обработки данных Формирование данных Сортировка (упорядочение по значению ключевых атрибутов) Поиск и корректировка Последовательная обработка. Критерии эффективности алгоритмов: Время формирования данных, Время поиска данных ( используется поиск по совпадению – нахождение записей, значения ключевого атрибута которых равно заранее известной величине q). Время корректировки данных (включение или исключение одной записи) Объем дополнительной памяти, расходуемой под служебную информацию (например, на адреса связи).

Изображение слайда
10

Слайд 10: Анализ алгоритмов и структур данных

Допущения при анализе алгоритмов обработки данных Равномерное распределение значений ключевых атрибутов в массиве из М записей, Значение q при поиске по совпадению выбрано случайно (поиск с одинаковой вероятностью 1\ М может закончится на любой записи массива) Положение включаемой (исключаемой) записи при корректировке определяется теми же вероятностями, что при поиске. Минимальное количество сравнений C записей для упорядочения массива: C ~ M ×log 2 M Время сортировки данных: Т ~ M ×log 2 M

Изображение слайда
11

Слайд 11: Анализ алгоритмов и структур данных

Поиск в последовательном массиве. Условие – совпадение: т. е. p(i) = q Базовый метод – ступенчатый поиск. Разделяется на одноступенчатый (последовательный) и много ступенчатые. Обычно используют двухступенчатый поиск с выбранным шагом поиска d1 и бинарный поиск. Цепная (списковая) организация данных. - Используется для связи физически разнесенных в памяти данных и логических последовательностей, определяющих порядок их обработки. В списке выделяется собственная информация (содержательные сведения) и ассоциативная информация (адреса связи). Необходим специальный атрибут ( указатель списка ), содержащий начальный адрес. Адрес связи последней записи списка содержит специальное значение « конец списка » (обычно 0).

Изображение слайда
12

Слайд 12: Анализ алгоритмов и структур данных

Варианты списковой организации данных Совместное хранение записей и адресов связи Раздельное хранение записей и адресов связи Указатель списка 1 2 3 4 0 Записи Указатель списка 1 2 3 4 0 Записи Ассоциативная информация 1

Изображение слайда
13

Слайд 13: Анализ алгоритмов и структур данных

Варианты списковой организации данных Двунаправленный список Кольцевой список Указатель прямого направления Указатель обратного направления 1 2 3 4 0 0 Записи 1 2 3 4 Записи Указатель списка

Изображение слайда
14

Слайд 14: Анализ алгоритмов и структур данных

Древовидная организация данных Древовидной организацией данных (деревом) называется множество записей, расположенных по уровнях следующим образом: На первом уровне расположена только одна запись (корень дерева), К любой записи i –того уровня ведет адрес связи только от одной записи уровня i -1. Ранг – количество уровней в дереве. Группа – совокупность записей в дереве, которые адресуются об общей записи ( i -1) –го уровня, Порядок дерева – максимальной число элементов в группе, Звено связи – набор адресов связи, принадлежащих одной записи. Определение. В упорядоченном бинарном дереве значение ключевого атрибута каждой записи должно быть больше, чем значение ключа у любой записи на ее левой ветви, и не меньше, чем ключ любой записи на ее правой ветви. Это определение позволяет различать правые и левые адреса (ветви).

Изображение слайда
15

Слайд 15: Анализ алгоритмов и структур данных

Сравнение методов организации данных Критерии оценки Методы организации данных Лучший метод Последовате-льный цепной Бинарное дерево Время формирования ~ M log 2 M ~ M log 2 M ~ M log 2 M Цепной, бинарное дерево Время поиска ~ log 2 M ~ M ~ log 2 M Последовате-льный, бинарное дерево Время корректировки ~ M ~ M ~ log 2 M бинарное дерево Объем дополнитель-ной памяти 0 ~ M ~ M Последовате-льный

Изображение слайда
16

Слайд 16: Методы ускорения доступа к данным

Достигается: Применением новых методов размещения и поиска информации (специальная расстановка записей, алгоритмы сортировки, вычисление местоположения записи). Созданием массивов вспомогательной информации о хранимых данных (метаданных). Методы рандомизации. Используется адресная функция (рандомизирующая функция или хэш-функция) вида: i = f(p), i – номер (адрес) записи, p – значение ключевого атрибута в записи. Методы ускорения доступа к данным

Изображение слайда
17

Слайд 17: Методы ускорения доступа к данным

Требования к адресной функции: Аналитическое задание и быстрое вычисление. Приближенная переработка произвольно распределенных ключевых атрибутов в равномерно распределенные номера записей. Число записей-синонимов (которые имеют одинаковое значение i для значений р разных записей ) должно составлять не более 10-20 % от общего числа записей. Простейшая адресная функция вида: i = p - а. Пример. Массив с набором значений ключевых атрибутов – 13, 11, 14, 15, 18, 14,16. Организовать размещение в памяти в соответствии с адресной функцией i = p - а Решение. Максимальное значение ключа в массиве р макс равно 18, а минимальное значение р мин – 11. Тогда а = р мин – 1 = 10. необходимый участок памяти для размещения массива равен р макс – а = р макс -р мин + 1= 8 Методы ускорения доступа к данным

Изображение слайда
18

Слайд 18: Методы ускорения доступа к данным

Поэтому первый ключ 13 помещается в (13 -10) = 3 номер, 11 – в (11-10) = 1 номер, и т. д. С помощью адресов связи извлекаются все синонимы. Недостаток: большой объем неиспользуемой памяти, если (р макс – р мин) >>M. Адресная функция вида: i = ОСТ ( p/m), m – целое число. Пример. Массив с набором значений ключевых атрибутов – 17, 9, 4, 25, 21, 20,11. Организовать размещение в памяти в соответствии с адресной функцией i = ОСТ ( p/m), Решение. Так как число записей М=8, выбираем m = 7 (или 19). Выделяется два участка памяти: основная и резервная. Методы ускорения доступа к данным 11 11 13 14 15 16 18 1 2 3 4 5 6 7 8 номера записей Основная память резервная память 14 0 0 0 0

Изображение слайда
19

Слайд 19

Последовательные номера записи, согласно адресной функции, составляют ОСТ (17 /7) = 3 номер, ОСТ (9 /7) = 2 номер, ОСТ (4 /7) = 4 номер и т. д. Если позиция номера занята, то значение ключа помещается в резервную память. Дополнительная информация – массив индексов Разновидности индексов: сплошная индексация (инвертированный массив ключевых атрибутов), Последовательно-индексный массив (с арифметической прогрессией по шагу d>1), Рандомизированный индексный массив (с приближенной арифметической прогрессией). Методы ускорения доступа к данным Основная память Резервная память 0 0 0 0 0 Номера ячеек 1 2 3 4 5 6 14 9 17 4 20 25 21 11

Изображение слайда
20

Слайд 20: Организация данных во внешней памяти ЭВМ

1. Запись на магнитный диск производится файлами. 2. Обмен информацией происходит физическими блоками – секторами (минимально 512 байт). 3. При последовательной обработке информации размер блока выбирается максимальным, при одиночной выборке используются блоки в одну запись. 4. Существуют стандартные методы организации файлов на магнитных дисках: последовательный, индексно-последовательный, индексно-произвольный и прямой. При этом в файле выделяется один ключевой атрибут.

Изображение слайда
21

Слайд 21: Организация данных во внешней памяти ЭВМ

Организация доступа к файлу на диске Последовательный доступ – к концу файла. При индексном виде доступа последовательный файл снабжается индексом. Выделяются три области памяти – первичная, индексная и переполнения. Типичная организация индексно-произвольного доступа соответствует В-дереву. При прямом доступе к файлу используется адресная функция i = p - а. На выбор организации влияет количество записей, обрабатываемых в процессе реализации. Резервная память блока должна составлять 10 -15 % от общей памяти.

Изображение слайда
22

Слайд 22: Организация данных во внешней памяти ЭВМ

Доля выборки – это отношение числа требуемых при выборке записей файла к общему числу записей в файле. Доля выборки Наилучшая организация файлов Первая запись прямая 0…10 % Прямая, индексная 10…100 % последовательная

Изображение слайда
23

Слайд 23: Организация данных во внешней памяти ЭВМ

Формула для расчета числа блоков (по технической документации СУБД): S = M ×L / B, S – число блоков, M – число записей, L – длина записей в байтах, B – размер блока в байтах. Используется оптимальное вторичное индексирование.

Изображение слайда
24

Последний слайд презентации: Методы организации данных и ЭИС: ВЫВОДЫ

Рассмотренные вопросы 1.Анализ алгоритмов и структур данных. 2.Методы ускорения доступа к данным. 3.Организация данных во внешней памяти ЭВМ. Практические работы Построение структур размещения данных. Построение алгоритмов поиска и доступа к данным.

Изображение слайда