Ковалевич И.А. Основы баз данных: учебное пособие

Подождите немного. Документ загружается.

— служебная информация, поддерживаемая для удовлетворения

внутренних потребностей нижнего уровня системы (например,

информация о свободной памяти).

6.4.1. ХРАНЕНИЕ ОТНОШЕНИЙ

Существуют два принципиальных подхода к физическому хранению

отношений. Наиболее распространенным является покортежное хранение

отношений (кортеж является единицей физического хранения). Естественно,

это обеспечивает быстрый доступ к целому кортежу, но при этом во

внешней памяти дублируются общие значения разных кортежей одного

отношения и, вообще говоря, могут потребоваться лишние обмены с

внешней памятью, если нужна часть кортежа.

Альтернативным (менее распространенным) подходом является

хранение отношения по столбцам, т.е. единицей хранения является столбец

отношения с исключенными дубликатами. Естественно, что при такой

организации суммарно в среднем тратится меньше внешней памяти,

поскольку дубликаты значений не хранятся; за один обмен с внешней

памятью в общем случае считывается больше полезной информации.

Дополнительным преимуществом является возможность использования

значений столбца отношения для оптимизации выполнения операций

соединения. Но при этом требуются существенные дополнительные

действия для сборки целого кортежа (или его части).

Поскольку гораздо более распространено хранение по строкам, мы

рассмотрим немного более подробно этот способ хранения отношений. К

основным характеристикам этой организации можно отнести следующие:

— Каждый кортеж обладает уникальным идентификатором (tid), не

изменяемым во все время существования кортежа.

размерами страницы. Возникает вопрос: как быть с "длинными"

данными, которые в принципе не помещаются в одной странице?

Применяются несколько методов. Наиболее простым решением является

хранение таких данных в отдельных (вне базы данных) файлах с заменой

"длинного" данного в кортеже на имя соответствующего файла. В

некоторых системах такие данные хранятся в отдельном наборе страниц

внешней памяти, связанном физическими ссылками. Оба эти решения

сильно ограничивают возможность работы с длинными данными (как,

например, удалить несколько байтов из середины 2-мегабайтной

строки?). В настоящее время все чаще используется метод,

предложенный несколько лет тому назад в проекте Exodus, когда

"длинные" данные организуются в виде B-деревьев последовательностей

байтов.

— Как правило, в одной странице данных хранятся кортежи только одного

отношения. Существуют, однако, варианты с возможностью хранения в

одной странице кортежей нескольких отношений. Это вызывает

некоторые дополнительные расходы по части служебной информации

(при каждом кортеже нужно хранить информацию о соответствующем

отношении), но зато иногда позволяет резко сократить число обменов с

внешней памятью при выполнении соединений.

— Изменение схемы хранимого отношения с добавлением нового столбца

не вызывает потребности в физической реорганизации отношения.

Достаточно лишь изменить информацию в описателе отношения и

расширять кортежи только при занесении информации в новый столбец.

— Проблема распределения памяти в страницах данных связана с

проблемами синхронизации и журнализации и не всегда тривиальна.

Например, если в ходе выполнения транзакции некоторая страница

данных опустошается, то ее нельзя перевести в статус свободных

страниц до конца транзакции, поскольку при откате транзакции

удаленные при прямом выполнении транзакции и восстановленные при

ее откате кортежи должны получить те же самые идентификаторы.

— Распространенным способом повышения эффективности СУБД является

кластеризация отношения по значениям одного или нескольких

столбцов. Полезным для оптимизации соединений является совместная

кластеризация нескольких отношений.

С целью использования возможностей распараллеливания обменов с

внешней памятью иногда применяют схему декластеризованного хранения

отношений: кортежи с общим значением столбца декластеризации

размещают на разных дисковых устройствах, обмены с которыми можно

выполнять в параллель.

Что же касается хранения отношения по столбцам, то основная идея

состоит в совместном хранении всех значений одного (или нескольких)

столбцов. Для каждого кортежа отношения хранится кортеж той же степени,

состоящий из ссылок на места расположения соответствующих значений

столбцов. Хранение отношения по столбцам в некотором смысле является

предельным случаем вертикального разделения отношений.

6.4.2.ЖУРНАЛЬНАЯ ИНФОРМАЦИЯ

Структура журнала обычно является сугубо частным делом

конкретной реализации. Мы отметим только самые общие свойства.

Журнал обычно представляет собой чисто последовательный файл с

записями переменного размера, которые можно просматривать в прямом

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

(страницами) с использованием буфера оперативной памяти. В грамотно

организованных системах структура (и тем более, смысл) журнальных

записей известна только компонентам СУБД, ответственным за

журнализацию и восстановление. Поскольку содержимое журнала является

критичным при восстановлении базы данных после сбоев, к ведению файла

журнала предъявляются особые требования по части надежности. В

частности, обычно стремятся поддерживать две идентичные копии журнала

на разных устройствах внешней памяти.

6.4.3.СЛУЖЕБНАЯ ИНФОРМАЦИЯ

Для корректной работы подсистемы управления данными во

внешней памяти необходимо поддерживать информацию, которая

используется только этой подсистемой и не видна подсистеме языкового

уровня. Набор структур служебной информации зависит от общей

организации системы, но обычно требуется поддержание следующих

служебных данных:

— Внутренние каталоги, описывающие физические свойства объектов базы

данных, например, число атрибутов отношения, их размер и, возможно,

типы данных; описание индексов, определенных для данного отношения

и т.д.

— Описатели свободной и занятой памяти в страницах отношения. Такая

информация требуется для нахождения свободного места при занесении

кортежа. Отдельно приходится решать задачу поиска свободного места в

случаях некластеризованных и кластеризованных отношений (в

последнем случае приходится дополнительно использовать

кластеризованный индекс). Как мы уже отмечали, нетривиальной

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

— Связывание страниц одного отношения. Если в одном файле внешней

памяти могут располагаться страницы нескольких отношений (обычно к

этому стремятся), то нужно каким-то образом связать страницы одного

отношения. Тривиальный способ использования прямых ссылок между

страницами часто приводит к затруднениями при синхронизации

транзакций (например, особенно трудно освобождать и заводить новые

страницы отношения). Поэтому стараются использовать косвенное

связывание страниц с использованием служебных индексов. В частности,

известен общий механизм для описания свободной памяти и связывания

страниц на основе B-деревьев.

ПРИЛОЖЕНИЯ.

ПРИЛОЖЕНИЕ А. Словарь терминов.

CASEd(Computer-AideddSoftwaredEngineering)—

автоматизированная разработка программного обеспечения. Среда

разработки программного обеспечения, ориентированная на автоматизацию

всех стадий разработки программ, начиная с планирования и моделирования

и кончая кодированием и документированием. Среда CASE состоит из

программ и других инструментальных средств разработки, позволяющих

администраторам, системным аналитикам, программистам

автоматизировать процесс разработки и внедрения программ и процедур в

компьютерные системы.

ERDd(Entity-relationshipYdiagram)—диаграмма элемент-связь. Метод

создания схем моделей данных, разработанный Питером Ченом в 1976 г. E-

R схемы предназначены для наглядного представления между объектами и

поведения элементов.

ISO—International Standards Organization, Международная

организация по стандартизации.

NOTY(логическое отрицание)—логическая связка только с одним

операндом. Будучи выполненной над высказыванием, значением или

формулой P, эта операция дает значение «ложь» (F), если P принимает

значение «истина» (T) и наоборот, т. е. результат P отрицается.

XORY(исключающее или)—логическая связка объединяющая два

утверждения, два значения истинности или две формулы P и Q таким

образом, что результат является истинным (T), если P или Q (но не P и Q)

истинны. В связи с тем, что истинность результата имеет место только при

неодинаковых операндах, ее называют

такжеYоперациейYотрицанияYэквивалентности.

Y Y P Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y F Y Y Y Y F Y Y Y Y T Y Y Y Y T

Y Y Y Y Q Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y F Y Y Y Y T Y Y Y Y F Y Y Y Y T

Y Y P Y XOR Y Q Y Y Y F Y Y Y Y T Y Y Y Y T Y Y Y Y F

авторизация (полномочия) в компьютерных системах, особенно для

удаленных компьютеров сети, доступных нескольким пользователям:

предоставляемое пользователю право на пользование системой и

хранящимся в ней данными. Обычно полномочия устанавливаются

администратором системы, а проверяются компьютером; при этом

пользователь должен предъявить некий идентификатор (например, кодовый

номер или пароль), который компьютер может проверить по своим

внутренним спискам.

агрегат данных — поименованная группа логически связанных

элементов данных (полей записи базы данных); составной элемент данных.

атрибут — буквально: характеристика. В системах проектирования

баз данных - свойство объекта, характеризующее его экземпляр. В базах

данных имя поля или структура поля считаются атрибутами записи.

базаdданных –

1. Совокупность взаимосвязанных данных, используемых несколькими

приложениямиYподYуправлениемYСУБД.

2. В широком смысле слова – любая совокупность данных; файл, состоящий

из некоторого числа записей (см. запись) или таблиц, каждая из которых

формируется из полей (см. поле) или столбцов определенного типа, вместе с

набором операций поиска, сортировки, и др.

блокировка – запрещение использования файла или записи базы

данных. Блокировка используется в сетях и в других ситуациях, когда

несколько человек могут использовать один и тот же файл или изменять

одну запись в базе данных одновременно. Блокировкой файла или записи

гарантируется раздельное (по времени) изменение данных. Обычно первым

получает доступ тот, кто имеет право делать изменения, другим

пользователям запрещаются какие-либо манипуляции с этими данными,

пока они не будут разблокированы, хотя им может быть разрешено их

просматривать.

буфер – место промежуточного хранения данных: зарезервированная

область памяти, в которой данные хранятся до их перемещения в

запоминающее устройство или из него, либо в другую область памяти.

Некоторые устройства, такие как принтеры или поддерживающие их

адаптеры, обычно имеют свои собственные буферы.

буферизация – процесс использования буфера или буферов для

размещения передаваемых данных, в частности направляемых в устройства

ввода-вывода (например, дисководы, последовательные порты) или из этих

устройств.

внешний ключ – одно или несколько полей таблицы, которые

содержат ссылку на ключевое поле или поля другой таблицы. Внешний

ключ определяет способ связывания таблиц, при котором значения полей

внешнего ключа и ключа должны совпадать. Например, список допустимых

кодов товаров может содержать внешний ключ таблицы товаров, со

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

условий целостности данных в базе данных.

вторичный ключ – в базах данных – элемент или совокупность

элементов, несовпадающие с первичным ключом, которые единственным

способом идентифицируют запись

данные – информация, подготовленная для определенных целей (при

этом часто подразумевается определенный формат). В вычислительной

технике термин имеет триYразличныхYзначения.

Во-первых, данные — как объекты, отличные от команд. Подразумеваются

все обрабатываемые программой операнды, например значения констант и

переменных, или файлы данных (в противоположность программным

файлам). Однако здесь приходится учитывать контекст: например, команды

на исходном языке являются данными для компилятора, а результирующий

объектный код — данными для компонующего загрузчика; когда же

начинается выполнение, тот же самый

объектныйYкодYстановитсяYпрограммой.

Во-вторых, в контексте отдельной программы или пакета программ слово

данные может использоваться в более узком смысле, означая входные

данные в противоположность результатам (выходным данным), как,

например, в случае подготовки и проверки данных. (Результаты,

полученные при выполнении одного процесса, однако, почти всегда

являются данными для следующего процесса.)

В-третьих, когда говорят данные, часто подразумевают (особенно в

последнее время) нечто отличное от текста, речи и изображений.

Аналогичным образом обработка данных противопоставляется обработке

текста, обработке речи и обработке изображений. При таком употреблении

термина подчеркивается высокая форматированность данных в

традиционных приложениях обработки данных в противоположность более

свободным структурам, используемым для представления текста (например,

на естественном языке), при передаче речи или в процессе обработки

визуальных изображений.

декартова структура (кортеж)–структура данных, которой число

элементов фиксировано, а сами элементы линейно упорядочены. Термин

иногда используется в качестве синонима термина запись

детерминант — в теории проектирования баз данных любой атрибут

или комбинация атрибутов, от которого функционально зависит любой

другой атрибут или другая комбинация атрибутов Например, если в базе

данных содержится информация об адресах, то комбинация атрибутов

АДРЕС + ГОРОД + ОБЛАСТЬ является детерминантом значения

ПОЧТОВЫЙ КОД Это значит, что для любого заданного адреса (полностью

определяемого атрибутами АДРЕС, ГОРОД И ОБЛАСТЬ) может

существовать один и только один ПОЧТОВЫЙ КОД Атрибут ПОЧТОВЫЙ

КОД функционально зависит от комбинации АДРЕС + ГОРОД + ОБЛАСТЬ

Аналогично в картотеке сведений о сотрудниках атрибут НОМЕР

ПАСПОРТА будет, вероятно, детерминантом атрибута ФАМИЛИЯ

Атрибут ФАМИЛИЯ функционально зависит от атрибута НОМЕР

ПАСПОРТА.

дизъюнкция,Yлогическое сложениеY(логическое ИЛИ)—логическая

связка (в языках программирования соответствует оператору OR)

объединяющая два высказывания , два истинностных значения или две

формулы P и Q таким образом, что результат является истинным только

тогда, когда или P, или Q истинны (T). Состояние когда и P, и Q

одновременно истинны и результат тоже истинен, отличает операцию ИЛИ

от операции исключающее ИЛИ.

P Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y F Y Y Y Y F Y Y Y Y T Y Y Y Y T

Q Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y F Y Y Y Y T Y Y Y Y Y F Y Y Y T

P Y  Y Q Y Y Y Y Y Y Y Y Y Y Y F Y Y Y Y T Y Y Y Y T Y Y Y Y T

домен — 1. в системах проектирования и управления базами данных

множество допустимых значений данного атрибута. Например, доменам