Базы данных

1. Модели данных

1.1. Информационные модели

1.1.1. Блочные

1.1.2. Матричные

1.1.3. Графовые

1.1.4. Графические

1.2. Методы исследования информационных потоков

1.2.1. Исследование информационного потока на основе его сетевой модели

1.2.2. Графоаналитический метод исследования потоков информации

1.2.3. Метод функционально-операционного анализа

1.2.4. Метод анализа норм выработки решений

1.2.5. Модуль-метод

1.2.6. Метод семиотического анализа

1.2.7. Анализ формулируемой информации

1.2.8. Метод последовательного анализа задач управления

1.2.9. Метод анализа документопотоков с помощью транспортной модели

1.3. Правила формирования наименований

1.3.1. Реквизитов-оснований

1.3.2. Реквизитов-признаков

1.3.3. Показателей

1.3.4. Документов и массивов

1.4. Классификации

1.4.1. Документов и массивов

1.4.2. Реквизитов-признаков

1.4.3. Реквизитов-оснований

2. Базы данных

2.1. Базы данных основанные на инвертированных списках

2.1.1. Структуры данных

2.1.2. Манипулирование данными

2.1.3. Ограничения целостности

2.2. Иерархические базы данных

2.2.1. Иерархические структуры данных

2.2.2. Манипулирование данными

2.2.3. Ограничения целостности

2.3. Сетевые базы данных

2.3.1. Сетевые структуры данных

2.3.2. Манипулирование данными

2.3.3. Ограничения целостности

2.4. Реляционные базы данных

2.4.1. Общие понятия реляционного подхода к организации БД. Основные концепции и термины

2.4.1.1. Элементы теории множеств

2.4.1.1.1. Множества

2.4.1.1.2. Операции над множествами

2.4.1.1.3. Декартово произведение множеств

2.4.1.1.4. Отношение

2.4.1.1.5. Примеры отношений

2.4.1.1.5.1. Бинарные отношения (отношения степени 2)

2.4.1.1.5.2. Отношение эквивалентности

2.4.1.1.5.3. Отношения порядка

2.4.1.1.6. Функциональное отношение

2.4.1.1.7. Еще пример бинарного отношения

2.4.1.1.8. n-арные отношения (отношения степени n)

2.4.1.1.9. Транзитивное замыкание отношений

2.4.2. Базовые понятия реляционной модели данных

2.4.2.1. Общая характеристика реляционной модели данных

2.4.2.2. Типы данных

2.4.2.2.1. Простые типы данных

2.4.2.2.2. Структурированные типы данных

2.4.2.2.3. Ссылочные типы данных

2.4.2.3. Типы данных, используемые в реляционной модели

2.4.2.4. Домены

2.4.2.5. Отношения, атрибуты, кортежи отношения

2.4.2.5.1. Определения и примеры

2.4.2.5.2. Свойства отношений

2.4.2.5.3. Первая нормальная форма

2.4.3. Целостность реляционных данных

2.4.3.1. Null-значения

2.4.3.2. Трехзначная логика (3VL)

2.4.3.3. Потенциальные ключи

2.4.3.4. Целостность сущностей

2.4.3.5. Внешние ключи

2.4.3.6. Целостность внешних ключей

2.4.3.7. Замечания к правилам целостности сущностей и внешних ключей

2.4.3.8. Операции, могущие нарушить ссылочную целостность

2.4.3.8.1. Для родительского отношения

2.4.3.8.2. Для дочернего отношения

2.4.3.9. Стратегии поддержания ссылочной целостности

2.4.3.10. Применение стратегий поддержания ссылочной целостности

2.4.3.10.1. При обновлении кортежа в родительском отношении

2.4.3.10.2. При удалении кортежа в родительском отношении

2.4.3.10.3. При вставке кортежа в дочернее отношение

2.4.3.10.4. При обновлении кортежа в дочернем отношении

2.4.4. Реляционная алгебра.

2.4.4.1. Обзор реляционной алгебры

2.4.4.2. Замкнутость реляционной алгебры

2.4.4.3. Отношения, совместимые по типу

2.4.4.4. Оператор переименования атрибутов

2.4.4.5. Теоретико-множественные операторы

2.4.4.5.1. Объединение

2.4.4.5.2. Пересечение

2.4.4.5.3. Вычитание

2.4.4.5.4. Декартово произведение

2.4.4.6. Специальные реляционные операторы

2.4.4.6.1. Выборка (ограничение, селекция)

2.4.4.6.2. Проекция

2.4.4.6.3. Соединение

2.4.4.6.4. Общая операция соединения

2.4.4.6.5. Тэта-соединение

2.4.4.6.6. Экви-соединение

2.4.4.6.7. Естественное соединение

2.4.4.6.8. Деление

2.4.4.7. Примеры использования реляционных операторов

2.4.4.8. Зависимые реляционные операторы

2.4.4.9. Примитивные реляционные операторы

2.4.4.10. Запросы, невыразимые средствами реляционной алгебры

2.4.4.11. Плохая нормализация отношений

2.4.4.12. Невыразимость транзитивного замыкания реляционными операторами

2.4.4.13. Кросс-таблицы

2.4.5. Проектирование реляционных БД

2.4.5.1. Нормальные формы отношений

2.4.5.1.1. Этапы разработки базы данных

2.4.5.1.2. Критерии оценки качества логической модели данных

2.4.5.1.3. Адекватность базы данных предметной области

2.4.5.1.4. Легкость разработки и сопровождения базы данных

2.4.5.1.5. Скорость операций обновления данных (вставка, обновление, удаление)

2.4.5.1.6. Скорость операций выборки данных

2.4.5.1.7. Основной пример

2.4.5.1.8. 1НФ (Первая Нормальная Форма)

2.4.5.1.9. Аномалии обновления

2.4.5.1.10. Аномалии вставки (INSERT)

2.4.5.1.11. Аномалии обновления (UPDATE)

2.4.5.1.12. Аномалии удаления (DELETE)

2.4.5.1.13. Функциональные зависимости

2.4.5.1.14. Определение функциональной зависимости

2.4.5.1.15. Функциональные зависимости отношений

2.4.5.1.16. 2НФ (Вторая Нормальная Форма)

2.4.5.1.16.1. Анализ декомпозированных отношений

2.4.5.1.16.2. Оставшиеся аномалии вставки (INSERT)

2.4.5.1.16.3. Оставшиеся аномалии обновления (UPDATE)

2.4.5.1.16.4. Оставшиеся аномалии удаления (DELETE)

2.4.5.1.17. 3НФ (Третья Нормальная Форма)

2.4.5.1.18. Алгоритм нормализации (приведение к 3НФ)

2.4.5.1.19. Анализ критериев для нормализованных и ненормализованных моделей данных

2.4.5.1.20. Сравнение нормализованных и ненормализованных моделей

2.4.5.1.21. OLTP и OLAP-системы

2.4.5.1.22. Корректность процедуры нормализации - декомпозиция без потерь. Теорема Хеза

2.4.5.2. Нормальные формы более высоких порядков

2.4.5.2.1. НФБК (Нормальная Форма Бойса-Кодда)

2.4.5.2.2. 4НФ (Четвертая Нормальная Форма)

2.4.5.2.3. 5НФ (Пятая Нормальная Форма)

2.4.5.2.4. Продолжение алгоритма нормализации (приведение к 5НФ)

2.4.5.3. Элементы модели "сущность-связь"

2.4.5.3.1. Основные понятия ER-диаграмм

2.4.5.3.2. Пример разработки простой ER-модели

2.4.5.3.3. Концептуальные и физические ER-модели

2.5. Постреляционные базы данных

2.5.1. Ориентация на расширенную реляционную модель

2.5.2. Абстрактные типы данных

2.5.3. Генерация систем баз данных, ориентированных на приложения

2.5.4. Оптимизация запросов, управляемая правилами

2.5.5. Поддержка исторической информации и темпоральных запросов

2.6. Объектно-ориентированные БД

2.6.1. Связь объектно-ориентированных БД с общими понятиями объектно-ориентированного подхода

2.6.2. Объектно-ориентированные модели данных

2.6.3. Языки программирования объектно-ориентированных баз данных

2.6.3.1. Потеря соответствия между языками программирования и языками запросов в реляционных БД

2.6.3.2. Языки программирования ООБД

2.6.3.3. Примеры языков программирования ООБД

2.6.4. Языки запросов объектно-ориентированных баз данных

2.6.4.1. Явная навигация как следствие преодоления потери соответствия

2.6.4.2. Ненавигационные языки запросов

2.6.4.3. Проблемы оптимизации запросов

2.6.5. Примеры объектно-ориентированных БД

2.6.5.1. Проект ORION

2.6.5.2. Проект O2

2.7. Системы баз данных, основанные на правилах

2.7.1. Экстенсиональная и интенсиональная части базы данных

2.7.2. Активные базы данных

2.7.3. Дедуктивные базы данных

3. Системы управления базами данных (СУБД)

3.1. Организация средств управления реляционными БД

3.1.1. Cтруктуры внешней памяти, методы организации индексов

3.1.1.1. Хранение отношений

3.1.1.2. Индексы

3.1.1.2.1. B-деревья

3.1.1.2.1.1. Классические B-деревья

3.1.1.2.1.2. B+-деревья

3.1.1.2.1.3. Разновидности B+-деревьев для организации индексов в базах данных

3.1.1.2.1.4. R-деревья и их использование в пространственных базах данных

3.1.1.2.2. Хэширование

3.1.1.3. Журнальная информация

3.1.1.4. Служебная информация

3.1.2. Управление транзакциями, сериализация транзакций

3.1.2.1. Транзакции и целостность баз данных

3.1.2.2. Изолированность пользователей

3.1.2.3. Сериализация транзакций

3.1.3. Методы сериализации транзакций

3.1.3.1. Синхронизационные захваты

3.1.3.1.1. Гранулированные синхронизационные захваты

3.1.3.1.2. Предикатные синхронизационные захваты

3.1.3.1.3. Тупики, распознавание и разрушение

3.1.3.2. Метод временных меток

3.1.4. Журнализация изменений БД

3.1.4.1. Журнализация и буферизация

3.1.4.2. Индивидуальный откат транзакции

3.1.4.3. Восстановление после мягкого сбоя

3.1.4.4. Физическая согласованность базы данных

3.1.4.5. Восстановление после жесткого сбоя

3.1.5. Методы оптимизации выполнения запросов в реляционных СУБД

3.1.5.1. Оптимизация запросов

3.1.5.1.1. Путь обработки запроса в реляционной СУБД

3.1.5.1.2. Логическая оптимизация запросов

3.1.5.1.3. Семантическая оптимизация запросов

3.1.5.1.4. Выбор и оценка альтернативных планов выполнения запросов

3.1.5.1.5. Оптимизаторы с гибкой структурой

3.1.5.2. Эффективные алгоритмы выполнения запросов

3.1.5.2.1. Эффективное выполнение операций соединения

3.1.5.2.2. Некоторые частные алгоритмы

3.1.5.3. Оптимизация в распределенных системах управления базами данных

3.1.5.3.1. Особенности оптимизации запросов в распределенных реляционных СУБД

3.1.5.3.2. Стратегии выполнения соединений в распределенных базах данных

3.1.5.4. Глобальные оптимизации в реляционных системах управления базами данных

3.1.5.4.1. Статистическая глобальная оптимизация

3.1.5.4.2. Оптимизация наборов запросов

3.2. SQL – язык управления реляционными базами данных

3.2.1. Язык SQL. Функции и основные возможности

3.2.1.1. SEQUEL/SQL СУБД System R

3.2.1.1.1. Запросы и операторы манипулирования данными

3.2.1.1.2. Операторы определения и манипулирования схемой БД

3.2.1.1.3. Определения ограничений целостности и триггеров

3.2.1.1.4. Представления базы данных

3.2.1.1.5. Определение управляющих структур

3.2.1.1.6. Авторизация доступа к отношениям и их полям

3.2.1.1.7. Точки сохранения и откаты транзакции

3.2.1.1.8. Встроенный SQL

3.2.1.1.9. Динамический SQL

3.2.1.2. Язык SQL в коммерческих реализациях

3.2.1.3. Стандартизация SQL

3.2.2. Стандартный язык баз данных SQL

3.2.2.1. Типы данных

3.2.2.2. Средства определения схемы

3.2.2.2.1. Оператор определения схемы

3.2.2.2.2. Определение таблицы

3.2.2.2.3. Определение столбца

3.2.2.2.4. Определение ограничений целостности таблицы

3.2.2.2.5. Определение представлений

3.2.2.2.6. Определение привилегий

3.2.3. Язык SQL. Средства манипулирования данными

3.2.3.1. Структура запросов

3.2.3.1.1. Спецификация курсора

3.2.3.1.2. Оператор выборки

3.2.3.1.3. Подзапрос

3.2.3.2. Табличное выражение

3.2.3.2.1. Раздел FROM

3.2.3.2.2. Раздел WHERE

3.2.3.2.3. Раздел GROUP BY

3.2.3.2.4. Раздел HAVING

3.2.3.3. Агрегатные функции и результаты запросов

3.2.3.3.1. Семантика агрегатных функций

3.2.3.3.2. Результаты запросов

3.2.4. Использование SQL при прикладном программировании

3.2.4.1. Язык модулей или встроенный SQL?

3.2.4.2. Язык модулей

3.2.4.2.1. Определение процедуры

3.2.4.3. Встроенный SQL

3.2.4.4. Набор операторов манипулирования данными

3.2.4.4.1. Операторы, связанные с курсором

3.2.4.4.2. Одиночные операторы манипулирования данными

3.2.4.5. Динамический SQL в Oracle V.6

3.2.4.5.1. Оператор подготовки

3.2.4.5.2. Оператор получения описания подготовленного оператора

3.2.4.5.3. Оператор выполнения подготовленного оператора

3.2.4.5.4. Работа с динамическими операторами SQL через курсоры

3.2.5. Некоторые черты SQL/92 и SQL-3

3.2.5.1. Оператор выделения памяти под дескриптор

3.2.5.2. Оператор освобождения памяти из-под дескриптора

3.2.5.3. Оператор получения информации из области дескриптора SQL

3.2.5.4. Оператор установки дескриптора

3.2.5.5. Оператор подготовки

3.2.5.6. Оператор отказа от подготовленного оператора

3.2.5.7. Оператор запроса описания подготовленного оператора

3.2.5.8. Оператор выполнения подготовленного оператора

3.2.5.9. Оператор подготовки с немедленным выполнением

3.2.5.10. Оператор объявления курсора над динамически подготовленным оператором выборки

3.2.5.11. Оператор определения курсора над динамически подготовленным оператором выборки

3.2.5.12. Оператор открытия курсора, связанного с динамически подготовленным оператором выборки

3.2.5.13. Оператор чтения строки по курсору

3.2.5.14. Оператор закрытия курсора

3.2.5.15. Оператор позиционного удаления по курсору

3.2.5.16. Оператор позиционной модификации по курсору

3.2.5.17. Подготавливаемый оператор позиционного удаления

3.2.5.18. Подготавливаемый оператор позиционной модификации

3.2.5.19. Сводка новых возможностей SQL-3

3.2.5.19.1. Типы данных

3.2.5.19.2. Некоторые другие свойства SQL-3

3.2.6. Компиляторы SQL. Проблемы оптимизации

3.2.6.1. Общая схема обработки запроса

3.2.6.2. Синтаксическая оптимизация запросов

3.2.6.2.1. Простые логические преобразования запросов

3.2.6.2.2. Преобразования запросов с изменением порядка реляционных операций

3.2.6.2.3. Приведение запросов со вложенными подзапросами к запросам с соединениями

3.2.6.3. Семантическая оптимизация запросов

3.2.6.3.1. Преобразования запросов на основе семантической информации

3.2.6.3.2. Использование семантической информации при оптимизации запросов

3.2.6.4. Выбор и оценка альтернативных планов выполнения запросов

3.2.6.4.1. Генерация планов

3.2.6.4.2. Оценка стоимости плана запроса

3.2.6.4.3. Более точные оценки

3.3. Средства управления Объектными БД

3.3.1. Сравнение возможностей манипуляции объектными и реляционными БД

3.3.1.1. Основные возможности реляционных БД

3.3.1.2. Объектно-реляционные методы

3.3.1.3. Объектно-реляционные адаптеры

3.3.1.4. Объектно-реляционные шлюзы

3.3.1.5. Гибридные СУБД

3.3.2. Положения объектно-ориентировочных СУБД

3.3.2.1. Why ODBMS?

3.3.2.2. Спорные моменты технологии

3.3.2.3. Стандарты объектных СУБД

3.3.2.4. Поставщики ООСУБД

3.4. Распределенные и параллельные СУБД

3.4.1. Основные понятия

3.4.2. Технологии распределенных и параллельных баз данных

3.4.2.1. Вопросы архитектуры

3.4.2.2. Обработка и оптимизация запросов

3.4.2.3. Управление одновременным доступом

3.4.2.4. Протоколы обеспечения надежности

3.4.2.5. Протоколы тиражирования

3.4.3. Исследовательские проблемы

3.4.3.1. Размещение данных

3.4.3.2. Проблемы сетевой масштабируемости

3.4.3.3. Распределенная и параллельная обработка запросов

3.4.3.4. Распределенная обработка транзакций

4. Практические реализации СУБД

4.1. System R: общая организация системы

4.1.1. Организация System R

4.1.1.1. Используемая терминология

4.1.1.2. Основные цели System R и их связь с архитектурой системы

4.1.1.3. Организация внешней памяти в базах данных System R

4.1.1.4. Интерфейс RSS

4.1.1.5. Синхронизация в System R

4.1.1.6. Журнализация и восстановление в System R

4.1.1.7. Трансляция запросов и поддержка времени выполнения

4.1.1.8. Оптимизация в System R

4.1.2. Распределенная система управления базами данных System R*

4.1.2.1. Исходные цели проекта System R*

4.1.2.2. Именование объектов и организация распределенного каталога

4.1.2.3. Распределенная компиляция запросов

4.1.2.4. Особенности оптимизации запросов в System R*

4.1.2.5. Управление транзакциями и синхронизация

4.1.3. Развитие System R для использования в нетрадиционных приложениях

4.1.3.1. Организация сложных объектов в XSQL

4.1.3.2. Расширение модели транзакции в XSQL

4.1.3.3. Управление версиями объектов в XSQL

4.2. Ingres: общая организация системы, основы языка Quel

4.2.1. История СУБД Ingres

4.2.2. Ingres как UNIX-ориентированная СУБД. Динамическая структура системы: набор процессов

4.2.3. Структуры данных, методы доступа, интерфейсы доступа к данным

4.2.4. Общая характеристика языка QUEL. Язык программирования EQUEL

4.2.5. Общий подход к организации представлений, ограничениям целостности и контролю доступа

4.3. Серверы баз данных

4.3.1. Средства и методологии проектирования, разработки и сопровождения файл-серверных приложений

4.3.1.1. Традиционные средства и методологии разработки файл-серверных приложений

4.3.1.1.1. Системы программирования и библиотеки

4.3.1.1.2. Средства и методы разработки приложений на основе СУБД на персональных компьютерах

4.3.1.2. Новые средства разработки файл-серверных приложений

4.3.1.2.1. Общая характеристика современных средств

4.3.1.2.2. Примеры новых подходов

4.3.1.3. Перенос файл-серверных приложений в среду клиент-сервер

4.3.1.3.1. Библиотеки доступа к базам данных

4.3.1.3.2. Протокол ODBC и его реализации

4.3.1.3.3. Укрупнение приложений (Upsigsing)

4.3.1.4. Инструментальные средства разработки файл-серверных приложений

4.3.2. Средства и методологии проектирования, разработки и сопровождения клиент-серверных приложений

4.3.2.1. Базовые средства построения ИС в архитектуре "клиент-сервер"

4.3.2.1.1. Вызовы удаленных процедур

4.3.2.1.2. Стек протоколов TCP/IP как основа RPC

4.3.2.1.3. Развитие идей RPC (пакет ONC+ компании Sun Microsystems)

4.3.2.2. Серверы баз данных в архитектуре "клиент-сервер"

4.3.2.2.1. Понятие сервера баз данных

4.3.2.2.2. Базовая архитектура сервера баз данных

4.3.2.2.3. Основные производители серверов баз данных и характеристика их продуктов

4.3.3. Средства и методологии проектирования, разработки и сопровождения Intranet-приложений

4.3.3.1. Основные понятия Intranet

4.3.3.2. Языки и протоколы

4.3.3.2.1. HTML

4.3.3.2.2. HTTP

4.3.3.3. Серверы Intranet

4.3.3.3.1. FTP-серверы

4.3.3.3.2. WWW-серверы

4.3.3.3.3. Поисковые серверы

4.3.3.4. Язык программирования Java

4.3.3.4.1. Мобильность Java

4.3.3.4.2. Безопасность, Java и Intranet

4.3.3.4.3. Миграция к языку мобильного программирования

4.3.3.5. Возможные архитектуры Intranet-приложений

4.3.3.5.1. Решения, ориентированные на клиентскую часть системы

4.3.3.5.2. Трехзвенные архитектуры (Web-ориентированные)

4.3.3.5.3. Решения, основанные на использовании языка Java

4.3.4. Информационные приложения, основанные на использовании "складов данных" (DataWarehousing)

4.3.4.1. Проблема интеграции данных

4.3.4.2. Подходы и имеющиеся решения

4.3.4.2.1. Компания IBM

4.3.4.2.2. Oracle

4.3.4.2.3. Hewlett Packard

4.3.4.2.4. Sybase

4.3.4.2.5. Informix Software

4.3.4.2.6. AT&T GIS

4.3.4.2.7. SAS Institute

4.3.4.2.8. Software AG

4.3.5. Глобально распределенные информационные системы

4.3.5.1. Проблема "унаследованных систем" (Legacy Systems)

4.3.5.2. Объектный подход

4.3.5.3. Предложения OMG и ODMG

4.3.5.4. Промышленный стандарт CORBA

4.3.6. Проблемы выбора аппаратно-программной платформы и конфигурации сервера базы данных

4.3.6.1. Введение

4.3.6.2. Проблемы оценки конфигурации системы

4.3.6.3. Основы конфигурирования серверов баз данных

4.3.6.3.1. Характеристики рабочей нагрузки (тесты TPC)

4.3.6.3.1.1. Что такое TPC

4.3.6.3.2. Выбор конфигурации сервера СУБД

4.3.6.3.2.1. Предпосылки выбора

4.3.6.3.2.2. Выбор вычислительной модели

4.3.6.3.2.3. Мониторы обработки транзакций

4.3.6.3.2.3.1. Гибкость доступа к данным

4.3.6.3.2.3.2. Вопросы производительности

4.3.6.3.2.4. Подсистема основной памяти

4.3.6.3.2.4.1. Выбор размера буфера ввода/вывода СУБД

4.3.6.3.2.4.2. Дополнительные требования к памяти

4.3.6.3.2.5. Процессоры

4.3.6.3.2.6. Дисковые подсистемы ввода/вывода

4.3.6.3.2.6.1. Соотношение запрос/индекс/диск

4.3.6.3.2.6.2. Емкость и пропускная способность дисковой памяти

4.3.6.3.2.6.3. Файловые системы по сравнению с "чистыми" (неструктурированными) дисками

4.3.6.3.2.6.4. Метаданные СУБД

4.3.6.3.2.6.5. Распределение данных

4.3.6.3.2.6.6. Использование ресурсов ввода/вывода

4.3.6.3.2.7. Сетевая подсистема ввода/вывода

4.3.6.3.2.7.1. Соображения по использованию режима клиент/сервер

4.3.6.3.2.7.2. Большие объекты данных

4.3.6.3.2.7.3. Конфигурация клиент/сервер и региональные сети

4.3.6.3.2.7.4. Трафик символьного терминала

4.3.6.3.2.7.5. Заключительные рекомендации по конфигурированию сетевого ввода/вывода

4.3.6.3.2.8. PrestoServe/NVSIMM

4.3.6.3.2.9. Обеспечение резервного копирования

4.3.6.3.2.9.1. Когда необходимо выполнять резервное копирование?

4.3.6.3.2.9.2. Резервное копирование в режиме online

4.3.6.3.2.9.3. Продолжительность резервного копирования

4.3.6.3.2.9.4. Использование зеркалирования дисков для облегчения резервного копирования

4.3.6.3.2.9.5. Частота резервного копирования

4.3.6.3.2.9.6. Утилиты резервного копирования

4.3.6.3.2.9.7. Отслеживание и проверка резервных копий

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

4.3.6.3.3.1. Пример 1

4.3.6.3.3.2. Пример 2

4.3.6.3.3.3. Предостережения