Списковые структуры (списки).

Под термином «списковая структура» обычно понимается такая организация данных, при которой объекты (данные) связаны в последовательную цепочку посредством указателей. Данное определение подразумевает динамическую природу списка – т.е. не заданное заранее количество и, иногда, тип элементов.

Различают одно- и двунаправленные, одно- и многосвязные списки. Списки легко обобщаются до понятия графа.

Списком называется множество записей, занимающих произвольные участки памяти, последовательность обработки которых задается с помощью адресов связи. Адресом связи некоторой записи называется атрибут, в котором хранится начальный адрес или номер записи, обрабатываемой после этой записи. Обычная последовательность обработки записей в списке определяется возрастанием значений ключа в записях.

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

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

1. Определение адресов связи как начальных адресов записей.

2. Определение адресов связи, как номеров записей.

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

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

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

При формировании упорядоченного списка записей возможны два варианта:

• вновь поступающие записи вставлять так, чтобы не нарушать упорядоченность по ключу;

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

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

Хэш-адресация.

Бинарные деревья, B+деревья и их использование в СУБД. Объектно-ориентированное визуальное проектирование приложений в объектно-ориентированных СУБД. Понятие транзакции. Управление доступом, привилегии.

Хэш-адресация заключается в использовании значения, возвращаемого хэш-функ­цией, в качестве адреса ячейки из некоторого массива данных. Тогда размер масси­ва данных должен соответствовать области значений используемой хэш-функции. Следовательно, в реальном компиляторе область значений хэш-функции никак не должна превышать размер доступного адресного пространства компьютера. Метод организации таблиц идентификаторов, основанный на использовании хэш-адресации, заключается в помещении каждого элемента таблицы в ячейку, адрес которой возвращает хэш-функция, вычисленная для этого элемента. Тогда в иде­альном случае для помещения любого элемента в таблицу идентификаторов достаточно только вычислить его хэш-функцию и обратиться к нужной ячейке массива данных. Для поиска элемента в таблице также необходимо вычислить хэш-функцию для искомого элемента и проверить, не является ли заданная ею ячейка массива пустой (если она не пуста — элемент найден, если пуста — не найден). Первоначально таблица идентификаторов должна быть заполнена информацией, которая позволила бы говорить о том, что все ее ячейки являются пустыми. Этот метод весьма эффективен, поскольку как время размещения элемента в таб­лице, так и время его поиска определяются только временем, затрачиваемым на вычисление хэш-функции, которое в общем случае несопоставимо меньше вре­мени, необходимого для многократных сравнений элементов таблицы. Метод имеет два очевидных недостатка. Первый из них — неэффективное ис­пользование объема памяти под таблицу идентификаторов: размер массива для ее хранения должен соответствовать всей области значений хэш-функции, в то время как реально хранимых в таблице идентификаторов может быть существен­но меньше. Второй недостаток — необходимость соответствующего разумного выбора хэш-функции. Этот недостаток является настолько существенным, что не позволяет непосредственно использовать хэш-адресацию для организации таб­лиц идентификаторов.

Бинарное (двоичное) дерево (binary tree) - это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла.
Бинарное дерево является рекурсивной структурой, поскольку каждое его поддерево само является бинарным деревом и, следовательно, каждый его узел в свою очередь является корнем дерева.
Узел дерева, не имеющий потомков, называется листом.
Схематичное изображение бинарного дерева:

Бинарное дерево может представлять собой пустое множество.

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

B+ дерево — структура данных, представляет собой сбалансированное дерево поиска. Является модификацией B-дерева, истинные значения ключей которого содержатся только в листьях, а во внутренних узлах — ключи-разделители, содержащие диапазон изменения ключей для поддеревьев.

При построении B+ дерева, его временами приходится перестраивать. Это связано с тем, что количество ключей в каждом узле (кроме корня) должно быть от k, до 2k, где k — степень дерева. При попытке вставить в узел (2k+1)-й ключ возникает необходимость разделить этот узел. В качестве ключа-разделителя сформированных ветвей выступает (k+1)-й ключ, который помещается на соседний ярус дерева. Особым же случаем является разделение корня, так как в этом случае увеличивается число ярусов дерева. Особенностью разделения листа B+ дерева является то, что он делится на неравные части. При разделении внутреннего узла или корня возникают узлы с равным числом ключей k. Разделение листа может вызвать «цепную реакцию» деления узлов, заканчивающуюся в корне.

В B+ дереве легко реализуется независимость программы от структуры информационной записи.

Поиск обязательно заканчивается в листе.

Удаление ключа имеет преимущество — удаление всегда происходит из листа.

Другие операции выполняются аналогично B-деревьям.

B+ деревья требуют больше памяти чем B-деревья для представления.

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

Транзакция – набор команд на SQL языке, выполняемых единым блоком, который выполняется по принципу все или ничего.

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

 

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

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

Логически пользователь понимается рассматриваемыми СУБД одинаково, хотя с принципиально различными реализациями этого понятия.

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

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

Методы аутентификации

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

При применении внутренних методов данные аутентификации пользователи являются объектами базы данных и их имена и пароли хранятся в СУБД.

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