- •«Информационное обеспечение систем управления»
- •1. Общие понятия ио
- •1) Файловые системы (фс)
- •2) Системы, использующие бд
- •1) По размещению:
- •2) По виду модели данных:
- •1) По размещению:
- •2. Жизненный цикл ио, проектирование ио
- •В соответствии с гост 34.601-90 Автоматизированные системы в стадии создания определены следующие стадии создания автоматизированных систем:
- •2) Каскад с возвратом (возможно переопределение требований):
- •3) Итерационная модель:
- •4) Эволюционная модель:
- •Проектирование ис. Основное проектирование данных и по
- •3. Инфологическое проектирование
- •Нотация Чена:
- •Нотация Баркера:
- •Нотация idef1x:
- •Основными элементами er-модели являются:
- •Сущность
- •Атрибут
- •Множественность
- •Обязательность
- •Расширение нотаций
- •Проблемы er-моделирования
- •4. Логические модели данных. Сетевая и иерархическая модели
- •Сетевая модель данных
- •Операции сетевой модели
- •1) Операции с данными:
- •2) Операции со связями:
- •3) Навигация по данным:
- •Иерархическая модель данных
- •5. Реляционная модель данных
- •Операции с реляционными данными
- •1) Унарные операции (операции с одним отношением):
- •2) Операции с двумя однотипными отношениями:
- •3) Операции с разнотипными отношениями:
- •1. Внутренние соединения:
- •Реляционное исчисление
- •6. Нормализация отношений
- •1Нф требует:
- •2Нф требует:
- •7. Даталогическое проектирование
- •Рассмотрим преобразование реляционной логической модели
- •I. Преобразование исходной инфологической модели (им):
- •Преобразования сущностей
- •Преобразования свойств
- •Преобразования связей
- •II. Переход к логической модели:
- •III. Нормализация отношений
- •IV. Дополнительные действия
- •8. Ограничения целостности, виды и реализация
- •1) По области действия.
- •2) По месту реализации.
- •3) По способу реакции на нарушение.
- •4) По моменту выполнения проверки.
- •9. Средства доступа к данным и разработки приложений
- •10. Язык sql
- •1. Основные составляющие языка sql.
- •2. Методы и средства контроля целостности в основном реализованы в create table:
- •3. Операторы модификации данных:
- •4. Выборка:
- •5. Управление доступом:
- •6. Управление транзакциями:
- •11. Создание бд в sql
- •1. Оператор создания схемы бд
- •2. Оператор создания домена
- •3. Оператор создания таблицы
- •4. Оператор фиксации результатов работы с бд
- •12. Выборка данных в sql
- •1) Формирование единой таблицы:
- •2) Ограничение единой таблицы по строкам:
- •3) Отбор выходных столбцов выборки:
- •4) Группирование строк таблицы выборки:
- •5) Ограничение по групповым строкам:
- •6) Объединение выборки:
- •7) Упорядочивание записей выборки:
- •13. Восстановление данных
- •14. Организация многопользовательского доступа
- •15. Защита от несанкционированного доступа
- •2. Защита на уровне субд
- •3. Защита на уровне приложения
- •16. Физическая организация данных в бд
- •1. Последовательная организация.
- •2. Списковое хранение
- •3. Индексная организация
- •4. Хэшированная организация
- •17. Методы поиска в бд
- •1. Последовательный поиск:
- •2. Блочный поиск.
- •3. Бинарный поиск
- •4. Индексный поиск
- •5. Хешированный поиск
5. Хешированный поиск
Этот метод называется еще методом перемешанных таблиц. Он представляет собой расширение метода прямого доступа на случай отсутствия взаимно однозначного соответствия между ключом и адресом записи. Существует адресная функция (хеш-функция), которая по ключу формирует адрес, однако, не исключено, что один и тот же адрес выделится разным ключам.
Быстродействие обеспечивается заменой переборных и поисковых процедур на прямое вычисление местоположения искомой записи по искомому значению ключа. Вычисление содержит три основных шага:
1) преобразование значения ключа в числовое значение (при нечисловом ключе),
2) хэширование, заключающееся в пересчете числового эквивалента ключа в значение рандомизированной переменной с предположительно равномерным законом распределения. Для пересчета используется выбранная хэш-функция, дающая желаемый эффект рандомизации,
3) масштабирование рандомизированной переменной для приведения получаемых значений к выделенному диапазону адресов памяти (определение адресов в памяти).
Проблемой хэшированного поиска является наличие коллизий, выражающееся получением одинаковых значений адреса хранения записи для различающихся значений ключа. Для решения проблемы коллизий приходится принимать дополнительные меры, такие так выделение дополнительных областей памяти для размещения цепочек перекрывающихся записей.
Этот алгоритм прост, но неэффективен по времени при заполнении таблицы более чем наполовину. Кроме того, при неравномерном распределении ключей этот алгоритм приводит к локальным сгущениям записей и увеличению числа коллизий при относительно свободной таблице.
