8 февраля [Лекции]

Понятие о физической организации базы данных. Физическая схема БД. Индексы. Представления.

В отличие от логических моделей баз данных, не ограниченных никакими программно-аппаратными рамками и представляющих логическую структуру данных описываемой предметной области, физические модели баз данных определяют способы размещения этих данных в среде хранения и способы доступа к этим данным, поддерживаемым на физическом уровне. Физическая модель отражает все свойства (атрибуты) информационных объектов базы и связи между ними с учетом способа их хранения используемой СУБД.

Исторически первыми средствами хранения и доступа к данным стали файловые структуры и системы управления файлами (СУФ), которые фактически являлись частью операционной системы. В свою очередь система управления базами данных (СУБД) создавала над этими файловыми моделями свою настройку, позволяющую организовать совокупность файлов таким образом, чтобы она работала как единое целое и имела централизованное управление от СУБД. При этом непосредственный доступ к данным осуществлялся на уровне файловых команд. Однако, механизмы буферизации и управления файловыми структурами оказался не приспособленным для решения специальных задач СУБД, так как они разрабатывались для традиционной обработки файлов, и с ростом объемов хранимых и обрабатываемых данных продемонстрировали свою неэффективность.

В результате постепенно произошел переход от базовых файловых структур к непосредственному управлению размещением хранимых данных на физических носителях. Но многие механизмы, применяемые в файловых системах, перешли и в новые системы организации данных, которые называют страничными, поэтому знать файлы и файловые структуры, используемые для организации физических моделей, применяемых в базах данных, полезно и сейчас.

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

Зная длину записи файла прямого доступа и ее номер, легко быстро найти нужную позицию в файле. Для файлов последовательного доступа применяются другие механизмы позиционирования: указание специальным образом конца записи или указание в начале записи ее длины.

Как уже говорилось, файлы прямого доступа обеспечивают самый быстрый доступ, однако такая схема неэффективна в случае баз данных. Чаще всего известен первичный ключ записи, а не ее номер. Иногда удается построить функцию, однозначно связывающую номер записи и значение первичного ключа. Но в подавляющем большинстве случаев приходится использовать другие механизмы. В этом случае применяют метод хэширования, суть которого заключается в следующем. Строится специальная хэш-функция, значение которой зависит от первичного ключа и определяет начальную точку поиска. Но и здесь есть свой «подводный камень» - хэш-функция не является однозначной, поэтому возможна ситуация, когда для разных ключей будет получено одно и то же значение функции. Такие ситуации называют коллизиями, а первичные ключи в этом случае называются синонимами.

Одним из способов разрешения коллизий является использование области переполнения. Область хранения условно разделяют на две части: основную область и область переполнения. Для каждой новой записи вычисляется значение хэш-функции, которое определяет ее адрес расположении. Если такое значение не было еще получено, то запись заносится в основную область. Если же значение совпадает с одним из полученных ранее, то запись заносится в область переполнения на первое свободное место, а в записи-синониме в основной области делается ссылка на адрес новой записи в области переполнения. Если же ссылка в записе-синониме уже существует, то новая запись получает дополнительную информацию в виде ссылки и уже в таком виде заносится в область переполнения. При этом цепочка синонимов не разрывается, но и не просматривается до конца. Новый синоним всегда заносится на второе место, что сокращает время размещения записи.

Несмотря на высокую эффективность метода хэширования, не всегда удается найти подходящую хэш-функцию, поэтому для организации доступа по первичному ключу часто используют индексные файлы.

Индексные файлы можно представить как файл, разделенный на две части. Физическое совмещение этих частей в одном файле необязательно, часто индексная область образует индексный файл, а основная область – файл, для которого создается индекс. Различают два основных типа файлов: с плотным индексом (индексно-прямые файлы) и с неплотным индексом (индексно-последовательные).

Файлы с плотным индексом структура индексной записи состоит из значения ключа и номера записи. Значение ключа содержит значение первичного ключа, а номер записи – номер записи в основной области с соответствующим первичным ключом. Все записи в индексной области упорядочены по значению ключа. Поиск необходимой записи происходит в два этапа: сначала в упорядоченной индексной области ищется номер записи (максимальное число шагов поиска t = log_2 n, где n – число записей), а затем по найденному номеру записи производится чтение.

Неплотный индекс строится для упорядоченных файлов. Для этих файлов используется принцип внутреннего упорядочения для уменьшения количества хранимых индексов. В этом случае запись в индексном файле будет состоять из двух частей: значении первичного ключа первой записи в блоке и номер блока с этой записью (все данные хранятся на внешних носителях в блоках, размеры которых определяются особенностями носителя и операционной системы). В индексной области теперь производится поиск нужного блока по значению первичного ключа. А так как записи упорядочены, то значение первой записи блока позволяет легко определить блок, в котором находится искомая запись. Остальные действия происходят уже в основной области.

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

Представлением (View) называется SQL запрос на выборку сведений из базы данных, который пользователь воспринимает как некоторое виртуальное отношение. Представления позволяют скрыть ненужные детали для разных пользователей, модифицировать структуры в удобном виде и разграничить доступ к различным сведениям.

Оператор создания представления имеет следующий синтаксис:

CREATE VIEW имя_представления

[(список_столбцов)] AS SQL_запрос

Различают несколько основных видов представлений. Горизонтальное представление используется для ограничении реального объема данных, в этом случае в качестве SQL-запроса используется операция горизонтальной фильтрации.

Например, отображать только преподавателей факультета информационных технологий можно с помощью следующего представления:

CREATE VIEW professors_it

AS SELECT * FROM professors WHERE faculty=’Информационные технологии’

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

Например, для отображения только имен студентов можно создать следующее представление:

CREATE VIEW students_names

AS SELECT last_name, first_name, mid_name FROM students

Сгруппированные представления содержат запросы, имеющие группировку. Эти представления должны обязательно содержать список столбцов и могут использовать агрегированные функции в качестве результирующих столбцов.

Например, для отображения числа студентов в группах можно создать следующее представление:

CREATE VIEW groups_count

group_num, count(*)

AS SELECT group_num, count(*) FROM students

GROUP BY group_num

Объединенные представления базируются на многотабличных запросах и позволяют упростить разработку пользовательского интерфейса, сохранив при этом корректность базы данных. Примером такого представления может служить список студентов с указанием их задолженностей:

CREATE VIEW students_debts

last_name, first_name, mid_name, group_num, subject

AS

SELECT last_name, first_name, mid_name, group_num, subject FROM students, debts

WHERE debts.student_id = students.id

8 февраля [Лекции]

Основные и производные операции, выражение производных операций через основные

v

8 февраля [Лекции]

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

r

8 февраля [Лекции]

Введение

Как уже говорилось ранее, множество отношений с 8 предложенными Э. Ф. Коддом операциями образует алгебру. Множество отношений в алгебре называется основным множеством.

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

Все 8 операций можно условно разделить на 2 группы. В первую группу войдут 4 теоретико-множественные операции, во вторую – 4 специальные операции. Из четырех теоретико-множественных операций первые три – объединение, пересечение и вычитание – привычные теоретико-множественные операции, четвертая – расширенное декартово произведение отношений.

12 января [Статьи]

"Требования к системам интерактивного контроля знаний, предназначенным для использования в традиционных учебных заведениях" - лучший секционный доклад 8 научно-практической конференции "Современные информационные технологии в управлении и образовании"

9 декабря 2008 г. на территории ФГУП НИИ «Восход» прошла традиционная 8-ая научно-практическая конференция "Современные информационные технологии в управлении и образовании: новая волна", организаторами которой стали НИИ «Восход» и МИРЭА. Конференция была проведена в рамках мероприятий, посвященных 25-летнему юбилею базовой кафедры МИРЭА при НИИ «Восход». На конференции было заслушано самое большое количество докладов за всю историю Конференции - около 70. Выступления были посвящены решению актуальных научно-технических проблем, отражающих новые практические решения в двух основных направлениях. Одно из них относится к разработке крупных информационных систем, являющейся основным видам деятельности ФГУП НИИ «Восход». Этому направлению была посвящена работа 1 секции конференции, на которую было представлено 25 докладов ведущих специалистов ФГУП НИИ «Восход», НИИАА, ЦИТиС, МИРЭА, МЭСИ и ряда других организаций. Работа 2 и 3 секций была направлена на рассмотрение вопросов использования практических программно-технических решений как в сфере управления, так и в сфере обучения. Было рассмотрено более 30 докладов, в том числе доклады аспирантов и студентов МИРЭА и МЭСИ.