Шпаргалка по "Информатике"

Существует несколько  способов изображения структуры  дерева. На рис. 4.17 приведено несколько примеров таких структур, где базовый тип Т—множество букв. Эти схемы относятся к одной и той же структуре и, следовательно, эквивалентны. Структура, представленная в виде графа и явно отражающая разветвления, по понятным причинам привела к появлению общеупотребительного термина «дерево». Однако довольно странно, что деревья принято рисовать перевернутыми или, можно считать и так, изображать только его корни. Как бы то ни было, и последнее толкование вводит в заблуждение, так как верхнюю вершину (А) обычно называют корнем.

Упорядоченное дерево — это дерево, у которого ребра (ветви), исходящие из каждой вершины, упорядочены. Поэтому два упорядоченных дерева на рис. 4.18—это разные, отличные друг от друга объекты. Вершина у, находящаяся непосредственно ниже вершины х, называется непосредственным потомком х; если х находится на уровне i, то говорят, что у лежит на уровне i + 1 - И наоборот, вершину х называют (непосредственным) предком * у. Считается, что корень дерева находится на уровне 0. Максимальный уровень какой-либо из вершин дерева называется его глубиной или высотой.

Если элемент  не имеет потомков, то его называют терминальной вершиной или листом, а нетерминальную вершину называют внутренней. Число непосредственных потомков внутренней вершины называют ее степенью. Максимальная степень всех вершин есть степень дерева. Число ветвей или ребер, которые нужно пройти от корня к вершине х, называется длиной пути к х. Корень имеет путь 0, его прямые потомки имеют путь длиной 1 и т. д. Вообще, вершина на уровне i имеет длину пути i. Длина пути всего дерева определяется как сумма длин путей для всех его компонент. Ее также называют длиной внутреннего пути. Например, длина внутреннего пути дерева, изображенного на рис. 4.17, равна 36.

Рис.  4.17 Представление  древовидной  структуры:  а) вложенные множества, Ь) вложенные скобки, с) отступы, d) граф. Иногда употребляют термин «родитель» и очень часто говорят об «отце» и «сыне», поскольку это сразу объясняет термины «брат» и даже «дядя»! — Прим. перев.

Рис. 4.18. Два  различных двоичных дерева. Очевидно, что средняя длина пути

P_I=(Si:!<i<n:n_|»i)/n      _: щ

 

35.Реляционная  полнота SQL. Порядок выполнения команды

SELECT.

Порядок выполнения оператора SELECT

Для того чтобы понять, как получается результат выполнения оператора SELECT, рассмотрим концептуальную схему его выполнения. Эта схема является именно концептуальной, т.к. гарантируется, что результат будет таким, как если бы он выполнялся шаг за шагом в соответствии с этой схемой. На самом деле, реально результат получается более изощренными алгоритмами, которыми "владеет" конкретная СУБД. Стадия 1. Выполнение одиночного оператора SELECT

Если в операторе присутствуют ключевые слова UNION, EXCEPT и INTERSECT, то запрос разбивается на несколько независимых запросов, каждый из которых выполняется отдельно:

Шаг 1 (FROM). Вычисляется прямое декартовое произведение всех таблиц, указанных в обязательном разделе FROM. В результате шага 1 получаем таблицу А.

Шаг 2 (WHERE). Если в операторе SELECT присутствует раздел WHERE, то сканируется таблица А, полученная при выполнении шага 1. При этом для каждой строки из таблицы А вычисляется условное выражение, приведенное в разделе WHERE. Только те строки, для которых условное выражение возвращает значение TRUE, включаются в результат. Если раздел WHERE опущен, то сразу переходим к шагу 3. Если в условном выражении участвуют вложенные подзапросы, то они вычисляются в соответствии с данной концептуальной схемой. В результате шага 2 получаем таблицу В.

Шаг 3 (GROUP BY). Если в операторе SELECT присутствует раздел GROUP BY, то строки таблицы В, полученной на втором шаге, группируются в соответствии со списком группировки, приведенным в разделе GROUP BY. Если раздел GROUP BY опущен, то сразу переходим к шагу 4. В результате шага 3 получаем таблицу С.

Шаг 4 (HAVING). Если в операторе SELECT присутствует раздел HAVING, то группы, не удовлетворяющие условному выражению, приведенному в разделе HAVING, исключаются. Если раздел HAVING опущен, то сразу переходим к шагу 5. В результате шага 4 получаем таблицу D.

Шаг 5 (SELECT). Каждая группа, полученная на шаге 4, генерирует одну строку результата следующим образом. Вычисляются все скалярные выражения, указанные в разделе SELECT. По правилам использования раздела GROUP BY, такие скалярные выражения должны быть одинаковыми для всех строк внутри каждой группы. Для каждой группы вычисляются значения агрегатных функций, приведенных в разделе SELECT. Если раздел GROUP BY отсутствовал, но в разделе SELECT есть агрегатные функции, то считается, что имеется всего одна группа. Если нет ни раздела GROUP BY, ни агрегатных функций, то считается, что имеется столько групп, сколько строк отобрано к данному моменту. В результате шага 5 получаем таблицу Е, содержащую столько колонок, сколько элементов приведено в разделе SELECT и столько строк, сколько отобрано групп.

Стадия 2. Выполнение операций UNION, EXCEPT, INTERSECT

Если в операторе SELECT присутствовали ключевые слова UNION, EXCEPT и INTERSECT, то таблицы, полученные в результате выполнения 1-й стадии, объединяются, вычитаются или пересекаются. Стадия 3. Упорядочение результата

Если в  операторе SELECT присутствует раздел ORDER BY, то строки полученной на предыдущих шагах таблицы упорядочиваются в соответствии со списком упорядочения, приведенном в разделе ORDER BY. 

44. Использование индексов  в Visual FoxPro 5.0. Типы индексов. Поиск данных в индексированных и неиндекс фай.

Команда, создающая индексный файл: INDEX ON <expr> TO <ind_file> [FOR <exprL>] [UNIQUE] Здесь:   <expr     -   ключ   индексирования,   т.е.   выражение   с числовыми или с символьными переменными или с датами но не с логическими переменными и не с memo-полями!); <ind_fle> - имя индексного файла без расширения (по умолчанию Visual FoxPro 5.0 присвоит расширение .idx).

FOR   <exprL>   -   опция,   позволяющая   эффективно   сочетать I   индексирование и фильтрацию данных: в индексном файле будут упорядочены   записи,   для  которых   соблюдается   логическое условие <exprL>.

1. Поиск записей в индексированных файлах

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

| индексированных файлов  и одной из команд поиска (FIND или SEEK), в которых должно быть задано значение ключа. Если Вы не хотите указать значение ключа точно (например, не хотите или не помните точно искомой фамилии и ищете запись только по первой букве либо по нескольким первым буквам), следует использовать конфигурацию виртуальной машины Visual FoxPro 5.0 командой из группы SET: SET EXACT ON и SET

I   EXACT OFF Команды поиска FIND имеют форму: FIND <значение ключа индексирования> SEEK <значение ключа индексирования>

По любой из этих команд будет найдена запись, в которой  значение ключа точно (если SET EXACT ON) или приблизительно (если SET EXACT OFF) совпадает с заданным в команде <значением ключа индексирования>. Если ключ -числовой, то совпадение требуется точное, если включен режим SET NEAR OFF, либо приблизительное, с округлением - если

j   SET NEAR ON По умолчанию в Visual FoxPro 5.0   установлено:SET EXACT OFF; SET NEAR OFF

Если в  файле имеется несколько записей  с одинаковым значением ключа, то по команде FIND файловый указатель остановится на «первой встреченной», функция RECNO(), возвращает номер записи:      ?RECNO()

2. Поиск записей в неиндексированном файле.

Если база данных невелика (менее 100 записей, менее 10 полей), индексирование не даст заметного выигрыша во времени по сравнению с «прямым», переборным поиском. Этот поиск осуществляется совокупностью команд:

LOCATE [<scope>] [FOR <exprL>][WHILE <exprl>]

<серия  команд FoxPro2.0> [CONTINUE]

Здесь: <scope> - группа записей (все, ALL; насколько следующих NEXT<число>; оставшиеся до конца файла REST); (по умолчанию поиск ведется по всей базе данных).

FOR... WHILE - необязательная часть команды, задающая условие поиска:

запись найдена, если логическое условие <exprL> истинно. FOR устанавливает условия для всех записей файла; WHILE  действует до тех пор, пока не будет «встречена» первая запись, не удовлетворяющая условию <exprL>.

По команде LOCATE файловый указатель останавливается на «первой встреченной» записи, для которой соблюдается условие поиска FOR... или WHILE.

Затем может быть выполнена  серия команд (например, просмотра  базы данных и/или определения номера записи, на которой остановился указатель).

Затем      поиск      может      быть      продолжен необязательная   опция   CONTINUE   для   нахождения   записей, возможно, также удовлетворяющих условию поиска - до конца файла (когда функция EOF() возвратит .Т. («истина»)). 

ЗО.Проектирование БД. Этап «Проектирование реализации».

Проектирование  БД

Методология поэтапного проектирования БД может  быть

определена  как построение структуры БД на основе

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

В настоящее  время существуют следующие этапы  построения БД:

1. Этап- Анализ требований.

2. Этап- Концептуальное (логическое) проектирование. I   3 Этап- Проектирование реализации.

| ! 4 Этап- Физическое проектирование. | ^: 5 Этап- Машинное проектирование. |     Каждый этап проектирования характеризуется набором методов

проектирования  и критериями оценки альтернативных вариантов.

Выбор критериев  оценки альтернативных вариантов является

слабым звеном в проектировании БД. Это обусловлено

следующими  факторами:

1 )Многовариантность  решения задачи проектирования.

2)Сложность  оценки альтернативных вариантов.  Большинство из

критериев не имеет количественной оценки, их важность

изменяется  во времени, время действия различных  критериев не

одинакова.

В качестве критериев оценки эффективности проектирования БД

используются  следующие:

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

I   Возможность изменения структуры БД, удобство пользовательского интерфейса и т.д.

ЗЗ.Понятие  языка данных. Язык запросов SQL. Команды DDL, DML, DCD.

Фактически  стандартным языком доступа к  базам данных в настоящее время стал язык SQL (Structured Query Language).

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

Стандарт  языка SQL, хотя и основан на реляционной теории, но во многих местах отходит он нее.

Основу языка SQL составляют операторы, условно разбитые не несколько групп по выполняемым функциям:

Операторы DDL (Data Definition Language) - операторы определения объектов базы данных.

Операторы DML (Data Manipulation Language) - операторы манипулирования данными.

Операторы защиты и управления данными, и др.

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

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