Поиск информации в БД с использованием структуры типа «сильно ветвящееся дерево».

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

Сильно ветвящееся дерево - выровненное m-арное дерево поиска, у которого каждая вершина имеет не более 2 m и не менее (кроме корня и листов) m потомков и корень, если он не является листом, имеет не менее двух потомков.

 

Рисунок 2 пример ветвящегося дерева как B-дерево.

Свойства:

· кажд. узел, за искл-ем корня содержит не < n и не > 2n ключей;

· корень содержит не < 1 и не > 2n ключей;

· все листья располологаются на 1 ур-не;

· каждый нелистовой узел содержит 2 списка: упорядоченный по возрастанию список ключей и соответствующий ему список указателей на поддеревья.

· лист-е узлы содержатт т.ж. 2 сп.: 1-й т.ж. и сп-к указ-ей на конкр-е д-е.

 

 

Представление данных с помощью модели «сущность-связь», основные элементы модели.

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

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

Элементы модели.

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

1. Сущность (entity) - это объект, который может быть идентифицирован неким способом, отличающим его от других объектов. Примеры: конкретный человек, предприятие, событие и т.д.

2. Набор сущностей - множество сущностей одного типа (обладающих одинаковыми свойствами). Примеры: все люди, предприятия. Наборы сущностей не обязательно должны быть непересекающимися. Например, сущность, принадлежащая к набору МУЖЧИНЫ, также принадлежит набору ЛЮДИ.

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

Атрибут - функция, отображающая набор сущностей в набор значений или в декартово произведение наборов значений. Домен -множество значений атрибута.

4. Ключ сущности - группа атрибутов, такая, что отображение набора сущностей в соответствующую группу наборов значений является взаимнооднозначным отображением. Другими словами: ключ сущности - это один или более атрибутов, уникально определяющих данную сущность.

5. Связь – в общем случае это некоторая ассоциация, которая устанавливается между несколькими сущностями. Набор связей – это отношение между N сущностями каждое из которых относится к отдельному набору сущностей (N>=2). N=2 – Бинарная связь. N>2 – N-арная связь.

При построении модели С-С N-арной связи:

лучше отражают семантику П.О.

позволяют создать более компактную модель С-С.

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

Бинарные связи – позволяют в полной мере обеспечить целостность связи.

Модель сущность-связь– один из наиболее удобных инструментов унифицированного представления данных.Она является логическим представление данных.

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

Элементы:

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

Экземпляр сущности – это конкретный представитель данной сущности(например Попов Егор)

Ключ сущности – один или группа атрибутов, однозначно определеющих экземпляр сущности.

Атрибут сущности - это именованная характеристика, являющаяся некоторым свойством сущности.

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

Набор связей (relationship set) - это отношение между n (причем n не меньше 2) сущностями, каждая из которых относится к некоторому набору сущностей.

14. Типы и характеристики связей сущностей;

Связь (relationship) -это ассоциация, установленная между несколькими сущностями.

Пример:

· поскольку каждый сотрудник работает в каком-либо отделе, между сущностями СОТРУДНИК и ОТДЕЛ существует связь "работает в" или ОТДЕЛ-РАБОТНИК;

· так как один из работников отдела является его руководителем, то между сущностями СОТРУДНИК и ОТДЕЛ имеется связь "руководит" или ОТДЕЛ-РУКОВОДИТЕЛЬ;

· могут существовать и связи между сущностями одного типа, например связь РОДИТЕЛЬ - ПОТОМОК между двумя сущностями ЧЕЛОВЕК;

Набор связей - это отношение между n (причем n не меньше 2) сущностями, каждая из которых относится к некоторому набору сущностей.

Пример:

сущности наборы сущностей

---------- ----------------

e1 принадлежит E1

e2 принадлежит E2

...

en принадлежит En

тогда [e1,e2,...,en] - набор связей R

В случае n=2, т.е. когда связь объединяет две сущности, она называется бинарной.

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

Виды степеней связи:

1. один к одному (1: 1). Это означает, что в такой связи сущности с одной ролью всегда соответствует не более одной сущности с другой ролью.

2. один ко многим (1: n). Это означает что сущности с одной ролью может соответствовать любое число сущностей с другой ролью.

3. много к одному (n:1). Этот тип связи аналогичен связям один ко многим.

4. много ко многим (n:n). В этом случае каждая из ассоциированных сущностей может быть представлена любым количеством экземпляров

Класс принадлежности сущности, входящей в состав связи (кординальность связи):

Так как в каждом отделе обязательно должен быть руководитель, то каждой сущности "ОТДЕЛ" непременно должна соответствовать сущность "СОТРУДНИК". Однако, не каждый сотрудник является руководителем отдела, следовательно в данной связи не каждая

сущность "СОТРУДНИК" имеет ассоциированную с ней сущность "ОТДЕЛ".

Таким образом, говорят, что сущность "СОТРУДНИК" имеет обязательный класс принадлежности (этот факт обозначается также указанием интервала числа возможных вхождений сущности в связь, в данн случае это 1,1), а сущность "ОТДЕЛ" имеет необязательн класс принадлежности (0,1)

· Обязательный класс принадлежности;

· Необязательный класс принадлежности.

Если существование сущности X зависит от существования сущности Y, то X называется зависимой сущностью (иногда сущность X называют "слабой", а"сущность" Y - сильной).

Пример:

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

с заказчиком, и прекращает свое существование по выполнению контракта. Таким

образом, сущность РАБОЧАЯ_ГРУППА является зависимой от сущности КОНТРАКТ.

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

линией со стрелкой.