Последовательный поиск

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

Очевидно, что Max последовательного поиска равен N. Если частота использования каждого элемента списка одинакова, т.е. P=1/N, то Avg последовательного поиска равно N/2. При различной частоте использования элементов Avg можно улучшить, если поместить часто встречаемые элементы в начало списка.

 

21. Сортировка данных в линейном списке. Назначение и варианты реализации.

 

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

Сортировка представляет собой процесс упорядочения множества подобных информационных объектов в порядке возрастания или убывания их значений. Например, список i из n элементов будет отсортирован в порядке возрастания значений элементов, если i <= i <=... <= i. Имеется три способа сортировки массивов:

· сортировка обменом;

· сортировка выбором;

· сортировка вставкой.

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

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

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

{ сортировка пузырьковым методом}procedureBubble(varitem:DataArray; count:integer);vari,j: integer;x:DataItem;beginfor i:= 2 to count dobeginfor j:= count downto i doif item[j-1]>item[j] thenbeginx:= item[j-1];item[j-1]:= item[j];item[j]:= x;end;end;end; {конец сортировки пузырьковым методом}

 

{сортировкавыбором}procedureSelekt(var item: DataArray; count:integer);vari, j, k: integer;x: DataItem;beginfor i:= i to count-1 dobegink:= i;x:= item[i];for j:= i+1 tocountdo {найти элемент с наименьшим значением}if item[j]<x thenbegink:= j;x:= item[j];end;item[k]:= item[i]; {обмен}item[i]:= x;end;end; {конец сортировки выбором

 

{ сортировка вставкой }procedureInser(var item: DataArray; count:integer);vari, l: integer;x: DataItem;beginfor i:= 2 to count dobeginx:= item[i];j:= i-1;while (x<item[j]) and (j>0) dobeginitem[j+1]:= item[j];j:= j-1;end;item[j+1]:= x; end;

end; { конец сортировки вставкой

 

22. Стек и очередь. Назначение, варианты реализации и примеры применения.

 

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

очередь предполагает занесение нового элемента в конец, а выбор с начала списка (FIFO √ FirstInFirstOut);

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

поступивший первым, обслуживается первым

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

в стек элемент заносится в начало и выбирается также сначала (LIFO √ LastInFirstOut).

Обычно над стеками выполняется три операции:

· -начальное формирование стека (запись первой компоненты);

· -добавление компоненты в стек;

· -выборка компоненты (удаление).

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

constn=15; { количество позиций в стеке или очереди }

type s10=string[10]; mas=array [1..n] of s10;

var a:mas; c,kl:s10; k:integer; fl:boolean;

{=======================}

functionbuf(var c:s10):s10;

begin

read(c);

buf:=c;

end;

{=Процедурадобавления =}

procedure dob(var a:mas; n:integer; var k:integer; buf:s10; varfl:boolean);

begin

if k<n then

begin

a[k+1]:=buf;

k:=k+1;

fl:=true;

end

elsefl:=false;

end;

{=Процедурв извлечения из стека=}

functions_izvl(var a:mas; n:integer; var k:integer; varfl:boolean):s10;

begin

s_izvl:=a[k];

k:=k-1;

end;

{=Процедура извлечения из очереди=}

functiono_izvl(var a:mas; n:integer; var k:integer; varfl:boolean):s10;

var i:integer;

begin

o_izvl:=a[1];

k:=k-1;

for i:=1 to k do

a[i]:=a[i+1];

end;

 

23. Дерево. Назначение, варианты реализации и примеры применения.

 

Дерево — это совокупность элементов, называемых узлами (при этом один из них определен как корень), и отношений (родительский–дочерний), образующих иерархическую структуру узлов. Узлы могут являться величинами любого простого или структурированного типа, за исключением файлового. Узлы, которые не имеют ни одного последующего узла, называются листьями.

Поддерево — часть деревообразной структуры данных, которая может быть представлено в виде отдельного дерева. Любой узел дерева T вместе со всеми его узлами-потомками является поддеревом дерева T. Для любого узла поддерева либо должен быть путь в корневой узел этого поддерева, либо сам узел должен являться корневым. То есть поддерево связано с корневым узлом целым деревом, а отношения поддерева со всеми прочими узлами определяются через понятие соответствующее поддерево (по аналогии с термином «соответствующее подмножество»).

Существует два основных типа деревьев. В рекурсивном дереве или неупорядоченном дереве имеет значение лишь структура самого дерева без учёта порядка потомков для каждого узла. Дерево, в котором задан порядок (например, каждому ребру, ведущему к потомку, присвоены различные натуральные числа) называется деревом с именованными рёбрами или упорядоченным деревом со структурой данных, заданной перед именованием и называемой структурой данных упорядоченного дерева.

Упорядоченные деревья являются наиболее распространёнными среди древовидных структур. Двоичное дерево поиска — одно из разновидностей упорядоченного дерева.

В двоичном (бинарном) дереве каждый узел может быть связан не более чем двумя другими узлами. Рекурсивно двоичное дерево определяется так: двоичное дерево бывает либо пустым (не содержит ни одного узла), либо содержит узел, называемый корнем, а также два независимых поддерева — левое поддерево и правое поддерево.

Двоичное дерево поиска может быть либо пустым, либо оно обладает таким свойством, что корневой элемент имеет большее значение узла, чем любой элемент в левом поддереве, и меньшее или равное, чем элементы в правом поддереве. Указанное свойство называется характеристическим свойством двоичного дерева поиска и выполняется для любого узла такого дерева, включая корень. Далее будем рассматривать только двоичные деревья поиска. Такое название двоичные деревья поиска получили по той причине, что скорость поиска в них примерно такая же, что и в отсортированных массивах: O(n) = C • log2n (в худшем случае O(n) = n).

 

Пример. Для набора данных 9, 44, 0, –7, 10, 6, –12, 45 построить двоичное дерево поиска.

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

Выделим типовые операции над двоичными деревьями поиска:

добавление элемента в дерево;

удаление элемента из дерева;

обход дерева (для печати элементов и т.д.);

поиск в дереве.

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

С помощью графов-деревьев решают задачи планирования (дерево целей, дерево переборов вариантов).

Пусть двоичное дерево поиска описывается следующим типом

Type BT=LongInt; U = ^BinTree; BinTree = Record Inf:

BT; L, R: U End;

Покажем два варианта добавления элемента в дерево: итеративный и рекурсивный.

{Итеративный вариант добавления элемента в дерево, TurboPascal}

Procedure InsIteration(Var T: U; X: BT);

Varvsp, A: U;

Begin

New(A); A^.Inf:= X; A^.L:=Nil; A^.R:= Nil;

If T=Nil Then T:=A

Else Begin vsp:= T;

While vsp<> Nil Do

If A^.Inf<vsp^.Inf

Then

If vsp^.L=Nil Then Begin vsp^.L:=A;

vsp:=A^.L End Else vsp:=vsp^.L

Else

If vsp^.R = Nil Then Begin vsp^.R:= A;

vsp:=A^.R End Else vsp:= vsp^.R;

End

End;

 

{Рекурсивный вариант добавления элемента в дерево, TurboPascal}

Procedure InsRec(Var Tree: U; x: BT);

Begin

If Tree = Nil

Then Begin

New(Tree);

Tree^.L:= Nil;

Tree^.R:= Nil;

Tree^.Inf:= x

End

Else If x < Tree^.inf

Then InsRec(Tree^.L, x)

Else InsRec(Tree^.R, x)

End;

 

Аналогичнона C++.

typedef long BT;

structBinTree{

BT inf;

BinTree *L; BinTree *R;

};

 

24. Текстовые и типизированные файлы. Обмен данных с внешними носителями.

 

Турбо Паскаль поддерживает три файловых типа:

· текстовые файлы;

· типизированные файлы;

· нетипизированные файлы.

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

fileof тип - типизированный файл (указан тип компоненты);

text - текстовый файл;

file - нетипизированный файл.

Примеры описания файловых переменных:

var

f1: fileofchar;

f2: file of integer;

f3: file;

t: text;

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

Assign(f, FileName)

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

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

Reset(f)

открывает для чтения файл, с которым связана файловая переменная f. После успешного выполнения процедуры Reset файл готов к чтению из него первого элемента. Процедура завершается с сообщением об ошибке, если указанный файл не найден.

Если f - типизированный файл, то процедурой reset он открывается для чтения и записи одновременно.

Rewrite(f)

открывает для записи файл, с которым связана файловая переменная f. После успешного выполнения этой процедуры файл готов к записи в него первого элемента. Если указанный файл уже существовал, то все данные из него уничтожаются.

Close(f)

закрывает открытый до этого файл с файловой переменной f. Вызов процедуры Close необходим при завершении работы с файлом. Если по какой-то причине процедура Close не будет выполнена, файл все-же будет создан на внешнем устройстве, но содержимое последнего буфера в него не будет перенесено.

EOF(f): boolean

возвращает значение TRUE, когда при чтении достигнут конец файла. Это означает, что уже прочитан последний элемент в файле или файл после открытия оказался пуст.

Rename(f, NewName)

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

Erase(f)

уничтожает физический файл на диске, который был связан с файловой переменной f. Файл к моменту вызова процедуры Erase должен быть закрыт.

IOResult

возвращает целое число, соответствующее коду последней ошибки ввода - вывода. При нормальном завершении операции функция вернет значение 0. Значение функции IOResult необходимо присваивать какой-либо переменной, так как при каждом вызове функция обнуляет свое значение. Функция IOResult работает только при выключенном режиме проверок ошибок ввода - вывода или с ключом компиляции {$I-}.

Типизированный файл - это последовательность компонент любого заданного типа (кроме типа "файл"). Доступ к компонентам файла осуществляется по их порядковым номерам. Компоненты нумеруются, начиная с 0. После открытия файла указатель (номер текущей компоненты) стоит в его начале на нулевом компоненте. После каждого чтения или записи указатель сдвигается к следующему компоненту.

Запись в файл:

Write(f, список переменных);

Процедура записывает в файл f всю информацию из списка переменных.

Чтение из файла:

Read(f, список переменных);

Процедура читает из файла f компоненты в указанные переменные. Тип файловых компонент и переменных должны совпадать. Если будет сделана попытка чтения несуществующих компонент, то произойдет ошибочное завершение программы. Необходимо либо точно рассчитывать количество компонент, либо перед каждым чтением данных делать проверку их существования (функция eof, см. выше)

Смещение указателя файла:

Seek(f, n);

Процедура смещает указатель файла f на n-ную позицию. Нумерация в файле начинается с 0.

Определение количества компонент:

FileSize(f): longint;

Функция возвращает количество компонент в файле f.

Определение позиции указателя:

FilePos(f): longint;

Функция возвращает порядковый номер текущего компонента файла f.

Отсечение последних компонент файла:

Truncate(f);

Процедура отсекает конец файла, начиная с текущей позиции включительно.

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

Чтение из текстового файла:

Read(f, список переменных);

ReadLn(f, список переменных);

Процедуры читают информацию из файла f в переменные. Способ чтения зависит от типа переменных, стоящих в списке. В переменную char помещаются символы из файла. В числовую переменную: пропускаются символы-разделители, начальные пробелы и считывается значение числа до появления следующего разделителя. В переменную типа string помещается количество символов, равное длине строки, но только в том случае, если раньше не встретились символы конца строки или конца файла. Отличие ReadLn от Read в том, что в нем после прочтения данных пропускаются все оставшиеся символы в данной строке, включая метку конца строки. Если список переменных отсутствует, то процедура ReadLn(f) пропускает строку при чтении текстового файла.

Запись в текстовый файл:

Write(f, список переменных);

WriteLn(f, список переменных);

Процедуры записывают информацию в текстовый файл. Способ записи зависит от типа переменных в списке (как и при выводе на экран). Учитывается формат вывода. WriteLn от Write отличается тем, что после записи всех значений из переменных записывает еще и метку конца строки (формируется законченная строка файла).

Добавление информации к концу файла:

Append(f)

Процедура открывает текстовый файл для добавления информации к его концу. Используйте эту процедуру вместо Rewrite.

Пример:

ProgramWriting;

Var

FileName:string; {строка, содержащая имя файла}

FVar:fileofbyte; {переменная файлового типа}

Index:byte;

Begin

write ('Введите имя файла ');{предложение ввести имя файла}

readln (FileName);{ввод имени файла}

assign (FVar, FileName);{связь имени файла и переменной}

rewrite (FVar);{открытие файла для записи}

forIndex:= 0 to 99 do {цикл для расчетов и вывода данных в файл}

write (FVar,Index);{запись в файл FVar величины Index}

close (FVar); {закрытие файла}

End.

Под вводом-выводом в программировании понимается процесс обмена информацией между оперативной памятью и внешними устройствами: клавиатурой, дисплеем, магнитными накопителями и т. п. Ввод — это занесение информации с внешних устройств в оперативную память, а вывод — вынос информации из оперативной памяти на внешние устройства. Такие устройства, как дисплей и принтер, предназначены только для вывода; клавиатура — устройство ввода. Магнитные накопители (диски, ленты) используются как для ввода, так и для вывода.

Основным понятием, связанным с информацией на внешних устройствах ЭВМ, является понятие файла. Всякая операция ввода-вывода трактуется как операция обмена с файлами: ввод — это чтение из файла в оперативную память; вывод — запись информации из оперативной памяти в файл. Поэтому вопрос об организации в языке программирования ввода-вывода сводится к вопросу об организации работы с файлами.

Вспомним, что в Паскале мы использовали представления о внутреннем и внешнем файле. Внутренний файл — это переменная файлового типа, являющаяся структурированной величиной. Элементы файловой переменной могут иметь разный тип и, соответственно, разную длину и форму внутреннего представления. Внутренний файл связывается с внешним (физическим) файлом с помощью стандартной процедуры Assign. Один элемент файловой переменной становится отдельной записью во внешнем файле и может быть прочитан или записан с помощью одной команды. Попытка записать в файл или прочитать из него величину, не совпадающую по типу с типом элементов файла, приводит к ошибке.

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

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

CON (консоль) — логическое устройство, связанное при вводе с клавиатурой, при выводе — с экраном;

PRN (принтер) — логическое имя файла, связанного с устройством печати;

AUX — логическое имя коммуникационного канала, который используется для связи ПК с другими машинами;

INPUT — логическое имя стандартного устройства ввода, связанного с клавиатурой; при этом вводимые с клавиатуры символы отражаются на экране дисплея;

OUTPUT — логическое имя стандартного устройства вывода на экран.

Магнитный диск (МД) - многофайловое устройство. На нем хранятся как стандартные (системные) файлы, так и файлы, создаваемые пользователем. На магнитном диске могут создаваться файлы любых типов. Файлы на МД используются как в режиме чтения, так и в режиме записи.

Список файлов на диске хранится в директории (каталоге) диска. Каталог вызывается на экран системной командой DIR. В полной форме каталог содержит идентификаторы файлов, объем занимаемой памяти, дату и время создания файла. Идентификатор файла состоит из имени и типа файла:

<имя файла>.<тип файла>

Для организации связи между файловой переменной и внешним файлом в Турбо Паскале используется процедура назначения:

Assign (<имя файловой переменной>,

<идентификатор внешнего файла>);

Здесь <идентификатор внешнего файла> — строковая величина (константа или переменная). Например: Assign(Fi,'Number.dat');

После выполнения процедур Assign и Rewrite создается новый внешний файл, имя которого заносится в директорию.

Если файл открывается для чтения (Assign и Reset), то в указанном каталоге уже должен содержаться указанный внешний файл. В противном случае будет обнаружена ошибка.

Работа с файлом в программе завершается его закрытием с помощью процедуры

Close (<имя файловой, переменной>)

Например:

Close(Fi)

Подведем итог сказанному. Для создания и заполнения файла требуется следующая последовательность действий:

1. Описать файловую переменную.

2. Описать переменную того же типа, что и файл.

3. Произвести назначение (Assign).

4. Открыть файл для записи (Rewrite).

5. Записать в файл данные (Write).

6. Закрыть файл (Close).

25. Архитектуры баз данных. Преимущества и недостатки.

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

Имеется четыре разновидности архитектур баз данных:

• локальные базы данных;

• архитектура "файл-сервер";

• архитектура "клиент-сервер";

• многозвенная (трехзвенная N-tier или multi-tier) архитектура.

Требование к БД:

1.Непрерывное расширение, как структуры данных, так и содержимого.

2. расширения-дополнить содержимое

3.поиск информации

4.понизить избыточность данных и повысить их надежность

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

При работе с локальными базами данных сами БД расположены на том же компьютере, что и приложения, осуществляющие доступ к ним. Работа с БД происходит в однопользовательском режиме. BDE распложена на компьютере пользователя. Приложение ответственно за поддержание целостности БД и за выполнение запросов к БД.

При работе в архитектуре "файл-сервер"; БД и приложение расположены на файловом сервере сети. Возможна многопользовательская работа с одной и той же БД, когда каждый пользователь со своего компьютера запускает приложение, расположенное на сетевом сервере. Тогда на компьютере пользователя запускается копия приложения. По каждому запросу к БД из приложения данные из таблиц БД перегоняются на компьютер пользователя, независимо от того, сколько реально нужно данных для выполнения запроса. После этого выполняется запрос. Каждый пользователь имеет на своем компьютере локальную копию данных, время от времени обновляемых из реальной БД, расположенной на сетевом сервере. При этом изменения, которые каждый пользователь вносит в БД, могут быть до определенного момента неизвестны другим пользователям, что делает актуальной задачу систематического обновления данных на компьютере пользователя из реальной БД. Другой актуальной задачей является блокирование записей, которые изменяются одним из пользователей; это необходимо для того, чтобы в это время другой пользователь не внес изменений в те же данные.

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

• вся тяжесть вычислительной нагрузки при доступе к БД ложится на приложение клиента, что является следствием принципа обработки информации в системах "файл-сервер": при выдаче запроса на выборку информации из таблицы вся таблица БД копируется на клиентское место, и выборка осуществляется на клиентском месте;

• локальные СУБД используют так называемый "навигационный подход", ориентированный на работу с отдельными записями; не оптимально расходуются ресурсы клиентского компьютера и сети;

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

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

 

Характерной особенностью архитектуры "клиент-сервер " является перенос вычислительной нагрузки на сервер БД (SQL-сервер) и максимальная разгрузка приложения клиента от вычислительной работы, а также существенное укрепление безопасности данных - как от злонамеренных, так и просто ошибочных изменений.

БД в этом случае помещается на сетевом сервере, как и в архитектуре "файл-сервер", однако прямого доступа к БД из приложений не происходит. Функции прямого обращения к БД осуществляет специальная управляющая программа - сервер БД (SQL-сервер), поставляемая разработчиком СУБД.

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

Преимущества архитектуры "клиент-сервер":

• большинство вычислительных процессов происходит на сервере; таким образом снижаются требования к вычислительным мощностям компьютера клиента;

• снижается сетевой график за счет посылки сервером клиенту только тех данных, которые он запрашивал;

• упрощается наращивание вычислительных мощностей в условиях развития программного обеспечения и возрастания объемов обрабатываемых данных

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

• сервер реализует управление транзакциями и предотвращает попытки одновременного изменения одних и тех же данных; различные уровни изоляции транзакций позволяют определить поведение сервера при возникновении ситуаций одновременного изменения данных;

• безопасность системы возрастает за счет переноса большей части бизнес-правил на сервер;

Многозвенная архитектура доступа к базам данным.

Архитектура "клиент-сервер" является двухзвенной. Первым звеном является приложение клиента, вторым - сервер БД и сама БД.

В трехзвенной архитектуре наборы данных, бывшие ранее "собственностью" клиентских приложений, выделяются в отдельное звено, называемое сервером приложений. Совместно с ним располагается BDE. Теперь, при изменении бизнес-правил нет необходимости изменять приложения клиентов и обновлять их у всех пользователей-клиентов.

Сервер приложений разделяется несколькими клиентами. Он формирует запрос к удаленной БД (т.е. к SQL-серверу). На нем расположены реальные наборы данных (в двухзвенной архитектуре "клиент-сервер" располагавшиеся в приложении клиента). В клиентском приложении размещается "клиентский набор данных" (компонент TClientDataSet). Он представляет собой локальную копию данных с сервера приложений. Таким образом, все изменения, вносимые пользователем в данные при помощи клиентского приложения, вносятся в локальную копию НД. При обновлении удаленного НД клиентское приложение посылает серверу приложений только изменившиеся записи. Сервер приложений, в свою очередь, отсылает эти изменения SQL-серверу, который вносит их в удаленную БД.

 

26. Реляционные базы данных, основные понятия.

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

Каждая таблица состоит из столбцов (их называют полями или атрибутами) и строк (записями или кортежами)

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

 

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

 

Домен определяется заданием некоторого базового типа данных, к которому относятся элементы домена, и произвольного логического выражения, применяемого к элементу типа данных. Если вычисление этого логического выражения дает результат "истина", то элемент данных является элементом домена. Домен допустимое потенциальное множества значений данного типа. Например, домен "Имена" определен на базовом типе строк символов, но в число его значений могут входить только те строки, которые могут изображать имя.

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

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

Отношение - это множество кортежей данной базы данных, соответствующих одной схеме отношения.

В теории реляционных баз данных логическая группировка элементов данных называется «отношением», а определенный экземпляр отношения - «кортежем».

первичный ключ — это множество атрибутов отношения, которое уникально определяет кортеж этого отношения.

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

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

 

27. Понятия и терминология, связанные с таблицей реляционной базы данных.

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

Каждая таблица состоит из столбцов (их называют полями или атрибутами) и строк (записями или кортежами)

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

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

Таблицы реляционной БД должны отвечать требованиям нормализации отношений. Нормализация отношений — это формальный аппарат ограничений на формирование таблиц, который позволяет устранить дублирование, обеспечивает непротиворечивость хранимых в базе данных, уменьшает трудозатраты на ведение базы данных.

Имеется три нормальные формы отношений.

Первая нормальная форма. Реляционная таблица приведена к первой нормальной форме тогда и только тогда, когда ни одна из ее строк не содержит в любом своем поле более одного значения и ни одно из ее ключевых полей не пусто. Так, если из таблицы Студент требуется получать сведения по имени студента, то поле ФИО следует разбить на части Фамилия, Имя, Отчество.

Вторая нормальная форма. Реляционная таблица задана во второй нормальной форме, если она удовлетворяет требованиям первой нормальной формы и все ее поля, не входящие в первичный ключ, связаны полной функциональной зависимостью с первичным ключом. Чтобы привести таблицу ко второй нормальной форме, необходимо определить функциональную зависимость полей. Функциональная зависимость полей — это зависимость, при которой в экземпляре информационного объекта определенному значению ключевого реквизита соответствует только одно значение описательного реквизита.

Третья нормальная форма. Таблица находится в третьей нормальной форме, если она удовлетворяет требованиям второй нормальной формы, ни одно из ее неключевых полей не зависит функционально от любого другого неключевого поля. Например, в таблице Студент (№ группы, ФИО, № зачетной книжки, Дата рождения, Староста) три поля — № зачетной книжки, № группы, Староста находятся в транзитивной зависимости. № группы зависит от № зачетной книжки, а Староста зависит от № группы. Для устранения транзитивной зависимости необходимо часть полей таблицы Студент перенести в другую таблицу Группа. Таблицы примут следующий вид: Студент (№ группы, ФИО, № зачетной книжки, Дата рождения), Группа (№ группы, Староста).

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

Существуют следующие типы информационных связей:

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

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

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

 

 

28. Понятия и терминология, связанные с полем таблицы.

 

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

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

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

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