Программистам хорошо известно, что упорядоченность является мощным инструментом эффективной обработки данных. В условиях многоцелевого использования данных возникает естественная потребность иметь для одной таблицы несколько видов ее упорядоченного представления. Хранить несколько копий таблицы, по-разному упорядоченных, и поддерживать их адекватность – не самый лучший вариант решения этой проблемы. Типовой метод – использование индексных файлов.
Индексный файл – создается для фиксированной пары: таблица данных, ключ упорядочения. Ключ упорядочения обычно задается списком полей таблицы и определяет порядок – по неубыванию ключа.
ИндексныйФайл: 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
СХЕМА СВЯЗЕЙ ОБЪЕКТОВ
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,...
ПРИМЕР. Решение вышерассмотренной задачи «о крупных поставках» описывается запросом реляционного исчисления кортежей:
НАЙТИ{(r.ImPst,s.Kol)/rÎPsts,sÎPst}
(r.KPst=s.KPst)&(s.KDet=1010)&(s.Kol>1000)
ПРИМЕР. Найти имена поставщиков, которые поставляют все красные детали.
Переформулируем постановку задачи, явно оговорив неявное и явно выделив кванторы: найти имена таких поставщиков, что для каждой детали, если она красная, тосуществует договор о поставке этой детали этим поставщиком. Устранив импликацию (AÉB)º(ØAÚB), получим: найти имена таких поставщиков, что для каждой детали - либо она не красная, либо существует договор о поставке этой детали этим поставщиком.
= {0,1,2...} натуральный ряд. 
- множество всех векторов длины k с элементами из N. Отношение RÍ
,...dk) /
,...dk)ÎR}
r.A операция s.B