- •Понятия «данные», «информация», «база данных», «субд», «банк данных». Классификация субд
- •Функции субд.
- •Архитектура субд: централизованная архитектура, архитектура «файл-сервер»
- •Архитектура субд: архитектура «клиент-сервер», трехзвенная архитектура
- •Уровни представления баз данных
- •Модели данных субд: иерархическая модель
- •Модели данных субд: сетевая модель
- •Модели данных субд: реляционная модель
- •Реляционная модель данных
- •Модели данных субд: постреляционная модель
- •Модели данных. Инфологические модели: семантическая сеть, графовые модели, модель «сущность-связь».
- •«Сущность-связь»
- •Инфологическая модель «Сущность-связь»: сущность, связь, типы связей, атрибут, уникальный идентификатор, полная и неполная идентификация, возможный ключ сущности.
- •Методология проектирования idef1x: зависимые и независимые сущности, степень связи, типы связи, внешние ключи, правила построения диаграмм
- •Реляционная модель данных: классы отношений, типы связей между отношениями
- •Манипулирование реляционными данными: базовые теоретико-множественные операции реляционной алгебры (объединение, разность, пересечение, произведение).
- •Манипулирование реляционными данными: специальные операции реляционной алгебры (селекция, проекция, соединение, деление)
- •Реляционная модель данных: аномалии обновления, нормализация, первая нормальная форма
- •Реляционная модель данных: функциональные зависимости, вторая нормальная форма
- •Реляционная модель данных: третья нормальная форма, алгоритм нормализации
- •Реляционная модель данных: сравнение нормализованных и ненормализованных моделей
- •Целостность реляционных данных: Null-значения, потенциальные ключи, простой ключ, составной ключ, первичный ключ, альтернативный ключ
- •Целостность реляционных данных: целостность сущностей, внешний ключ, целостность внешних ключей
- •Целостность реляционных данных: операции, которые могут нарушить ссылочную целостность
- •Целостность реляционных данных: стратегии поддержания ссылочной целостности.
- •Основы языка sql: синтаксис операторов определения объектов базы данных (create table, alter table, drop table) create table - создать таблицу
- •Определение первичных и альтернативных ключей с помощью оператора alter
- •Операторы drop
- •Основы языка sql: синтаксис операторов манипулирования данными (select, order by, встроенные функции, group by)
- •Сортировка результатов
- •Встроенные функции sql
- •Основы языка sql: чтение данных из нескольких таблиц с применением вложенных запросов
- •Основы языка sql: чтение данных из нескольких таблиц с помощью операции соединения
- •Основы языка sql: средства модификации данных языка sql
- •Представления. Применение представлений. Обновление представлений.
- •Обновление представлений
- •Триггеры. Типы триггеров. Применение.
- •Применения триггеров
- •Хранимые процедуры. Преимущества использования хранимых процедур
- •Преимущества хранимых процедур
- •Большая безопасность и меньший сетевой трафик.
- •Sql можно оптимизировать
- •Совместное использование кода:
- •Физическая организация бд: структура памяти эвм, представление экземпляра логической записи в памяти эвм
- •Структура памяти эвм
- •Представление экземпляра логической записи
- •Физическая организация бд: организация обмена между оперативной и внешней памятью
- •Физическая организация бд: размещение физических записей в виде списковой структуры (реализация операций поиска, чтения, редактирования, удаления и добавления логических записей)
- •Физическая организация бд: использование индексов (реализация операций поиска, чтения, редактирования, удаления и добавления логических записей)
- •Физическая организация бд: использование сбалансированного дерева (реализация операций поиска, чтения, редактирования, удаления и добавления логических записей)
- •Физическая организация бд: использование хеширования (реализация операций поиска, чтения, редактирования, удаления и добавления логических записей)
- •Параллельная обработка данных: необходимость в атомарных транзакциях
- •Параллельная обработка данных: проблема потерянного обновления, проблема несогласованного чтения
- •Блокировка ресурсов. Неявные и явные блокировки. Глубина детализации блокировки. Монопольная и коллективная блокировки
- •Блокировка ресурсов: сериализуемые транзакции
- •Блокировка ресурсов: взаимная блокировка
- •Блокировка ресурсов: оптимистическая и пессимистическая блокировки
- •Блокировка ресурсов: объявление характеристик блокировки
- •Свойства транзакций: атомарность, долговечность, согласованность
- •Свойства транзакций: изолированность транзакции, уровни изоляции
- •Курсор. Типы курсоров
- •Управление параллельной обработкой в ms sql Server
- •Xml как язык разметки. Общие черты и различия html и xml. Разделение между структурой документа, его содержимым и материализацией
- •Описание содержимого xml-документа с помощью dtd.
- •Описание содержимого xml-документа с помощью xml-схемы.
- •Материализация хмl-документов с помощью xslt.
- •Плоские и структурированные xml-схемы. Глобальные элементы
- •Создание хмl-документов на основе информации из базы данных
- •Select...For xml для нескольких таблиц
- •Понятие и архитектура системы поддержки принятия решений
- •Понятие хранилища данных
- •Физические и виртуальные хранилища данных
- •Проблематика построения хранилищ данных
- •Витрины данных
- •Понятие olap. Категории данных в хд. Информационные потоки в хд
- •Категории данных в хд
- •Информационные потоки в хд
- •Структура olap-куба. Иерархия измерений olap-кубов
- •Иерархия измерений olap-кубов
- •Операции, выполняемые над гиперкубом
- •Архитектура olap-систем
- •Слой извлечения, преобразования и загрузки данных
- •Слой хранения данных
- •Слой анализа данных
- •Клиентские и серверные olap-средства
- •Клиентские olap-средства
- •Серверные olap-средства
- •Технические аспекты многомерного хранения данных: molap, holap
- •Технические аспекты многомерного хранения данных: rolap, схема «звезда», схема «снежинка»
- •Основные характеристики системы Notes. Инфраструктура Lotus Domino. Типы клиентов. Основные характеристики системы No
- •Основные характеристики системы Notes [1]:
- •Инфраструктура Lotus Domino
- •Клиенты
- •Структура баз данных Lotus Domino. Типы документов Структура баз данных Lotus Domino
- •Типы документов
- •Механизм репликации в Lotus Domino.
- •Что происходит во время репликации
- •Некоторые соображения по поводу репликации
-
Физическая организация бд: использование хеширования (реализация операций поиска, чтения, редактирования, удаления и добавления логических записей)
Как в любом другом способе организации структур хранения, логические записи группируются в физические записи (блоки) по k штук. Однако в отличие от всех других способов организации структур хранения здесь выбран особенный способ группировки. Определенным образом выбирается так называемая хэш-функция f. Аргументом этой функции является значение x первичного ключа логической записи. Тогда f(x) указывает адрес расположения блока, в котором должна находиться логическая запись со значением ключа x.
Функция f должна, по возможности, равномерно распределять значения x по физическим блокам. Обсуждению возможных хэш-функций посвящено достаточно много литературы, поэтому здесь мы не будем касаться этого вопроса. Можно лишь добавить, что иногда, исходя из специфики множества значений x первичного ключа, можно построить функцию f, удовлетворяющую всем необходимым условиям.
Таким образом, логическая запись таблицы со значением x первичного ключа размещается в блоке внешней памяти по адресу f(x). В этом блоке может находиться не более k записей. Может оказаться, что выбранная функция отображает в один адрес памяти (один блок) более k записей. Возникает так называемая коллизия. Возможным способом разрешения коллизий является использование дополнительной области переполнения следующим образом.
Если очередная запись распределяется с помощью функции хеширования в блок, а он полностью заполнен, то в области переполнения формируется список записей, соответствующих этому блоку, с включением в него указанной записи, а в сам блок заносится указатель – адрес связи на первую запись этого списка. Возможны и другие способы разрешения коллизий.
Рассмотрим реализацию основных операций и дадим оценку числа обращений к ВП при их выполнении.
Поиск записи с заданным значением ключа и чтение. По заданному значению ключа x подсчитывается значение функции f(x). Далее из ВП считывается блок, находящийся по адресу f(x). В ОП внутри этого блока перебором ищется нужная запись. Если записей в блоке нет, то по указателю в блоке (адресу связи) читается первая запись списка переполнения, относящаяся к этому блоку. Далее необходимая запись ищется по этому списку. Число обращений к ВП при этом равно:
-
единице, если запись находится в блоке;
-
единице плюс число записей в соответствующем этому блоку списке области переполнения (как правило, небольшое число).
Модификации записи. Осуществляется поиск и чтение записи, затем в ОП модифицируются поля записи (не являющиеся первичным ключом), запись заносится на свое место. Число обращений к ВП в этом случае на единицу больше, чем при чтении записи. Если модифицируется значение ключа, то занесение записи осуществляется как ввод новой записи (добавление).
Удаление записи. Осуществляется поиск и чтение записи. Если удаляемая запись находилась в блоке основной памяти, на ее место заносится «пустая» запись (или признак «пустой» записи). Если удаляемая запись находилась в списке области переполнения, удаление ее производится по правилам удаления элемента списка. Число обращений к ВП при удалении находится примерно в тех же пределах, что и для предыдущих операций.
Добавление записи. При добавлении записи со значением ключа x подсчитывается адрес соответствующего блока f(x). Блок считывается в ОП. Если в нем есть место, запись заносится в блок, блок записывается в ВП по своему адресу. Если блок заполнен, из него выбирается адрес начала списка записей, переполняющих блок. Далее добавление записи в список производится по правилам добавления элемента в список. Число обращений к ВП при добавлении записей находится примерно в тех же пределах, что и для предыдущих операций.
Таким образом, описанная структура хранения с использованием хеширования является наиболее эффективной (из рассмотренных выше) по критерию минимизации числа обращений к ВП при реализации основных операций.