русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

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


Дата добавления: 2014-03-26; просмотров: 678; Нарушение авторских прав


Примечание. Если исходный файл инвертирован по всем вторичным ключам, то он называется полностью инвертированным, если не по всем ключам, то частично инвертированным.

 

4.6 Прямой метод доступа. Хеширование

 

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

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

 

Ключ Преобразованное значение ключа Действительный адрес
. . . . . . .

Преобразованному ключу ставится в соответствие адрес с 1001 до 1011. Все ячейки с 1002 до 1011 являются пустыми. Это и есть зарезервированная память. Чтобы избавиться от основного недостатка в прямом методе доступа (а именно, значительного резервирования памяти), применяют методы хеширования.

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

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

 

Исходные значения ключей Преобразованные значения ключей
1-100 (синонимы) 201-400 401-600 601-800  

 



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

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

5 УСТАНОВЛЕНИЕ СВЯЗЕЙ МЕЖДУ ОБЪЕКТАМИ В ИНФОРМАЦИОННОЙ СИСТЕМЕ

 

5.1 Установление функциональных связей (ФС) между объектами

 

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

 

где А1, А2…, Аmисходные объекты,

В1, В2,… Вn, -конечные объекты.

Если исходный объект один, то это одномерная ФС, в другом случае – многомерная.

Под последовательностью ФС будем понимать упорядоченную совокупность, в которой всякое n-ная ФС используется в качестве исходного конечного объекта m-той ФС, 1≤m<n.

Для начала выполнения исследования необходимо обратится к экземплярам исходных объектов первой ФС. Для таких объектов задается характеристика В6, которая определяет дополнительные способы обращения к экземплярам объектов. В6 может принимать следующие значения:

 

 

D непосредственное обращение к экземплярам объектов,

В6 = S последовательное обращение к экземплярам объектов, DS обеспечение обеих возможностей.

 

Значение характеристики В6 определяется из текста запроса. Например, если имя в запросе обозначено словом «данному» или «указанному», в этом случае В6 = D. Если слово «каждому», то В6 = S.

В большинстве ФС используется один конечный объект. Однако, как видно из определения ФС, в не могут участвовать и несколько конечных объектов. В этом случае совокупность всех конечных объектов представляется как один объект.

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

 

 

Как указывалось выше, существует четыре типа связей между объектами: 1:1, 1:М, М:1, М:N. Тип соответствия между объектами будем обозначать Т (А,В). Например, тип соответствия

 

Т (предприятие, изделие)=M:N

 

Если последовательность ФС состоит только из одномерных связей, то ее преобразовывать не нужно. Если же в последовательности определены многомерные ФС, то эти связи требуется преобразовать к более простым. Введем некоторые определения:

1. Две совокупности ФС F1,, F2, …, Fk, F1,, F2, …, Fkназываются тождественными, если результаты их выполнения, полученные на одних и тех же экземплярах объектов, заданных в запросе, совпадают.

Пример. Дан запрос: выдать список всех учеников данной школы посещающих указанную библиотеку. Этому запросу соответствуют две тождественные последовательности:

 

ºº

 

Необходимо отметить, что порядок расположения исходных объектов в многомерной ФС можно менять, получая при этом тождественную ФС.

 

º

2. Упорядоченная совокупность объектов A1,…, Аk называется цепью объектов для " I, 1≤i<(k-1), если для "i выполняется

 

T(Ai,, Ai+1)=1:М

Пример. Университет, факультет, студент.

 

3. Упорядоченная совокупность ФС вида

,

 

называется цепью ФС, если совокупность A1, ……Akявляется цепью объектов. Процесс преобразования последовательности ФС заключается в замене этой последовательности на тождественную.

Преобразования последовательностей ФС

Преобразование 1.

Если среди исходных объектов многомерной ФС

(1)

Можно выделить цепь объектов A1, A2, ……Ak ,то такой многомерной ФС можно поставить в соответствие тождественную совокупность ФС:

 

º

Для выделения цепи исходных объектов сопоставляются таблицы типов соответствия.

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

 

Исходный объект A2 A3 A4 Если хотя бы в одной клетке таблицы задан тип соответствия, который отличается от M:N, то среди исходных объектов всегда можно выделить цепь.
A1 Т(A1,A2) Т(A1,A3) Т(A1, A4)
  A2 Т(A2,A3) Т(A2, A4)
    A3 Т(A3, A4)

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

F=

 

Исходный объект Город Район Подписное издание
Отделение связи М:1 М:1 M:N
  Город 1:М M:N
    Район M:N

В соответствии с указанной выше рекомендацией запишем следующее соответствие:

 

F== F2

 

Отметим, что во второй ФС имеет место цепь исходных объектов город, район, отделение связи, для которых выполняется преобразование:

F2º ,,

 

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

Примечание 2. Если в результате преобразований выделяется цепь ФС

,

а в соответствующей цепи исходных событий есть объект Ai,1≤i≤k для которого характер В6=D(DS), т.е. имеется возможность обращения к экземпляру объекта по назначению идентификатора, то в этих случаях первоначально определенная цепь ФС должна быть упразднена, если i=k и усечена, если i<k до следующего вида:

 

Например, рассмотренная выше последовательность ФС может быть представлена в виде:

(2)

 

Преобразование 2.

Ai, A2,…, AN

Если среди исходных объектов многомерной ФС Fв существует объект, для которого тип соответствия Т(А,В)=1:М, то такой многомерной связи сопоставляется тождественная совокупность ФС:

 

º

 

Если же первоначально ФС содержит только два исходных объекта, то ей можно сопоставить одну их двух тождественных совокупностей.

 

ºº

 

Возьмем ФС из выражения (2). Проанализируем эту связь. Очевидно, что тип связи

Т (подписное издание, адресат)= M:N,

Т (отделение связи, адресат)= 1:М.

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

 

º,º,

 

Отметим, что если в результате выполненных преобразований получена много мерная ФС, которая в дальнейшем уже не может быть подвергнута преобразованиям, то тип соответствия между объектами равен M:N. В то же время тип соответствия между любым исходным и конечным объектом не равен 1:М. Такая многомерная ФС называется канонической. Любая одномерная ФС является канонической.

3. Пусть одна многомерная ФС ,

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

поотношениюкзаданнойФС.

Преобразование 3.

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

Следует отметить, что после второго преобразования проводится проверка: входит ли объект Ai , для которого определена ФС типа FB в цепь исходных объектов или не входит. Ai

Если входит, то соответствующая этой цепи объектов цепь ФС заменяется обратной совокупностью связей. На этапе описания и анализа ФС определяется значение характеристики В7, которая носит название структурной активности.

А

В7=

N

 

Если В7=А, то при последующем развитии базы для этого объекта могут определяться новые ФС, следовательно он может входить в новые структурные связи.

При В7=N, предполагается, что объект не будет менять свой статус в информационной базе.

 

5.2 Установление структурных связей (СС) между объектами

 

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

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

 

Главный объект Детальный объект

 

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

С1 = М, в тех случаях, когда обеспечивается возможность обратного перехода,

NM, когда обеспечиваются обе возможности.

 

2. С2 – характеризует способ упорядочивания экземпляров детальных объектов в СС. Значение С2 определяется только для тех СС, у которых С1=N(NM). С2 определяет в какой последовательности будут выбираться экземпляры детального объекта при переходе к ним от главного объекта по указанной СС. Также одновременно характеристика С2 определяет способ и точку включения нового экземпляра детального объекта.

 

F, в тех случаях, когда новый экземпляр детального объекта включается первым в экземпляр СС,

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

С2 = S, в тех случаях, когда экземпляр детального объекта включается в связь по принципу сортировки,

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

 

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

4. С4 – накладывает ограничения на использование данной СС.

Характеристики детального объекта

Для каждого детального объекта должны быть заданы характеристики, которые отражают его участие в СС. Таких характеристик четыре: М1-М4.

М1 – класс, членство.

 

О, когда каждый экземпляр детального объекта обязательно участвует в каком-либо экземпляре этой СС,

М1 =

N, когда такое участие не обязательно.

 

Например,

 

Группа   Библиотека
 
     
Студент   Житель

М1=0 М1=N

М2 – характеризует перемещаемость экземпляров детального объекта.

 

R, когда экземпляр детального объекта может быть перемещен из одного экземпляра СС в другой,

М2 = N, когда перемещение экземпляров детального объекта запрещено.

 

М3 – это количество экземпляров детального объекта в экземпляре СС.

 

n1, количество экземпляров детального объекта во всех экземплярах СС, оно постоянно и равно n1,

М3 = (n1, n2 ), когда количество экземпляров детального объекта имеет переменное значение, оно колеблется от n1 до n2.

 

М4 – это параметры сортировки экземпляров детального объекта. Их определяют тогда, когда C2=S.

Параметры сортировки:

 

A, сортировка производится по возрастанию значений ключа,

L1 = D, сортировка производится по убыванию значений ключа сортировки.

 

 

D, когда допускается несколько экземпляров объектов с

L2 = одинаковым значением ключа сортировки,

N, когда такое положение не допускается.

 

 

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

Например,

 

М4=DDD

           
     
 

 


Сортировка по Возможно Указывается поле

убыванию дублирование сортировки

L1 L2 L3

 

Определение. Две СС называются согласованными, если они отвечают двум условиям:



<== предыдущая лекция | следующая лекция ==>
Эффективность доступа выше. Если индексный файл полностью помещается в оперативной памяти, эффективность доступа равна единице. | Временем выполнения запросов,


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.31 сек.