1. Слабоструктурированные данные
В современных программных системах используются различные аппараты для обработки и хранения данных. Модели данных и средства хранения, основанные на них, выбираются исходя из специфики самих данных. Основные модели данных на сегодняшний день – реляционная, иерархическая и сетевая. При выборе оптимальной модели и средства хранения для конкретной задачи нужно опираться на особенности области данных и характеристики алгоритмов разработки, соотнося их с возможностями аппарата.Модель данных – теория представления и обработки данных в системе управления данными (хранилище данных), включающая три аспекта:
· аспект структуры: методы описания типов и логических структур данных в базе данных;
· аспект манипуляции: методы манипулирования данными;
· аспект целостности: методы описания и поддержки целостности базы данных.
Аспект структуры определяет, что из себя логически представляет хранилище данных, аспект целостности определяет средства описаний корректных состояний хранилища данных, аспект манипуляции определяет способы перехода между состояниями хранилища данных (т.е. способы модификации данных) и способы извлечения данных из хранилища.
В математике принято называть типами (или, иначе, сортами) относительно устойчивые и независимые совокупности элементов, которые можно выделить во всем рассматриваемом множестве (предметной области). При этом разделение элементов предметной области на типы или сорта во многом является условным и носит субъективный характер, так как зависит от эксперта в этой области.
Тип, подобно множеству, может определяться двояко. Во-первых, возможно определение типа посредством явного перечисления всех элементов, принадлежащих типу (такой подход применяется и в математике, и в программировании, где существуют так называемые перечислимые типы). Другим способом определения типа T является формализация общих свойств тех элементов d из предметной области D, которые объединяются в этот тип, посредством задания индивидуализирующей предикатной функции Ψ, значение которой истинно, если элемент принадлежит данному типу и ложно в противном случае:
T = {d: D|Ψ}
Слабоструктурированными называются данные, обладающие определенной структурой, но эта структура может оказаться непостоянной, недостаточно изученной или неполной. Как правило, такие данные не могут быть описаны с помощью какой-либо неизменной схемы, поэтому иногда их называют не имеющими схемы или описывающими сами себя. Характерной особенностью слабоструктурированных данных является то, что описательная информация, которая обычно выделяется в отдельную схему, присутствует в самих данных. В некоторых формах представления слабоструктурированных данных не предусмотрено применение отдельной схемы, а в других она существует, но налагает на представленные в ней данные очень слабые ограничения.
Можно выделить следующие ключевые положения, характеризующие особенности слабоструктурированных данных:
· Не существует фиксированной структуры данных
· Нет четкого различия между собственно данными и их структурой
· Отсутствует строгая типизация
· Изменение структуры данных является рутинной операцией, сравнимой с внесением изменений в данные
· Объем данных сравним с количеством типов в структуре данных
· Структура данных является описывающей, а не предписывающей, и может быть получена из самих данных
· Полное знание структуры данных не является необходимым для построения запросов, возможны запросы, полностью игнорирующие структуру данных
С точки зрения типизации это означает, что количество элементов d:D сравнимо с количеством T, причем в процессе изменения данных могут изменяться как значения, так и структура, то есть T становится функцией времени T(t), как и d(t):
T(t) = {d(t): D|Ψ},
где число уникальных T(t) эквивалентно числу уникальных d(t).
В последнее время обнаруживается значительный интерес к слабоструктурированным данным по многим причинам. Наиболее важные из них перечислены ниже:
· Для дальнейшей автоматизации обработки информации необходимо иметь возможность обращаться к различным источникам данных, как к базам данных, но на эти источники невозможно наложить какую-либо заранее заданную схему.
· Количество разнотипных баз данных постоянно возрастает, поэтому задача создания гибкого формата, обеспечивающего обмен данными между базами различных типов, становится все более важной.
· В связи со становлением языка XML как стандарта представления и обмена данными между приложениями появились перспективы создания новых методов обработки слабоструктурированных данных, поскольку язык XML хорошо подходит для их описания.
Далее рассмотрим модели данных с точки зрения их применимости для работы со слабоструктурированных данными.
2 Модели хранения данных
2.1 Реляционная модель данных
Реляционная модель данных (РМД) – модель данных, основывающаяся на отношениях (relation) и описывающая три аспекта применительно к реляционным базам данных.· Структурный аспект – данные в базе данных представляют собой набор отношений.
· Аспект целостности – отношения (таблицы) отвечают определенным условиям целостности. РМД поддерживает декларативные ограничения целостности уровня домена (типа данных), уровня отношения и уровня базы данных.
· Аспект манипулирования (обработки) – РМД поддерживает операторы манипулирования отношениями (реляционная алгебра).
Для лучшего понимания РМД следует отметить три важных обстоятельства:
· модель является логической, то есть отношения являются логическими, а не физическими (хранимыми) структурами;
· всё информационное наполнение базы данных представлено одним и только одним способом, а именно – явным заданием значений атрибутов в кортежах отношений; в частности, нет никаких указателей (адресов), связывающих одно значение с другим;
· наличие реляционной алгебры позволяет реализовать декларативное программирование и декларативное описаний ограничений целостности, в дополнение к навигационному (процедурному) программированию и процедурной проверке условий.
РМД характеризуется простотой структуры данных, удобным для пользователя табличным представлением и возможностью использования формального аппарата алгебры отношений и реляционного исчисления для обработки данных.
Реляционная модель ориентирована на организацию данных в виде таблиц. Каждая реляционная таблица представляет собой двумерный массив строк и столбцов и обладает следующими свойствами:
· каждая строка таблицы – один элемент данных (кортеж)
· все ячейки в столбце таблицы однородные, то есть все элементы в столбце имеют одинаковый тип (числовой, символьный и т. д.)
· каждый столбец имеет уникальное имя
· одинаковые строки в таблице отсутствуют
· порядок следования строк и столбцов может быть произвольным
Недостатки реляционной модели с точки зрения применимости аппарата для хранения слабоструктурированных данных:
· Реляционная модель данных не допускает естественного представления данных со сложной иерархической структурой, поскольку в ее рамках возможно моделирование лишь с помощью плоских отношений (таблиц). Все отношения принадлежат одному уровню, многие значимые связи между данными либо теряются, либо их поддержку приходится осуществлять в рамках конкретной прикладной программы в области данных со своей реализацией задач хранения.
· По определению в реляционной модели поля кортежа могут содержать лишь атомарные значения. Однако, во многих приложениях, таких как системы автоматизированного проектирования, геоинформационные системы, пользователи оперируют со сложноструктурированными объектами. Например, необходимо создать базу данных земельных участков. Каждый участок задается координатами узлов ломаной линии, ограничивающей его по периметру. В этом случае весьма затруднительно спроектировать реляционную таблицу, так как заранее неизвестно количество узлов для всех участков. Также трудность представляет написание общих процедур (вычисление площади, нахождение пересечения и так далее) для всех случаев. Кроме того, даже в том случае, когда сложный объект удается "уложить" в реляционную базу данных, его данные распределяются, как правило, по многим таблицам. Соответственно, извлечение каждого такого объекта требует выполнения многих операций соединения (JOIN), что значительно замедляет работу СУБД. Обойти это и предыдущее ограничения можно было бы в том случае, если бы реляционная модель допускала:
o возможность определения новых неатомарных типов данных
o определение наборов операций, связанных с данными определенного неатомарного типа
o ссылки
2.2 Иерархическая модель данных
Иерархическая модель данных (ИМД) – модель представления данных в виде древовидной структуры.
Рис. 1. Пример иерархической структуры.
ИМД представляет собой совокупность элементов, расположенных в порядке их подчинения от общего к частному и образующих перевернутое дерево (граф). Данная модель характеризуется такими параметрами, как уровни, узлы, связи. Узел – информационная модель элемента, представляющего собой объект и находящегося на данном уровне иерархии. Между объектами в ИМД существуют связи, каждый объект может включать в себя несколько объектов более низкого уровня. Такие объекты находятся в отношении предка (объект более близкий к корню) к потомку (объект более низкого уровня), при этом возможно, когда объект-предок не имеет потомков или имеет их несколько, тогда как у объекта-потомка обязательно только один предок. Объекты, имеющие общего предка, называются близнецами.
Организация данных в СУБД иерархического типа определяется в терминах: элемент, агрегат, запись (группа), групповое отношение, база данных.
· Атрибут (элемент данных) – наименьшая единица структуры данных. Обычно каждому элементу при описании базы данных присваивается уникальное имя. По этому имени к нему обращаются при обработке. Элемент данных также часто называют полем.
· Запись - именованная совокупность атрибутов. Использование записей позволяет за одно обращение к базе получить некоторую логически связанную совокупность данных. Именно записи изменяются, добавляются и удаляются. Тип записи определяется составом ее атрибутов. Экземпляр записи – конкретная запись с конкретным значением элементов
· Групповое отношение – иерархическое отношение между записями двух типов. Родительская запись (владелец группового отношения) называется исходной записью, а дочерние записи (члены группового отношения) – подчиненными. Иерархическая база данных может хранить только такие древовидные структуры.
В иерархической модели данных вершине графа соответствует тип записи или просто запись, а дугам – типы связей предок-потомок. В иерархических структурах запись-потомок должен иметь в точности одного предка. Иерархическая модель представляет собой связный неориентированный граф древовидной структуры, объединяющий записи. Иерархическая база данных состоит из упорядоченного набора деревьев.
Корневая запись каждого дерева обязательно должна содержать ключ с уникальным значением. Ключи некорневых записей должны иметь уникальное значение только в рамках группового отношения. Каждая запись идентифицируется полным сцепленным ключом, под которым понимается совокупность ключей всех записей от корневой вниз по иерархическому пути.
Преобразование концептуальной модели в иерархическую структуру данных во многом схоже с преобразованием ее в сетевую модель (см. п. 1.4), но и имеет некоторые отличия в связи с тем, что иерархическая модель требует организации всех данных в виде дерева. Преобразование связи типа "один ко многим" между предком и потомком осуществляется практически автоматически в том случае, если потомок имеет одного предка, и происходит это следующим образом. Каждый объект с его атрибутами, участвующий в такой связи, становится логическим сегментом. Между двумя логическими сегментами устанавливается связь типа "один ко многим". Сегмент со стороны "много" становится потомком, а сегмент со стороны "один" становится предком. Ситуация значительно усложняется, если потомок в связи имеет не одного, а двух и более предков. Так как подобное положение является невозможным для иерархической модели, то отражаемая структура данных нуждается в преобразованиях, которые сводятся к замене одного дерева, например, двумя (если имеется два предка). В результате такого преобразования в базе данных появляется избыточность, так как единственно возможный выход из этой ситуации – дублирование данных.
Например, если иерархическая база данных содержала информацию о покупателях и их заказах, то будет существовать объект «покупатель» (родитель) и объект «заказ» (дочерний). Объект «покупатель» будет иметь указатели от каждого заказчика к физическому расположению заказов покупателя в объект «заказ». В этой модели запрос, направленный вниз по иерархии, прост (например: какие заказы принадлежат этому покупателю); однако запрос, направленный вверх по иерархии, более сложен (например, какой покупатель поместил этот заказ).
Операции над данными, определенные в иерархической модели:
· ДОБАВИТЬ в базу данных новую запись. Для корневой записи обязательно формирование значения ключа.
· ИЗМЕНИТЬ значение данных предварительно извлеченной записи. Ключевые данные не должны подвергаться изменениям.
· УДАЛИТЬ некоторую запись и все подчиненные ей записи.
· ИЗВЛЕЧЬ:
- извлечь корневую запись по ключевому значению, допускается также последовательный просмотр корневых записей
- извлечь следующую запись (следующая запись извлекается в порядке обхода дерева, определенном в хранилище)
Примеры типичных операторов поиска данных:
· найти указанное дерево БД;
· перейти от одного дерева к другому;
· найти экземпляр сегмента, удовлетворяющий условию поиска;
· перейти от одного сегмента к другому внутри дерева;
· перейти от одного сегмента к другому в порядке обхода иерархии.
Примеры типичных операторов поиска данных с возможностью модификации:
· найти и удержать для дальнейшей модификации единственный экземпляр сегмента, удовлетворяющий условию поиска;
· найти и удержать для дальнейшей модификации следующий экземпляр сегмента с теми же условиями поиска;
· найти и удержать для дальнейшей модификации следующий экземпляр для того же родителя.
Примеры типичных операторов модификации иерархически организованных данных, которые выполняются после выполнения одного из операторов второй группы (поиска данных с возможностью модификации):
· вставить новый экземпляр сегмента в указанную позицию;
· обновить текущий экземпляр сегмента;
· удалить текущий экземпляр сегмента.
В иерархической модели автоматически поддерживается целостность ссылок между предками и потомками. Основное правило: никакой потомок не может существовать без своего родителя. При удалении родительской записи автоматически удаляются все подчиненные (аспект целостности).
Достоинства иерархической модели данных:
· простота представления сложных строго иерархических данных.
Недостатки иерархической модели данных:
· проблемы с преобразованием данных, не имеющих древовидной структуры: часто приходится вводить дублирующие связи, возникает проблема избыточности данных;
· отсутствие переиспользования данных за счет жесткого ограничения на структуру дерева.
Комментариев нет:
Отправить комментарий