Индексные файлы и их использование.

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

Индексный файл – создается для фиксированной пары: таблица данных, ключ упорядочения. Ключ упорядочения обычно задается списком полей таблицы и определяет порядок – по неубыванию ключа.

ИндексныйФайл: FILEOF

RECORD НомерСтрокиТаблицыДанных:T1;

ЗначениеКлючаУпорядоченияДляЭтойстроки:T2

END

§ количество строк в индексном файле совпадает с их количеством файле данных;

§ индексный файл упорядочен по неубыванию ключа.

Индексный файл обеспечивает эффективный доступ к строке таблицы данных по заданному ее ключу (упорядочения):

§ сначала логарифмический поиск в индексном файле по ключу;

§ потом доступ к строке таблицы данных по ее номеру (эффективность этого доступа обеспечивают физические устройства хранения данных).

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

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

SQL- ориентированные СУБД, в частности InterBase:

§ создают и используют индексные файлы для внутренних целей, в частности для объявленных ключей – уникальных (UNIQUE), первичных (PRIMARY KEY), дочерних (FOREIGN KEY);

§ позволяют явно создавать индексные файлы

CREATE [UNIQUE] [ASC | DESC] INDEX ИмяИндексФайла

ON ИмяТаблицыДанных (ИмяКолонки,...)

§ поддерживают индексные файлы – обеспечивают их соответствующую корректировку при внесении изменений в данные таблиц;

§ допускают прямое использование индексных файлов программистами через посредников, предоставляющих Record- ориентированные средства обработки БД.

Использование индексных файлов в Delphi. Свойства и методы объекта типа TTable позволяют:

¨ Установить логический порядок строк в таблице.

§ property IndexName: String;

Устанавливает логический порядок, соответствующий указанному имени индексного файла.

§ property DefaultIndex: Boolean;

Устанавливает логический порядок по умолчанию, действующий только при пустом IndexName. Если DefaultIndex=TRUE и таблица имеет первичный ключ, то он и определяет логический порядок, иначе используется физический порядок.

Отметим, что ранее рассмотренные First, Next, Eof... выполняются в соответствии с текущим установленным логическим порядком.

¨ Выполнить поиск по ключу.

function FindKey

(const KeyValues: array of const): Boolean;

FindKey выполняет поиск строки по ее ключу, заданное значение ключа (значение KeyValues) должно соответствовать текущему логическому порядку. Если строка была найдена, то она становится текущей и FindKey возвращает TRUE.

¨ Установить операционную связь (Master-Detal).

В операционной связи участвуют две таблицы Ведущая (Master) и Ведомая (Detal), любое перемещение маркера текущей строки в ведущей таблице вызывает перемещение в ведомой на соответствующую строку. Операционная связь определяется (и реализуется) с помощью двух ключей:

§ Для Detal- таблицы (ведомой) надо установить логический порядок (индексный файл), его ключ упорядочения используется в качестве Detal -ключа.

§ Для Master- таблицы (ведущей) надо указать Master -ключ (список полей Master- таблицы).

§ В операционной связи Detal -таблица автоматически позиционируется на строке, у которой Detal -ключ равен Master -ключу текущей строки Master- таблицы.

Для установления связей с объектами – источниками данных в Delphi используются объекты специального классаTDataSource. Мы рассмотрим только одно свойство объектов этого класса property DataSet: TDataSet. Оно позволяет указать на объект типа TTable – источник данных.

Операционная связь устанавливается в объекте типа TTable, управляющем Detal- таблицей:

§ property IndexFieldNames: String;

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

§ property MasterSource: TDataSource;

Эта ссылка на объект типа TDataSource, у которого свойство DataSet ссылается на объект типа TDataSet, приводит к Master- таблице.

§ property MasterFields: string;

Этому свойству надо присвоить значение - список полей Master -ключа.

ПРИМЕР. Решение задачи «о крупных поставках».

DBLEC\PRG01\Project1.dpr DBLEC\Prg01C++\Project1.bpr

СХЕМА СВЯЗЕЙ ОБЪЕКТОВ

type

TForm1 = class(TForm)

Database1: TDatabase;

PstsTable: TTable; {Объект доступа к таблице Psts}

DetTable: TTable; {... Det}

DogTable: TTable; {... Dog}

PstTable: TTable; {... Pst}

NewTable: TTable; {... New – рабочая таблица для хранения

результата решения задачи}

DataSource1: TDataSource; {Объект, обеспечивающий связь

PstTable(Master) <- PstsTable(Detal)}

procedure N2Click(Sender: TObject);

procedure N3Click(Sender: TObject);

procedure N4Click(Sender: TObject);

end;

var Form1: TForm1;

procedure TForm1.N2Click(Sender: TObject);

{Решение 1. Используются средства работы с таблицами

на уровне записей ~ традиционные средства

программирования.}

begin

NewTable.Close;

NewTable.EmptyTable;

NewTable.Open;

PstsTable.Open;

PstTable.Open;

PstTable.First;

WHILE NOT PstTable.EOF DO

begin

IF (PstTable.FieldByName('KDet').Value=1010) AND

(PstTable.FieldByName('Kol').Value>1000) THEN

begin

PstsTable.First;

WHILE NOT PstsTable.EOF AND

(PstsTable.FieldByName('KPst').Value<>

PstTable.FieldByName('KPst').Value)

DO PstsTable.Next;

NewTable.Append;

NewTable.FieldByName('ImPst').Value:=

PstsTable.FieldByName('ImPst').Value;

NewTable.FieldByName('Kol').Value:=

PstTable.FieldByName('Kol').Value;

NewTable.Post;

end;

PstTable.Next;

end;

NewTable.Close;

NewTable.Open;

{Unit2.Form2.QuickRep1.DataSet:=Form1.NewTable;}

Unit2.Form2.QuickRep1.Preview

end;

procedure TForm1.N3Click(Sender: TObject);

{Решение 2. Используется FindKey - поиск по индексу}

begin

NewTable.Close;

NewTable.EmptyTable;

NewTable.Open;

PstsTable.Open;

PstTable.Open;

PstTable.First;

WHILE NOT PstTable.EOF DO

begin

IF (PstTable.FieldByName('KDet').Value=1010) AND

(PstTable.FieldByName('Kol').Value>1000) THEN

begin

{bb:=}PstsTable.FindKey

([PstTable.FieldByName('KPst').Value]);

{Да!!!??? В ObjectPascal2 это действительно

так... функцию можно вызвать как процедуру,

по крайней мере иногда.}

NewTable.Append;

NewTable.FieldByName('ImPst').Value:=

PstsTable.FieldByName('ImPst').Value;

NewTable.FieldByName('Kol').Value:=

PstTable.FieldByName('Kol').Value;

NewTable.Post;

end;

PstTable.Next;

end;

NewTable.Close;

NewTable.Open;

Unit2.Form2.QuickRep1.Preview

end;

procedure TForm1.N4Click(Sender: TObject);

{Решение 3. Используется реляционная связь Master-Detal}

begin

NewTable.Close;

NewTable.EmptyTable;

NewTable.Open;

PstsTable.Close;

DataSource1.DataSet:=PstTable;

PstsTable.MasterSource:=DataSource1;

PstsTable.MasterFields:='KPst';

PstsTable.Open;

PstTable.Open;

PstTable.First;

WHILE NOT PstTable.EOF DO

begin

IF (PstTable.FieldByName('KDet').Value=1010) AND

(PstTable.FieldByName('Kol').Value>1000) THEN

begin

NewTable.Append;

NewTable.FieldByName('ImPst').Value:=

PstsTable.FieldByName('ImPst').Value;

NewTable.FieldByName('Kol').Value:=

PstTable.FieldByName('Kol').Value;

NewTable.Post;

end;

PstTable.Next;

end;

NewTable.Close;

PstsTable.Close;

PstsTable.MasterSource:=NIL;

PstsTable.MasterFields:='';

DataSource1.DataSet:=NIL;

PstsTable.Open;

NewTable.Open;

Unit2.Form2.QuickRep1.Preview

end;

Средства обработки БД в СУБД FoxPro.DBL(FOX).doc

 

4. Теоретические основы реляционной модели баз данных.

4.1. Перечислимые отношения и способы их задания: алгоритмический, алгебраический и логический подходы.

= {0,1,2...} натуральный ряд. - множество всех векторов длины k с элементами из N. Отношение RÍ , R: FILE OF RECORD x1,x2,... xk: Natural END

В теории рассматриваются в том числе и бесконечные отношения-файлы. Дело в том что задачи «Вычислить y=f(x)» и «Перечислить отношение {(x,y)/y=f(x)}» сводимы друг к другу (по крайней мере для xÎ N).

Алгоритмический подход.

Перечислимое отношение - имеется программа, формирующая соответствующий файл:

§ ничего не вводит, только выводит;

§ в случае бесконечного отношения R: выводит только вектора из R и для " вектора Î R $ t такое что этот вектор будет выведен через £ t шагов работы.

R перечислимо относительно R1,...Rк – имеется аналогичная программа, но с входными файлами R1,...Rк и на языке, расширенном логическими выражениями вида rÎR1,... rÎRk. Отметим, что в случае бесконечных R1,...Rк наличие возможности «запросто» получить ответ на вопрос вида «IF rÎR1 THEN... ELSE...» не просто облегчает задачу перечисления, а открывает возможность перечислять неперечислимое без такого использования R1,...Rк.

Алгебраический подход.

Общая схема:

§ Фиксируется конечный набор базовых отношений.

§ Фиксируется конечный набор операций над отношениями O: R1,...Rк ® R.

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

§ R перечислимо относительно R1,...Rк – имеется аналогичное выражение, в котором дополнительно к базовым можно использовать отношения R1,...Rк.

Один из вариантов такой алгебраической системы:

¨ Базовые отношения:

§ Sum: (x,y,z)ÎSum Û x+y=z

§ Mult: (x,y,z)ÎMult Û x*y=z

¨ Набор операций.

§ Группа теоретико-множественных операций: È, Ç и – (дополнение).

§ Группа операций явного преобразования.

Пусть RÍ , I1,...Ik Î {1,2,...n}È{#d/ dÎ N }.

{n:I1,...Ik}(R) = {(A1,...An) / (B1,...Bk)ÎR, где Bj = IF IjÎ{1,2,...n} THEN

ELSE d (где Ij=#d)}

Примеры важных (для последующего материала) операций. Пусть k=8.

· Выборка по значению компонента.

{7:#d,1,...7}(R)=

{(A1,...A7)/(d,A1,...A7)ÎR}

· Выборка по равенству значений двух компонентов.

{7:1,1,...7}(R)=

{(A1,...A7)/(A1,A1,A2,...A7)ÎR}

· Перестановка (переименование) компонентов.

{8:2,1,3,...8}(R)=

{(A1,A2,A3,...A8)/(A2,A1,A3,...A8)ÎR}

· Цилиндрификация – декартово умножение на N.

{9:1,...8}(R)=

{(A1,...A8,A9)/(A1,...A8)ÎR, A9Î N }

§ Ограниченная (",$) квантификация.

{"xi £ y}(R)= {(d1,...,di,...dk) /

для каждого dÎ N такого, что (d £ di), имеет место (d1,...,d,...dk)ÎR}

{$xi £ y}(R)= {(d1,...,di,...dk) /

имеется dÎ N такое, что (d £ di) и (d1,...,d,...dk)ÎR}

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

§ Проекция ($-квантификация неограниченная).

{$xi}(R)= {(d1,..., ,...dk) /

имеется dÎ N такое, что

(d1,..., ,...dk)ÎR}

Перечислимое отношение – можно получить проекциями из подходящего конструктивно определимого отношения.

Логический подход.

...

 

 

4.2. Реляционная алгебра.

Ниже используются обозначения:

· A,B,C... (возможно с индексами) - имена полей (атрибуты), причем считается, что для каждого имени однозначно определен тип данных (домен) и этот тип неструктурный;

· r,s,t... (возможно с индексами) - переменные типа запись (кортеж), причем считается, что порядок полей в записи не существенен, т.е. записи с одинаковым множеством полей (и их значениями) одинаковы;

· R,S,T... (возможно с индексами) - переменные типа файл (таблица, отношение), причем считается, что порядок записей в файле не существенен и одинаковых записей в файле не может быть, т.е. файлы с одинаковым множеством записей одинаковы.

Базовый набор файлов: файлы, содержащие одну запись; базовые файлы определяются с помощью операции - (имя_поля: значение_поля,...)

Базовый набор операций над файлами.

Ø Теоретико-множественные: Ç È - (объединение, пересечение и разность, соответственно). Операции применимы только к парам файлов, имеющих одинаковую структуру (схему отношения базы данных).

Ø Естественное соединение R*S={r*s / rÎR, sÎS}, где операция соединения записей r и s применима только к парам записей, у которых одноименные поля имеют одинаковое значение. Соединение таких записей r и s дает запись, в которую входят все поля (со своими значениями) из r и s (одноименные поля не дублируются).

ПРИМЕР.(A:1,B:2)*(B:2,C:3)=(A:1,B:2,C:3);

(A:1,B:2)*(C:3,D:4)=(A:1,B:2,C:3,D:4) - в случае файлов без одноименных полей, операция применима к каждой паре записей;

(A:1,B:2)*(B:3,D:4) - к такой паре записей операция не применима.

Ø Выборка [ B ] (R) = файл записей из R, удовлетворяющих условию B. Условие B строится как обычное логическое выражение - из имен полей и констант с помощью операций сравнения и логических операций.

Ø Переименование полей [ A1®B1,A2®B2,... ] (R). A1,A2,... должны быть именами полей файла R, а поля B1,B2,... должны иметь соответствующий тип. Результат операции будет содержать те же записи, что и файл R, но поля A1,A2,... будут соответственно переименованы на B1,B2,...

Ø Проекция [имя_поля,...] (R) = файл записей из R, в которых удалены все поля, кроме перечисленных в операции.

Ø Деление R ¸ S. Операция применима, если все поля «делителя» S являются полями «делимого» R; пусть A1,A2,... - поля файла S, а A1,A2,...B1,B2,... - поля файла R. Результат деления будет файлом с полями B1,B2,... R ¸ S={t: такие, что (t*s)ÎR для любой записи s из S}. Отметим, что в этом выражении записи t и s не имеют общих полей, поэтому операция * это просто соединение записей.

ПРИМЕР. Пусть R - файл с полями (A,B), S - файл с полем (A), T=(R ¸ S) - будет файлом с полем (B):

 

ПРИМЕР. Решение вышерассмотренной задачи «о крупных поставках» описывается реляционным выражением:

[ImPst,Kol](Psts*([(KDet=1010)&(Kol>1000)]Pst))

4.3. Реляционное исчисление кортежей.

Базовые (элементарные) формулы:

· R(r) - имеет смысл «запись r принадлежит файлу R», т.е. rÎR.

· r.A операция s.B

константа сравнения константа

имеет смысл «поле A записи r (или константа) имеет значение больше (меньше, равно...), чем поле B записи s (или константа)».

Формулы общего вида - строятся из базовых с помощью операций:

· логики высказываний &Ú и ограниченно используемого отрицания Ø: если F1 и F2 формулы, то F1 & F2, F1 Ú F2, F1 &Ø F2тоже формулы;

· логики предикатов "$: если F формула, то " rÎR F и $ rÎR Fтоже формулы.

Смысл формул без кванторов "$ известен по языку Паскаль - это логические выражения с операциями AND (&), OR (Ú) и NOT (Ø).

Смысл кванторных формул - для фиксированных значений других (кроме r) переменных:

· формула " rÎR F истинна, если формула F истинна для любой записи r из файла R

· формула $ rÎR F истинна, если формула F истинна хотя бы для одной записи r из файла R.

ПРИМЕЧАНИЕ. С некоторыми оговорками (уточнениями, в которых используется операция естественного соединения - декартова произведения) имеют место следующие соответствия:

· каждой формуле соответствует файл записей, на которых эта формула истинна;

· формулам F1 & F2, F1 Ú F2, F1 &Ø F2 соответствуют Ç (пересечение), È (объединение) и - (разность) файлов, соответствующих формулам F1 и F2;

· формуле " rÎR F соответствует файл F ¸ R;

· формуле $ rÎR F соответствует проекция файла F по полям, которые отсутствуют в rÎR.

Запрос НАЙТИ{(r.A,...s.B,...)/rÎR,sÎS...}F имеет смысл:

· найти запись r в файле R, s в файле S..., такие что на этом наборе записей истинна формула F;

· по каждому такому набору записей сформировать соответствующую запись в файл - результат запроса, включая в нее поле A записи r, поле B записи s,...

ПРИМЕР. Вышеприведенный рисунок, иллюстрирующий операцию деления T=(R ¸ S), соответствует запросу T=НАЙТИ{t.B/tÎR} " sÎS $ rÎR ((r.B=t.B) & (r.A=s.A))

ПРИМЕР. Решение вышерассмотренной задачи «о крупных поставках» описывается запросом реляционного исчисления кортежей:

НАЙТИ{(r.ImPst,s.Kol)/rÎPsts,sÎPst}

(r.KPst=s.KPst) & (s.KDet=1010) & (s.Kol>1000)

ПРИМЕР. Найти имена поставщиков, которые поставляют все красные детали.

Переформулируем постановку задачи, явно оговорив неявное и явно выделив кванторы: найти имена таких поставщиков, что для каждой детали, если она красная, тосуществует договор о поставке этой детали этим поставщиком. Устранив импликацию (AÉB)º(ØAÚB), получим: найти имена таких поставщиков, что для каждой детали - либо она не красная, либо существует договор о поставке этой детали этим поставщиком.