Новости :

FoxPro : Советы начинающим Часть III

FoxPro : Советы начинающим Часть III

В этой статье :

Индекс
Типы (виды) индексов
Режим сортировки индексов (Collate)
Метод половинного деления
Использование индексов для отображения данных
Контроль уникальности данных при помощи индекса
Название индексных тегов
Сколько и каких индексов надо создавать
Собственно работа с индексами
Индекс
Важнейшим элементом любой системы управления базами данных является наличие средств ускоренного поиска данных, поскольку поиск - это самая распростарненная операция в системах обработки данных. Но простое сканирование исходной таблицы в поисках нужной записи - это относительно медленная операция. В предельном случае, необходимо будет просканировать все записи таблицы, чтобы найти нужную запись или убедится, что такой записи не существует. Чтобы уменьшить количество просматриваемых записей, как правило, создают специальный файл, который содержит в себе нечто вроде списка пар: значение записи - номер запись. Т.е. в этом файле, перечисленны все значения некоторого поля или функции полей таблицы и указаны идентификаторы соответсвующих записей Этот специальный файл называют индексным файлом, а имя поля или функцию полей, на основе которого вычисляется значение записи - индексным ключем

В FoxPro различают 2 вида индексных файлов

Простой (обычный) индексный файл - это файл с расширением IDX, который содержит в себе только один индексный ключ

Мультииндексный файл - это файл с расширением CDX, который может содержать в себе несколько индексных ключей. По существу, мультииндексный файл - это объединение в одном файле нескольких простых (обычных) индексных файлов. Каждый отдельный индекс в этом файле за неимением лучшего термина называют тегом (от английского TAG - этикетка, метка)

Кроме того, выделяют еще особый структурный индексный файл - это обычный мультииндексный файл, но его имя совпадает с именем файла DBF по полям которого и строятся индексные ключи

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

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

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


Индекс- это один тег структурного индексного файла

Типы (виды) индексов

В FoxPro в настоящий момент различают четыре типа (вида) индексов

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

Очень много недоразумений возникает из-за контроля уникальности данных в индексе типа Candidat. Типичные ошибки, заключаются в следующем:
-) Пустое значение (одни пробелы) - это тоже значение, поэтому невозможно создать 2 записи с пустыми значениями. Это будет воспринято как попытка ввода 2 одинаковых значений.
-) Установка ограничения SET DELETED ON - не есть физическое удаление записей помеченных как удаленные. Это всего-лишь наложение специфичекого фильтра, который делает такие записи "невидимыми", но тем не менее они по прежнему существуют в таблице. Поэтому попытка ввода новой записи со значениями, которые есть в одной из записей помеченных как удаленная также будет рассматриваться как ввод дублирующего значения.
Primary Можно сказать, что данный тип - это частный случай индекса типа Candidat. Он обладает всеми свойствами индекса типа Candidat, но с дополнительными ограничениями. Данный тип индекса может быть только один в каждой таблице и данный тип индекса может быть только у таблиц включенных в базу данных. Если таблица с индексом типа Primary исключается из базы данных, то индекс типа Primary автоматически конвертируется в тип Candidat.

Строго говоря, никакой дополнительной функциональности, с точки зрения целостности данных индекс типа Primary по сравнению с индексом типа Candidat не дает. Однако факт его наличия облегчает процесс проектирования базы данных. Дело в том, что по умолчанию предполагается, что индекс типа Primary построен по ключевому полю таблицы. Соответственно в тех визуальных средствах программирования, где необходимо указание ключевого поля (например, View Designer на закладке Update Criteria) FoxPro автоматически предлагает считать ключевым то поле, по которому построен индекс типа Primary.
Regular Это самый распространенный тип индексов. Его использование не предполагает никаких особых ограничений на содержимое таблицы. Можно сказать, что это обычный (простой) индекс
Unique Данный тип индекса не запрещает ввод в таблицу одинаковых значений, однако учитывает (отображает) только одно (самое первое) из введенных одинаковых значений. Можно сказать, что это своеобразный фильтр, который отсекает повторяющиеся значения.

Отдельного упоминания заслуживает использование команды APPEND BLANK применительно к таблицам, по которым построены индексы типа Primary или Candidat.

По умолчанию, команда APPEND BLANK создает новую запись, где все поля имеют пустое значение. Но пустое значение - это тоже значение. Поэтому, если Вы дадите две команды APPEND BLANK подряд, то получите сообщение о нарушении уникальности индекса. Чтобы этого избежать необходимо создавать новую запись с не пустым и уже уникальным значением. Это можно сделать одним из следующих способов:

  • Вместо APPEND BLANK использовать INSERT-SQL указав заранее созданные уникальные значения
  • Использовать специальную функцию, генерирующую новые уникальные значения, вызов которой организовать из DEFAULT поля, по которому создан индекс типа Primary или Candidat.

Контроль уникальности в триггерах не сработает, поскольку проверка уникальности индекса выполняется ДО проверки триггеров. Т.е. проверять в триггерах в этом случае уже поздно.


Режим сортировки индексов (Collate)

Настройка SET COLLATE определяет режим сортировки символьных строк. Иными словами, какой символ надо поставить первым, а какой вторым, при упорядочивании.

По умолчанию, в FoxPro используется режим сортировки MACHINE. Это такой порядок сортировки, когда символы выстраиваются в соответствии с их ASCII-кодами. Чтобы понять что это означает (т.е. в каком порядке будут сортироваться символьные данные) посмотрите таблицу ASCII кодов. Это можно сделать так:

  
  CREATE CURSOR curASCII (nASC   I, cCHR   C(1))  
  FOR m.lnI=1 TO 255  
         INSERT INTO curASCII (nASC,cCHR) VALUES (m.lnI, CHR(m.lnI))  
  ENDFOR  
  BROWSE NOWAIT  
 

Обратите внимание, что сначала идут большие буквы и только потом маленькие. Кроме того, применительно к буквам русского алфавита, выпадает буква "ё" (ASCII-код 184) и "Ё" (ASCII-код 168). Именно в таком порядке и будут следовать символьные строки.

Если используется какой-нибудь национальный режим сортировки, например RUSSIAN, то различия между большими и маленькими буквами игнорируются и все буквы национального языка выстраиваются по алфавиту без разрывов. Чтобы понять как изменится порядок сортировки выполните следующий код, используя полученный ранее курсор

  
  SET COLLATE TO 'RUSSIAN'  
  select curASCII  
  INDEX ON cCHR TAG cCHR  
  BROWSE NOWAIT  
 

Как видите, буквы русского языка выстроились строго по алфавиту игнорируя разделение на большие и маленькие буквы и буква "Ё" заняла надлежащее ей место после "Е". Можно заметить и другие отличия, но здесь я их рассматривать не буду.

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

Таким образом внутри одного индексного файла могут быть индексы созданные в разных режимах сортировки. Проверить режим сортировки в котором был создан индекс можно при помощи функции IDXCOLLATE()

Однако я бы не советовал на первых порах экспериментировать с SET COLLATE. Оставьте эту настройку в режиме по умолчанию, т.е. SET COLLATE TO 'MACHINE'. Этому есть причины.

  • В версиях FoxPro младше 6 ServicePack 5 запросы Select-SQL теряли некоторые числовые значения если была установлена сортировка отличная от MACHIN. Т.е. эта ошибка сохранялась вплоть до Visual FoxPro 6 Service Pack 4 и была исправлена только с выходом Service Pack 5 к 6 версии.
  • При использовании Private DataSession установка SET COLLATE - это одна из тех установок, которая сбрасывается в значение по умолчанию. Вследствии чего, ее надо устанавливать повторно каждый раз при открытии Private DataSession
    Полный список настроек, сбрасываемых в значения по умолчанию при использовании Private DataSession можно почитать в описании к команде SET DataSession
  • При оптимизации используются только те индексы, которые созданы в том же режиме сортировки, что и текущий режим сортировки системы.
  • В подавляющем большинстве случаев, вместо использования режима сортировки SET COLLATE TO 'RUSSIAN' можно использовать режим сортировки MACHINE с индексным ключем UPPER(MyField) или LOWER(MyField). Применительно к русским буквам эффект будет тот же (за исключением букв "ё" и "Ё")

Метод половинного деления

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

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

Запись Значение
1 500
2 300
3 200
4 400
5 100


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

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

Значение Запись
100 5
200 3
300 2
400 4
500 1


А теперь посмотрим как поиск записи со значением 200 приблизительно будет выглядеть в индексе в случае использования метода половинного деления.

-) На первом этапе определяются начальные и конечные значения. В данном случае - это 100 и 500. Значение 200 находится между ними.

-) Вычисляется среднее арифметическое от граничных значений: (100+500)/2=300 и берется ближайшее значение из списка значений к вычисленному среднему. В данном случае это то же самое значение 300

-) Теперь смотрим в какой половине находится искомое значение 200. Оно находится в интервале от 100 до 300

-) Вычисляется среднее арифметическое этого нового интервала: (100+300)/2=200 и берется ближайшее значение из списка значений к вычисленному среднему. В данном случае это то же самое значение 200.

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

А теперь сравним, сколько шагов необходимо сделать в случае простого сканирования и в случае использования метода половинного деления

Предельно допустимое количество записей в DBF-таблице - это 1 миллирад (1 billion) записей (это единица и девять нулей). Значит при прямом сканировании таблицы в предельном случае может понадобиться просканировать весь миллирад записей. Т.е. сделать миллиард операций.

А в случае половинного деления количество операций определяется значением степени в которую следует возвести число 2, чтобы превысить миллирад (логарифм от миллиарда по основанию 2). Это число 30, поскольку 2**30=1,073,741,824. Т.е. в предельном случае для поиска значения в индексе потребуется не более 30 шагов

Выигрыш в производительности очевиден: миллирад против тридцати.

Замечание: Подчеркну еще раз: приведенный алгоритм - это всего лишь общая схема. В реальности и способ хранения данных в индексном файле и способ поиска несколько отличаются


Использование индексов для отображения данных

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

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

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

Однако это вовсе не означает, что индексы для упорядочивания записей не используются. Дело в том, что любая таблица используемая в FoxPro может быть проиндексирована. Это относится как к обычным таблицам, так и к результатам выполнения команд Select-SQL, Local View и Remote View.

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

Некоторые особенности создания индексов для временных таблиц

  • Если курсор, созданный командой Select-SQL имеет статус Read-Only, то для него можно построить только один индексный тэг.
    По умолчанию, курсор созданный командой Select-SQL всегда имеет статус Read-Only, чтобы это изменить необходимо использовать опцию READWRITE (она появилась только в 7 версии). А для более младших версий курсор следует переоткрыть. Подробнее об этом читайте в разделе Курсор
  • Индексация View возможна только если он находится в 3 режиме буферизации (оптимистическая буферизация строк). Если View находится в 5 режиме буферизации (оптимистическая буферизация таблиц), то при попытке индексации Вы получите сообщение об ошибке.
  • Обновление содержимого View по команде Requery() также обновит и содержимое всех созданных для него индексов.
  • Если Вы создали структурный индексный файл к курсору или View, то он будет автоматически удален в момент закрытия этого курсора или View

Контроль уникальности данных при помощи индекса

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

Прежде всего, следует заметить, что индекс типа Candidat в "чистом" виде нас не устаивает по той причине, что в большинстве случаев задача контроля уникальности формулируется так: В таблице должны быть уникальны значения, если они удовлетворяют некоторым дополнительным условиям

Ну например, Вы хотите контролировать уникальность только среди записей не помеченных как удаленные.

Это можно сделать добавив в индекс FOR-условие, которое в данном случае будет выглядеть так: FOR .NOT.Deleted()

Но добавление FOR-условия в выражение индекса автоматически исключает его из списка индексов, участвующих в оптимизации. Т.е. для ускорения выборок понадобиться создать еще один индекс с тем же выражением индексного ключа, но без FOR-условия. Чтобы этот новый индекс не контролировал уникальность, он должен быть типа Regular

Как следствие, получаем "раздувание" индексного файла на "лишний" индекс.

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

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

Есть еще одно соображение, не столь принципиального характера. В случае внесения изменений в правило контроля уникальности если речь идет об индексе, то потребуется удалить старый индекс и создать новый, а если речь идет о триггере, то надо будет просто заменить файлы базы данных (DBC, DCX, DCT) на новые (с новым триггером)

Итого, контроль уникальности данных при помощи индекса типа Candidat с FOR-условием по сравнению с триггером проще в реализации, но приводит к значительно большему увеличению объема базы данных (в байтах) и изменению логики обработчика ошибок при редактировании данных.


Название индексных тегов

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

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


Сколько и каких индексов надо создавать

Вопрос крайне неоднозначный и сильно зависит от конкретной задачи, однако некоторые рекомендации все-таки можно сделать.

  • Прежде всего, Вам следует определиться в каком режиме сортировки (SET COLLATE) Вы будете работать. Дело в том, что индекс запоминает тот режим сортировки в котором он был создан и в оптимизации запросов участвуют только те индексы, которые были созданы в том же режиме сортировки, что и используемый на момент выполнения запроса.

    Например, если Вы создали индекс в режиме сортировки MACHINE, а запрос выполняется при настройке RUSSIAN, то индекс использоваться не будет, хотя казалось бы он есть. Проверить в каком режиме сортировки был создан тот или иной индекс можно используя функцию IDXCOLLATE(). При этом следует иметь в виду, что изменить режим сортировки индекса невозможно. Необходимо будет удалить "неправильный" индекс и создать новый в нужном режиме сортировки

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

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

Индексы используются для ускорения получения выборок в так назваемой Rushmore-оптимизации. Что это такое и как оно работает я здесь объяснять не будут. С точки зрения создания индексов нас интересует следующая особенность работы Rushmore-оптимизации:

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

Следствием этой особенности работы является следующий вывод


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

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

Объем информации НЕ удовлетворяющей условию < Объем индекса

Объем информации НЕ удовлетворяющей условию - это произведение количества записей не попадающих в выборку на объем в байтах одной записи.

Объем индекса - это сумма размеров индексных тэгов, участвующих в оптимизации.

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

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

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

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

Частным случаем индекса по логическому выражению является индекс по выражению Deleted(). Этот индекс используется в случае настройки SET DELETED ON для того, чтобы оптимизировать выборку на предмет отсечения записей помеченных как удаленные. Как уже было сказано чуть выше, если количество удаленных записей относительно невелико, то данный индекс приведе не к ускорению, а к замедлению выборки.

Значительно сложнее определить необходимость прочих индексов. Да, есть некоторые правила, которые говорят, что если построить такой и такой индекс, то запрос будет оптимизирован. Даже есть функция SYS(3054) при помощи которой можно установить используется ли данный индекс при оптимизации или нет (да и то не всегда из-за несовершенства функции SYS(3054)). Но как было замечено ранее: оптимизация далеко не всегда приводит к ускорению получения выборки.

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

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

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

Замечу еще, что индексы содержащие FOR-условия в оптимизации не участвуют


Собственно работа с индексами
  • В FoxPro не поддерживается значение индексного ключа переменной длины. Т.е. если в качестве выражения индексного ключа Вы напишите AllTrim(MyField), то хотя ошибки это и не вызовет, но фактически будут удалены только ведущие пробелы, а общая длина каждого значения будет дополнена концевыми пробелами до некоторой фиксированной величины. В данном случае до длины поля MyField. Поэтому, чтобы избежать различных недоразумений, лучше в таких сложных случаях самостоятельно явно указывать длину индексного ключа, например PADR(AllTrim(MyField),50)
  • По возможности, старайтесь избегать сложных выражений индексного ключа для тегов структурного индексного файла. Чем проще выражение индексного ключа - тем лучше. В идеале, лучше иметь индексный ключ состоящий из названия одного поля.
  • Индекс "запоминает" режим сортировки (SET COLLATE) при котором он был создан и при модификации исходных таблиц автоматически сортирует новые значения в "запомненном" режиме сортировки вне зависимости от текущей настройки SET COLLATE. Проверить в каком режиме сортировки был создан тот или другой тег можно функцией IDXCOLLATE()
  • На результат поиска по индексному выражению влияет настройка SET EXACT, а внутри команды SELECT-SQL аналогичная ей настройка SET ANSI
    Эти настройки определяют как будет осуществлятся поиск в случае если заданный критерий поиска отличается по длине от длины индексного ключа. По умолчанию, если заданный критерий поиска меньше длины индексного ключа, то будут найдены записи, где заданный критерий - это первые символы индексного ключа. Фактически поиск ведется по первым символам, а не по всему ключу.
    Если необходимо избежать влияния этих настроек на результат поиска (т.е. требуется строгое соответствие), то дополняйте критерий поиска нужным количеством пробелов справа используя функцию PADR(KeyValue,10)
  • Следует помнить, что изменения данных в исходной таблице приводит к немедленному изменению всех открытых в данный момент индексов и перестроению в соответствии с главным индексом. Это значит, что крайне нежелательно модифицировать те поля, которые входят в выражение индексного ключа главного индекса, поскольку это может привести к непредсказуемым последствиям. Предварительно надо или переглючится на другой индекс или вообще отключить главный индекс (SET ORDER TO 0)

    Рассмотрим следующий пример

      
      CREATE CURSOR test (testID I)  
      INSERT INTO test (testID) VALUES (2)  
      INSERT INTO test (testID) VALUES (1)  
      INDEX ON testID TAG testID  
     
    

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

      
      SELECT test  
      SCAN  
            REPLACE testID WITH testID+10  
      ENDSCAN  
     
    

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

    -) На первом шаге цикла SCAN указатель записей будет установлен на первую запись в соответсвии с главным индексом. Это запись со значением поля testID=1

    -) По команде REPLACE значение поля TestID первой записи будет увеличено на 10 и примет значение 11. Немедленно произойдет модификация индексного файла и его перестроение. Теперь эта же самая запись оказывается не первой, а самой последней

    -) На команде ENDSCAN будет предпринята попытка перейти на следующую запись, но в соответствии с новым значением индекса текущая запись уже последняя. Поэтому цикл будет завершен и запись со значением testID=2 так и останется не измененной.

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

      
      SELECT test  
      SET ORDER TO 0  
      SCAN  
            REPLACE testID WITH testID+10  
      ENDSCAN  
     
    
  • Индексный файл - это все-таки отдельный (другой) файл. Поэтому если индексный файл не открыт (командой SET INDEX или опцией ORDER в команде USE), то изменения сделанные в исходной таблице не отразятся в индексе. Это может привести к серьезным недоразумениям - запись введена, но ее не видно.

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

  • Курсор, созданный командами CREATE CURSOR или SELECT ... INTO CURSOR можно индексировать. Однако если курсор созданный командой SELECT ... INTO CURSOR имеет статус Read-Only (т.е. не была указана опция ReadWrite или он не был переоткрыт), то для такого курсора можно будет создать только один индексный тег. Если Вы создадите структурный индексный файл для таких курсоров, то этот файл будет автоматически удален в момент закрытия курсора
  • Local View и Remote View также можно индексировать если они находятся в режиме оптимистической буферизации строк (3). В режиме оптимистической буферизации таблиц (5) индексирование невозможно. Обновление содержимого View по команде Requery() также обновит и структурный индексный файл созданный для данного View. Закрытие View автоматически уничтожит и структурный индексный файл.

Опубликовал: Владимир Максимов www.foxclub.ru

Комментарии: (0) | FoxPro | 2006-06-08

FoxPro : Советы начинающим Часть II

Советы начинающим Часть II

В этой статье :

Таблица
Таблица


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

Таблица- это файл с расширением DBFи связанные с ним файлы с тем же именем, но с расширением FPT(файл для хранения полей типа Memo и General) и с расширением CDX(структурный индексный файл)

Формально, это абсолютно правильное определение. Проблема только в том, что в подавляющем большинстве случаев, когда в FoxPro употребляют термин "таблица", то под этим подразумевают вовсе не это. Точнее, не совсем это.

Таблица- это некий образ файлас расширением DBFоткрытый в указанной сессии данныхи в указанной рабочей области.

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

Алиас(alias) - это "псевдоним" файла DBFоткрытого в какой-либо рабочей области. Как правило, алиас совпадает с именем файла DBF. Однако это не всегда так. Дело в том, что в одном сеансе данных не может быть двух одинаковых алиасов. Поэтому, если алиас таблицы не указан явно при ее открытии (опция ALIAS в команде USE, или каким-либо другим способом), то FoxPro самостоятельно назначит уникальный алиас для таблицы, начав разумееется с алиаса совпадающего с именем файла DBF если это возможно.

Имейте в виду, что в абсолютном большинстве случаевпод термином "таблица"подразумевается именно "образ файла", т.е. файл уже открытый через команду USE (или каким-либо еще способом) в среде FoxPro. Если же подразумевается именно файл DBF, то как правило это оговаривается особо.

В версиях FoxPro 2.x в том смысле, в котором используется термин "таблица"использовался термин "база данных"(видимо отсюда пошло расширение - первые буквы английской фразы DataBase File), поскольку в тех версиях еще не существовало файла DBC. Соответственно, когда программисты переходят на версию Visual FoxPro, то их бывает достаточно трудно понять из-за этой путаницы с терминами.

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

Рабочая область(Work area) - это некий числовой идентификатор, который может быть присвоен таблице. Если у Вас был опыт программирования в других языках, то можно сказать, что рабочая область - это "хэндл" или "дескриптор" таблицы внутри среды FoxPro

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

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

Кроме понятия "рабочая область" в FoxPro введено понятие "сеанс данных"(DataSession)

Сеанс данных (DataSession)- это некоторая динамическая копия среды FoxPro. Открывая среду FoxPro Вы автоматически открываете сеанс данных, который автоматически же и завершается при выходе из FoxPro. Но внутри собственно FoxPro Вы имеете возможность сделать как бы копию среды FoxPro используя так называемые "частные сеансы данных" (Private DataSession)

Что собственно дает эти "частные сеансы данных"? А дает это возможность симулировать внутри одного приложения FoxPro работу нескольких, независимых друг от друга пользователей.

В результате таблицы открытые в одном сеансе данных "не видны" в другом сеансе данных. И соответственно манипуляции (не все) производимые с таблицами в одном сеансе данных не влияют на другие сеансы данных.

Самый распростарненный случай применения Private DataSession- это одновременное открытие нескольких форм, рассматривающих один и тот же документ с разных сторон. Как правило, для этой цели между таблицами устанавливается связь по SET RELATION. Если открыть подобные формы в одном сеансе данных, то зачастую это становится большой проблемой, поскольку в одной форме требуется наложить на таблицы одни индексы и связи, а в другой - другие. И переключение из одной формы в другую приводит к непредсказуемым изменениям содержимого.

Название таблицы

Файл таблицы, как и любой другой файл в системе Windows может содержать до 128 символов, содержать пробелы, русские символы, цифры и некоторые спец.символы. Однако для упрощения работы в FoxPro я бы порекомендовал следующие ограничения в наименовании файла таблицы
  • Не использовать в названии русские символы - причина этой рекомендации в том, что FoxPro разрабатывался прежде всего для англоязычных пользователей и использование в нем символов другого языка - это уже последующее дополнение. Как следствие, велик риск, что чего-то, где-то недосмотрели и при определенных ситуациях русские буквы в имени вызовут неожиданные глюки
  • Не использовать в названии пробелы - в принципе, ошибок использование пробелов не вызовет, но несколько усложнит сам процесс программирования, поскольку имена и пути доступа, содержащие пробелы необходимо заключать в кавычки. Просто добавит лишней заботы - не забывать кавычки. А зачем усложнять себе жизнь, когда без этого легко можно обойтись.
  • Ограничивайте длину названия 8 символами и не используйте в названии цифр и спец.символов - в отличии от аналогичной рекомендации в отношении наименования файла база данных этому есть причина. Причина не настолько явная, чтобы ее описать в двух словах. Но цепочка рассуждений приведшая к этой рекомендации основана на рекомендации по наименованию ключевых полей таблиц и наименований индексных тэгов. Прочтя эти разделы Вам станет понятна причина этой рекомендации.
  • Не называйте таблицу также как и одно из его полей - разумеется ошибки это не вызовет, но усложнит понимание написанного кода самим программистом. Не всегда с ходу можно однозначно определить, что речь идет именно о таблице, а не о поле таблицы. А если еще и их названия совпадают, то совсем тяжело становится.
  • Не используйте для названия одно из зарезервированных в FoxPro слов - опять же, ошибки это не вызовет, но резко снизит "читабельность" кода. Ведь зарезервированные слова автоматически подсвечиваются опеределенным цветом (если Вы используете стандартный текстовый редактор FoxPro) и с ходу становится проблематично отличить опцию или команду от имени таблицы
  • Не используйте псевдонимы таблицы внутри базы данных - в данном случае речь идет о том, что внутри базы данных можно присвоить таблице псевдоним, отличный от имени файла DBF. Речь не идет об опции ALIAS в команде USE. Это несколько другое. Если Вы войдете в режим модификации структуры таблицы, и перейдете на закладку "Table", то увидите, что в опции "Name" стоит имя, совпадающее с именем файла DBF. Вот это-то имя и можно изменить, присвоив таблице некоторый "псевдоним" по которому и будут обращаться к указанной таблице. Лично я не рекомендовал бы новичкам использование подобных псевдонимов, поскольку это может внести путаницу в сам процесс программирования.

    Расположение таблицы

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

    Причины этой рекомендации подробно изложены в разделе Где расположить файлы проекта. Вкратце, суть сводится к тому, что в противном случае возрастает риск непреднамеренной порчи файлов данных и соответственно потере данных. А также облегчается поиск нужных файлов и создание резервной копии.
  • Желательно файл базы данных располагать в той же папке, где и включенные в него файлы DBF

    По большому счету, конечно можно держать файл базы данных в одной директории, а включенные в него файлы DBF в другой. Но это усложняет сам процесс разработки проекта. Например, создание резервной копии в простейшем случе заключается в простом копировании директории с рабочими файлами в другое место. Если же рабочие файлы отделены от файла базы данных, то потребуется уже копирование 2-х директорий. Соответственно усложнится код.

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

    Собственно работа с таблицами

  • У объекта Grid при указании значения для RecordSourceType под термином "таблица" (Table) подразумевают как раз-таки именно файл DBF, а под термином "алиас" (Alias) - образ файла. Что вызывает огромное количество проблем у новичков с этим объектом. Ни в коем случае не используйте в качестве RecordSourceType указание "Table" - это приведет к непредсказуемому поведению данного объекта. Оставьте значение по-умолчанию "Alias"

    [li]Как уже было замечено выше, таблицы всегда открываются в конкретной рабочей области и для перехода в нужную рабочую область есть 2 способа адресации: либо по номеру этой рабочей области, либо по имени алиаса (alias) таблицы открытой в этой рабочей области.

    Так вот, я бы рекомендовал всегда адресоваться к рабочей области именно по имени алиаса (alias) таблицы, а не по номеру.

    Причина этой рекомендации в том, что конкретной рабочей области абсолютно все-равно, какая именно таблица в ней открыта. А при определенных условиях таблица может быть переоткрыта, но уже в другой рабочей области. Соответственно, адресуясь к рабочей области по ее номеру невозможно быть до конца уверенным, что в ней открыта именно нужная таблица. Да и вообще, что в ней открыта хоть какая-нибудь таблица. С другой стороны, обращение по алиасу с большей вероятностью укажет на нужную таблицу (тут тоже могут быть варианты, но это уже более экзотические случаи)
  • Крайне нежелательно динамически в процессе работы модифицировать таблицы или добавлять/удалять таблицы в базе данных. Это сопряжено с большими проблемами и значительным усложнением программного кода.

    Рабочая область с номером 0

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

    Такая адресация позволяет делать несколько вещей

    Во-первых, это позволяет открывать новые таблицы не заботясь о том, не занята ли текущая рабочая область другой таблицей. Т.е. дается команда вида
  
  USE MyTable IN 0  
 


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

Другое применение нулевой рабочей области - это настройки по умолчанию.

Например, Вы вероятно уже знаете, что любое Viewпо-умолчанию открывается в режиме оптимистической буферизации строк (3), но если Вам необходимо использовать его в режиме оптимистической буферизации таблиц (5), то необходимо после его открытия сделать это переключение используя функцию CursorSetProp()примерно так
  
  USE MyView IN 0  
  =CursorSetProp('buffering',5,'MyView')   
 


Однако используя нулевую рабочую область можно сделать глобальную настройку для открытия всех талиц в 5 режиме буферизации примерно так:
  
  =CursorSetProp('buffering',5,0)  
  USE MyView IN 0   
 


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

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

Большая таблица

Очень часто в конференциях проскакивает словосочетание "большая таблица".

Я бы сказал, что понятие "большая таблица"весьма субъективно. По моим наблюдениям, в большинстве случаев, под "большой" понимают такую таблицу, выполнение операций чтения/записи с которой занимает ощутимо заметное время. Заметное для пользователя.

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

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

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

Курсор


В очередной раз вспоминается лень американцев и их стремление все сокращать (впрочем русские здесь ушли еще дальше - могут сказать почти все используя только несколько специфических слов). Термин "курсор"употребляется сразу в нескольких смыслах в зависимости от контекста.

Курсор- это образ файла DBF открытого в одной из рабочих областей

Курсор- это временная таблица являющаяся результатом выполнения команды Select-SQL

Курсор- это указательположения индикатора ввода текста с клавиатуры

Ну, последнее определение не очень-то интересно. В том смысле, что здесь все ясно, кроме того, почему этот термин был использован еще и для временных таблиц, ведь слово "cursor"собственно и переводится как "указатель".

Курсор как образ файл DBF

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

Замечу еще, что курсор, как объект, используется не только как образ файлов DBF, но и как образ View. А View и таблица - это не одно и то же.

Курсор как временная таблица

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

Первый способ- это использование команды CREATE CURSOR. Созданный таким способом курсор будет редактируемым. И это будет именно временная таблица, т.е. она будет автоматически уничтожена в момент закрытия. Ну про этот способ сказать особо нечего. Здесь нет каких-то проблем и особенностей

Второй способ- это использование опции CURSORв команде SELECT-SQL. Примерно в следующем синтаксисе
  
  SELECT * FROM MyTable INTO CURSOR TmpTable  
 


Вот этот-то TmpTable и есть курсор

В зависимости от различных условий этот курсор может иметь разное физическое "воплощение" и разные свойства

Если SQL-запрос полностью оптимизируем, то вместо создания нового файла будет просто открыта та же самая таблица с наложенным на нее фильтром. Зачастую это очень неприятная неожиданность. Проверить, чем же физически является сформированный курсор, можно используя функцию DBF()
  
  SELECT * FROM MyTable INTO CURSOR TmpTable  
  ?DBF('TmpTable')   
 


Если будет возвращено имя файла с расширением DBF, то данный курсор является той же самой исходной таблицей с наложенным на нее фильтром.

Если Вы хотите при любых запросах быть уверенными, что курсор - это именно временная таблица, а не исходная таблица с наложенным фильтром, то Вам следует добавить опцию NOFILTER
  
  SELECT * FROM MyTable INTO CURSOR TmpTable NOFILTER  
 


Эта опция появилась тольков 5 версии Visual FoxPro, хотя там она еще не была документирована. В более ранних версиях необходимо добавлять фиктивные условия или признаки группировки, чтобы исключить возможность оптимизации.

Однако если курсор - это временная таблица, то это еще не значит, что эта временная таблица будет непременно физически расположена на диске. Вполне возможно, что вся временная таблица целиком поместится в оперативную память. Т.е. функция DBF('TmpTable')будет исправно показывать некий временный файл, но попытка найти его физически на диске окончится неудачей и функция FILE(DBF('TmpTable'))вернет .F.

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

Еще один немаловажный вопрос связан с тем, что полученные таким образом курсоры нельзя редактировать. Они доступны только на чтение. Начиная с 7 версии Visual FoxPro для решения этой проблемы появилась специальная опция ReadWrite
  
  SELECT * FROM MyTable INTO CURSOR TmpTable NOFILTER READWRITE  
 


Использование этой опции позволяет создавать курсор, который можно редактировать. Для более младших версий FoxPro для того, чтобы курсор можно было редактировать его следует переоткрыть
  
  SELECT * FROM MyTable INTO CURSOR TmpReadTable NOFILTER  
  USE (DBF('TmpReadTable')) IN 0 AGAIN ALIAS TmpWriteTable  
  USE IN TmpReadTable   
 


Переоткрытый таким образом курсор TmpWriteTableуже можно будет редактировать

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

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

Формирование имени курсора в команде Select-SQL

Это не такой простой вопрос, как может показаться. Проблема здесь в том, что имя курсора - это фактически алиас (alias) временной таблицы. Но в FoxPro в одном сеансе данных не может быть открыто 2 таблиц с одинаковыми алиасам.

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

Ну например, Вы открыли 2 формы использующих Default DataSessionи в обоих создали курсор с одинаковым именем. В этом случае, курсор созданный позднее затрет курсор созданный ранее. При этом настройка SET SAFETYне играет никакой роли. Курсор будет пересоздан молча. Без каких-либо дополнительных запросов.

Избежать подобных конфликтов можно несколькими способами
  • Открывать формы и отчеты только в Private DataSession
  • Самостоятельно следить за уникальностью имен курсоров
  • Использовать функцию для генерации уникальных имен файлов
    Последний вариант кажется наиболее предпочтительным. Однако тут следует быть осторожным. Дело в том, что в описании к FoxPro для генерации уникальных имен файлов предлагается использовать следующую функцию
  
  lcCursorName=SubStr(SYS(2015),3,10)  
 


Проблема в том, что функция SYS(2015)может содержать в возвращаемом значении как буквы, так и цифры. Это значит, что при использовании выделения строки по SubStr() Вы вполне можете получить первым символом цифру. А использование в качестве имени переменной цифры в синтаксисе FoxPro недопустимо и Вы неожиданно получите сообщение о синтаксической ошибке. Чтобы этого избежать следует либо принудительно подмешать букву
  
  lcCursorName='t'+SubStr(SYS(2015),3,10)  
 


Либо вообще не выделять строку
  
  lcCursorName=SYS(2015)  
 


Соответсвенно выполнение запроса станет выглядеть так:
  
  LOCAL lcCursorName  
  lcCursorName=SYS(2015)  
  SELECT * FROM MyTable INTO CURSOR &lcCursorName NOFILTER   
 


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

Поля таблицы


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

Название полей таблицы

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

    Ну, например, если в таблице необходимо указать сумму платежа и сумму налога, то Вы конечно можете создать 2 поля Platezh1 и Platezh2. Но в этом случае, вам каждый раз придется вспоминать, что собственно обозначает цифра 1, а что цифра 2. Если Вы работаете постоянно только с одним проектом, то это не страшно, как-нибудь да запомните. Но если Вы отложили этот проект и вернулсь к нему через несколько месяцев, то напряженные размышления на тему - а что это собственно такое? - Вам обеспечены. Гораздо разумнее дать значимые имена: Platezh и Nalog
  • Если по данному полю Вы создаете простой индексный тэг, выражение которого состоит только из имени поля, то ограничивайте название поля 10 символами - причина здесь в том, что количество символов в названии индексного тэга не может быть больше 10. Это значит, что Вам придется указать в качестве названия индексного тэга что-то отличное от названия поля, по которому этот индекс построен. В принципе, ничего страшного. Однако если имя тэга и имя поля совпадают, то это сильно упрощает процесс программирования и позволяет в некоторых случаях создавать универсальный программный код не зависящий от использования конкретной таблицы.
  • Не называйте таблицу также как и одно из его полей - разумеется ошибки это не вызовет, но усложнит понимание написанного кода самим программистом. Не всегда с ходу можно однозначно определить, что речь идет именно о таблице, а не о поле таблицы. А если еще и их названия совпадают, то совсем тяжело становится.
  • Не используйте для названия одно из зарезервированных в FoxPro слов, в особенности те слова, которые используются в команде Select-SQL - это может вызвать сообщение о синтаксической ошибке, для подавления которой придется сильно усложнить программный код. Кроме того, это снизит "читабельность" кода. Ведь зарезервированные слова автоматически подсвечиваются опеределенным цветом (если Вы используете стандартный текстовый редактор FoxPro) и с ходу становится проблематично отличить опцию или команду от имени поля таблицы.

    Если воображение Вам напрочь отказывает и Вы не знаете как по другому назвать поле кроме как например "Order" или "Group", то добавьте в качестве первого символа букву, обозначающую тип данных, используемых в данном поле. Например, "nOrder" или "cGroup"
  • В некоторых книгах рекомендуется в качестве первого символа имени поля всегда указывать букву, обозначающую тип данных, использующийся в данном поле. Я бы не рекомендовал этого делать, по той причине, что FoxPro - это регистро-независимый язык. Т.е. ему все-равно большие или маленькие буквы используются в именах. Как следствие, все команды и функции FoxPro возвращающие какие-либо имена возвращают их либо в верхнем (большими буквами), либо в нижнем (маленькими буквами) регистре. При таком написании название воспринимается как одно целое слово без смыслового разбиения. Т.е. первая буква не воспринимается как тип данных, а воспринмается просто как начало слова.

    Собственно работа с полями таблицы

  • Крайне нежелательно динамически в процессе работы модифицировать поля таблицы или добавлять/удалять поля. Это сопряжено с большими проблемами и значительным усложнением программного кода.

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

    Дело в том, что если алиас не указан, то FoxPro предполагает, что речь идет о поле таблицы, расположенной в текущей рабочей области. А если у таблицы в текущей рабочей области нет такого поля, то о переменной памяти с тем же именем. Но при написании относительно сложной программы далеко не всегда можно с уверенностью сказать, что мы находимся в нужной рабочей области. Явное указание алиаса таблицы снимает эту проблему.
  • Заполняйте раздел "Comment" для всех полей таблицы в дезайнере таблиц. Написание комментариев, хотя бы минимальное, в любом случае очень полезная вещь. Этот текст автоматически отображается в окне самого проекта (Project), когда указатель встает на соответствующее поле таблицы. Да и документирование базы данных упрощается. Можно использовать этот текст (через функцию DBGetProp()) при выдаче сообщений об ошибках.


    Ключевое поле

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

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

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

    Начну сразу с вывода:
    Для большинства задач в FoxPro удобно использовать в качестве ключевого поля суррогатный ключ типа Integer. Ключевое поле желательно вводить для всех без исключения таблиц базы данных

    Ну а теперь рассмотрим как же я дошел до выводов таких

    Естесственные или Суррогатные ключи

    До сих пор не утихают споры о том, что лучше использовать: суррогатные или естесственные ключи.

    Естесственный ключ - это поле или набор полей, которые имеют некий физический смысл. Ну например, табельный номер, номер паспорта, и т.п.

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

    Рассмотрим какие преимущества и недостатки имеют естесственные и суррогатные ключи

    Фактически самый главный и определяющий критерий по которому можно судить о том, пригодно ли данное поле для использования его в качестве ключевого или нет - это однозначность идентификации записи. Здесь имеется в виду, действительно ли значение выбранного поля для каждой записи уникально?

    Ну с суррогатным ключем все понятно - мы сами формируем его значение без участия со стороны пользователя, поэтому можем проследить за уникальностью, а вот как тут у естесственного ключа?

    На первый взгляд кажется, что тоже все в порядке. Разве может номер паспорта быть не уникальным? Или табельный номер? Оказывается еще как может!

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

    Например, если речь идет о некотором цифро-буквенном номере (номер паспорта) и пользователь ввел "123 АБВ", а надо было "423 АБВ", то синтаксически это правильно, но по содержанию - это ошибка. Если впоследствии окажется что теперь надо ввести новый номер паспорта, но уже "123 АБВ", то программа откажется это сделать, поскольку такой номер уже есть. А на что его исправить неизвестно, поскольку документов, с которых он был введен уже нет.

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

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

    В одной из конференций, один из посетителей выразился по этому поводу достаточно эмоционально
  
  1. ИНН может быть одинаковым у разных организаций. Не верите? Я тоже не верил...   
  2. ИНН может быть разным у одной и той же организации.   
  3. У одного и того же человека может быть два разных номера паспорта.   
  4. У одного и того же человека могут быть разные фамилии.   
  5. У одной и той же организации могут быть разные наименования (в разное время года :) )   
  6. Количество детей, конечностей, зубов и даже папилярные линии... МОГУТ ИЗМЕНЯТЬСЯ!!!   
 


Я отдаю предпочтение СК просто потому, что СК предоставляет возможность пользователю решать, Иванов И.И. и Петров И.И. - один и тот же человек или разные. Может быть, он сменил фамилию, может быть даже пол, может быть он сменил и тип паспорта, и его номер. Может быть, он сменил гражданство, вернулся с войны без рук, ног и головы, наплодил детей, сделал пластическую операцию по изменению веса... Но от этого он не перестал быть самим собой.

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

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

Дело в том, что главным аргументом приверженцев естесственного ключа является его "понятность" пользователю. Т.е. предполагается, что пользователь что-то ищет опираясь на значение ключевого поля. Иными словами, пользователь сам вводит, исправляет и просматирвает значение ключевого поля.

Но в отношении суррогатного ключа - такое его использование просто недопустимо! Ну не должен пользователь знать как там внутри программы все "тикает". Пользователю интересно показание часов, а не вские там "шестеренки". Если Вы хотите предоставить пользователю некую аббревиатуру (краткое название, "ник"), то это ни в коем случае не должен быть суррогатный ключ. Введите для этой цели еще одно дополнительное поле.
Есть и еще один, более хитрый аргумент, в пользу хотя бы частичного использования естесственных ключей. Дело в том, что очень часто возникает необходимость в некоторой внутренней классификации. Ну например, если речь идет о документах, то они могут находится в некоторых взаимоисключающих сотояниях:
  
  1 - Получено  
  2 - Отложено  
  3 - Утверждено  
 


Есть очень большое искушение не делать дополнительную таблицу с этими 3 записями, а просто использовать коды 1,2,3 Ну действительно, ну не может же пользователь изменить количество и название состояний. Вот тут приверженцы естесственного ключа и поднимают голос - дескать, что говорят программисту какие-то цифирки, пускай уж сразу слова пишет

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

Какой тип данных использовать: Character или Integer

Раньше, когда для хранения числовых данных в FoxPro существовали только поля типа Numericперевес в аргументации склонялся в пользу использования полей типа Character, но с появлением полей типа Integerвсе стало не так однозначно

При сравнении способа хранения ключевого поля в символьном или числовом формате выдвигаются 3 аргумента

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

    Числовые поля легче формировать

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

    Замечу еще, что не стоит для генерации нового значения ключа использовать именно определение максимального значения в текущей таблице. Это хорошо в однопользовательском режиме, но в многопользовательском Вы рискуете получить 2 одинаковых значения ключа при одновременном добавлении новой записи двумя пользователями одновременно. Обычно используют специальную служебную таблицу, хранящуюю значение последнего использованного (или первого не использованного) значения ключа. Примеры использования такой таблицы приведены в стандартных проектах примеров FoxPro: Solution.pjx (форма NewID.scx) и TasTrade.pjx. А в 8 версии FoxPro появились автоинкрементные поля, которые совсем упростили данную задачу.

    Символьные поля "экономичнее", т.е. можно уместить больше значений в том же размере

    Начнем с вопроса, а сколько вообще необходимо значений для идентификации вообщех всех записей таблицы?

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

    Поле типа Integer может принимать знаячение в диапазоне от -2,147,483,647 до 2,147,483,647. Ну, отрицательные значения как правило не используются, но и положительные значения в 2 раза больше, чем максимально возможное количество записей. С учетом возможного удаления записей - в самый раз.

    Поскольку поле типа Integer физически занимает 4 байта (4 символа), то посмотрим, сколько же значений может быть присвоено при таком же размере для символьного поля

    В одном байте может быть записано 256 значений, т.е. это составит 256**4=4,294,967,296. Но поскольку некоторые значения нельзя использовать по ряду соображений (например, символ перевода строки, Esc и т.п.), то получается, что в смысле количества значений поля типа Integer ничуть не уступает полю типа Caracter(4), даже пожалуй несколько превосходит

    Замечание

    Следует заметить, что в FoxPro поля типа Numeric храняться как символьные поля, т.е. для хранения каждой цифры нужен один байт. Это значит, что если предполагаемое количество значений в данной таблице не превышает тысячи (меньше 4 символов), то возникает искушение "сэкономить" и вместо типа Integer ввести скажем поле типа N(2)

    Так вот, я бы не советовал этого делать по следующим соображениям:

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

    Символьные поля "универсальнее" при так назваемых задачах репликации

    Репликация - это объединение информации из двух не связанных между собой баз данных, например, из двух филиалов одной организации территориально удаленных друг от друга

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

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

  • генерация нового значения числового ключа проще, чем символьного
  • количество значений ключа для типа Integer и Chracter(4) практически одинаково
  • при решении сложных задач репликации удобнее пользоваться символьными ключевыми полями
    Но поскольку большинству программистов не придется сталкиваться с задачами репликации, то можно смело использовать для ключевых полей тип Integer.

    Надо ли использовать ключевое поле во всех без исключения таблицах

    На первый взгляд, вопрос может показаться странным. Разве можно без ключевого поля? Оказывается, в некоторых случаях можно.

    Например, для организации связи много-ко-многим стандартным способом является создание таблицы-посредника. Что имеется в виду?

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

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

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

    Если вернуться к примеру с контрагентами и банками, то легко заметить, что я обошел вниманием тот момент, что один контрагент может иметь несколько счетов в одном и том же банке. Этот самый реквизит (счет контрагента в банке) невозможно прицепить ни к банку, ни к контрагенту. Но он очень удачно подходит к этой таблице-посреднику. Если бы для идентификации записи в этой таблице Вы опирались бы на пару: код банка - код контрагента, то Вам пришлось бы серьезно переделывать значительную часть программы. А в случае существования собственного кода записи никаких проблем. Ну добавили еще одно поле, ну и что?

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

    Название ключевого поля


    Поскольку ключевое поле - это обычное поле таблицы, то на него распространяются все рекомендации приведенные в разделе "Поля таблицы". Однако поскольку это все-таки очень специфическое поле, то для него я бы добавил следующие рекомендации
  • Образуйте название ключевого поля таблицы добавив к имени таблицы 2 буквы "ID" (от слова identifier - идентификатор), отбросив букву "s" если имя таблицы - это слово во множественном числе - Например, если вы назвали таблицу контрагентов "Partners", то ключевое поле будет назваться "PartnerID". При таком способе наименования однозначно можно сказать к какой таблице относится ключевое. Но не стоит назвать ключевое поле также как и собственно таблицу, поскольку в некоторых случаях станет весьма проблематично сходу определить о чем идет речь - о поле или собственно о таблице
  • Называйте внешние ключи также как и соответствующие ключевые поля - такой способ наименования внешних ключей очень облегчает понимание о чем собственно идет речь при написании программы.
  • Ограничивайте название ключевого поля 10 символами - причина здесь в том, что количество символов в названии индексного тэга не может быть больше 10. А по ключевому полю обязательно следует построить индекс. Если количество символов в ключевом поле будет больше 10, то название индексного тэга будет отличаться от названия ключевого поля. А это не очень хорошо в том смысле, что серьезно затруднит программирование, поскольку использовать этот индекс Вы будете сплошь и рядом.

    Кстати, из этой рекомендации вместе с самой первой рекомендацией по наименованию ключевых полей вытекает, что количество символов в имени таблицы не должно превышать 8 (или 9, если название таблицы - это множественное число)

    Собственно работа с ключевыми полями таблицы


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

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

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

    Дело в том, что любая информация, которую вводит пользователь по определению является не надежной и как бы Вы ни защищали информацию, пользователь найдет как ее обойти или просто заставит Вас это сделать! А то, о чем он не подозревает и испортить не может.
  • Не пытайтесь навесить на ключевые поля какие-либо еще функции кроме однозначной идентификации записи.

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

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

Опубликовал: Владимир Максимов www.foxclub.ru

Комментарии: (0) | FoxPro | 2006-06-08

FoxPro : Советы начинающим Часть I

FoxPro : Советы начинающим Часть I


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

Как правило, большинство книг по программированию являются либо пересказом статей Help к языку, либо набором комиксов по типу "нажмите эту кнопочку увидите такую картинку, теперь нажмите эту кнопочку ...". Нельзя сказать, что это плохо или не нужно. Просто между двумя этими крайностями образовался провал, в котором и пропадает множество новичков. Поэтому любая книга, которая хоть как-то его закрывает обычно пользуется повышенным спросом.

О каком "провале" собственно идет речь?

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

Второй разрыв - это когда и что лучше всего применять. Обычно изложение строится таким образом: для решения задачи сделаем так, так и вот так. Но не предпринимается даже попытки объяснить, а почему собственно не иначе, когда есть другой способ? Как следствие, когда новичек узнает о том, что одну и ту же задачу можно решить даже не двумя, а тремя, четыремя и более способами у него в голове начинается полная карусель. Бросает из одной крайности в другую.

Есть и еще одна проблема, связанная с предыдущими двумя. Обычно в FoxPro начинают разбираться люди, уже попробовавшие свои силы в программировании на других языках (чаще всего в Delphi или Basic, да даже программисты работавшие ранее в FoxPro for DOS) и они пытаются применить стиль программирования хорошо (или не очень) им известного языка в Visual FoxPro и очень удивляются сталкиваясь с неожиданными (в смысле - не ожидАемыми) проблемами: вот ведь, в руководстве написано, что это можно, а у меня не выходит! А проблема оказывается в самом стиле программирования. Кое-какие приемы, хорошо работающие в Delphi для FoxPro являются попросту неприменимы.

Вот я и попытаюсь заполнить этот "провал" и описать некоторые рекомендации по программированию на FoxPro, с пояснениями почему собственно желательно делать так, а не иначе.
Комментарии: (0) | FoxPro | 2006-06-08

Алгоритмы сортировок

Сравнительная скорость работы некоторых нижеприведенных алгоритмов сортировки:


Примечание:
size: размер сортируемой последовательности
n: количество сортировок для замера времени
*: RadixSort в последнем тесте прогонялся при параметрах:
size=21000; n=100

----- ----- ----- ----- ----- -----


1. Пузырьковая сортировка(простым выбором, линейная)

Скачать: [attachmentid=987]
Код
Type
arrType = Array[1 .. n] Of Integer;

Procedure Bubble(Var ar: arrType; n: integer);
Var i, j, T: Integer;
Begin
For i := 1 To n Do
For j := n DownTo i+1 Do
If ar[Pred(j)] > ar[j] Then { < }
Begin
T := ar[Pred(j)]; ar[Pred(j)] := ar[j]; ar[j] := T
End
End;


Реализация пузырьковой сортировки на ассемблере:
Код
procedure BubbleSort(Mas: Pointer; Len: LongWord);
asm
dec Len
@CycleExt:
xor ebx,ebx
mov ecx,Len
mov esi,0
@CycleIn:
mov edi,Mas[esi]
cmp edi,Mas[esi+4]
jg @Exchange
add esi,4
loop @CycleIn
jmp @Check
@Exchange:
mov ebx,Mas[esi+4]
mov Mas[esi+4],edi
mov Mas[esi],ebx
add esi,4
loop @CycleIn
@Check:
cmp ebx,0
je @Exit
jmp @CycleExt
@Exit:

end;


Сложность этого метода сортировки составляет О(n^2)


2. Сортировка простой вставкой

Скачать: [attachmentid=988]
Код
Type
arrType = Array[1 .. n] Of Integer;

Procedure Insert(Var ar: arrType; n: Integer);
Var i, j, T: Integer;
Begin
For i := 1 To n do
Begin
T := ar[i];
j := Pred(i);
While (T < ar[j]) and (j > 0) Do
Begin
ar[Succ(j)] := ar[j]; Dec(j);
End;
ar[Succ(j)] := T;
End;
End;

Сложность О(n^2)


3. Сортировка слияниями
Код
Type
arrType = Array[1 .. n] Of Integer;

Procedure merge(Var ar: arrType; n: Integer);

Procedure Slit( k, q: Integer );
Var
m: Integer;
i, j, T: Integer;
d: arrType;
Begin
m := k + (q-k) div 2;
i := k; j := Succ(m); t := 1;
While (i <= m) and (j <= q) Do
Begin
If ar[i] <= ar[j] Then
Begin
d[T] := ar[i]; Inc(i)
End
Else
Begin
d[T] := ar[j]; Inc(j)
End;
Inc(T)
End;

While i <= m Do
Begin
d[T] := ar[i]; Inc(i); Inc(T)
End;

While j <= q Do
Begin
d[T] := ar[j]; Inc(j); Inc(T)
End;

For i := 1 to Pred(T) Do
ar[Pred(k+i)] := d[i]
End;

Procedure Sort(i, j: Integer);
Var
T: integer;
Begin
If i >= j Then Exit;

If j-i = 1 Then
Begin
If ar[j] < ar[i] Then
Begin
T := ar[i]; ar[i] := ar[j]; ar[j] := T
End
End
Else
Begin
Sort(i, i + (j-i) div 2);
Sort(i + (j-i) div 2 + 1, j);
Slit(i, j)
End;
End;

Begin
Sort(1, n);
End;

Сложность О(n*logn), самая быстрая из сортировок ,но использует в 2 раза больше оперативной памяти.


4. Быстрая сортировка Хоара
Это улучшенный метод, основанный на обмене. При "пузырьковой" сортировке производятся обмены элементов в соседних позициях. При пирамидальной сортировке такой обмен совершается между элементами в позициях, жестко связанных друг с другом бинарным деревом. Ниже будет рассмотрен алгоритм сортировки К. Хоара, использующий несколько иной механизм выбора значений для обменов. Этот алгоритм называется сортировкой с разделением или быстрой сортировкой. Она основана на том факте, что для достижения наибольшей эффективности желательно производить обмены элементов на больших расстояниях.

Предположим, что даны N элементов массива, расположенные в обратном порядке. Их можно рассортировать, выполнив всего N/2 обменов, если сначала поменять местами самый левый и самый правый элементы и так далее, постепенно продвигаясь с двух сторон к середине. Это возможно только, если мы знаем, что элементы расположены строго в обратном порядке.

Рассмотрим следующий алгоритм: выберем случайным образом какой-то элемент массива (назовем его x). Просмотрим массив, двигаясь слева направо, пока не найдем элемент a[i]>x (сортируем по возрастанию), а затем просмотрим массив справа налево, пока не найдем элемент a[j]<x. Далее, поменяем местами эти два элемента a[i] и a[j] и продолжим этот процесс "просмотра с обменом", пока два просмотра не встретятся где-то в середине массива.

После такого просмотра массив разделится на две части: левую - с элементами меньшими (или равными) x, и правую - с элементами большими (или равными) x. Итак, пусть a[k] (k=1,...,N) - одномерный массив, и x - какой-либо элемент из a. Надо разбить "a" на две непустые непересекающиеся части а1 и а2 так, чтобы в a1 оказались элементы, не превосходящие x, а в а2 - не меньшие x.

Рассмотрим пример. Пусть в массиве a: <6, 23, 17, 8, 14, 25, 6, 3, 30, 7> зафиксирован элемент x=14. Просматриваем массив a слева направо, пока не найдем a[i]>x. Получаем a[2]=23. Далее, просматриваем a справа налево, пока не найдем a[j]<x. Получаем a[10]=7. Меняем местами a[2] и a[10]. Продолжая этот процесс, придем к массиву <6, 7, 3, 8, 6> <25, 14, 17, 30, 23>, разделенному на две требуемые части a1, a2. Последние значения индексов таковы: i=6, j=5. Элементы a[1],....,a[i-1] меньше или равны x=14, а элементы a[j+1],...,a[n] больше или равны x. Следовательно,разделение массива произошло. Описанный алгоритм прост и эффективен, так как сравниваемые переменные i, j и x можно хранить во время просмотра в быстрых регистрах процессора. Наша конечная цель - не только провести разделение на указанные части исходного массива элементов, но и отсортировать его. Для этого нужно применить процесс разделения к получившимся двум частям, затем к частям частей, и так далее до тех пор, пока каждая из частей не будет состоять из одного единственного элемента. Эти действия описываются следующей программой. Процедура Sort реализует разделение массива на две части, и рекурсивно обращается сама к себе...


Код
Type
arrType = Array[1 .. n] Of Integer;

{ первый вариант : }
Procedure HoarFirst(Var ar: arrType; n: integer);

Procedure sort(m, l: Integer);
Var i, j, x, w: Integer;
Begin

i := m; j := l;
x := ar[(m+l) div 2];
Repeat

While ar[i] < x Do Inc(i);
While ar[j] > x Do Dec(j);
If i <= j Then
Begin
w := ar[i]; ar[i] := ar[j]; ar[j] := w;
Inc(i); Dec(j)
End

Until i > j;
If m < j Then Sort(m, j);
If i < l Then Sort(i, l)

End;

Begin
sort(1, n)
End;

{ второй вариант : }
Procedure HoarSecond(Var ar: arrType; n: Integer);

Procedure Sort(m, l: Integer);
Var i, j, x, w: Integer;
Begin
If m >= l Then Exit;
i := m; j := l;
x := ar[(m+l) div 2];

While i < j Do
If ar[i] < x Then Inc(i)
Else If ar[j] > x Then Dec(j)
Else
Begin
w := ar[i]; ar[i] := ar[j]; ar[j] := w;
End;
Sort(m, Pred(j));
Sort(Succ(i),l);
End;

Begin
Sort(1, n)
End;

Сложность O(n*logn), на некоторых тестах работает быстрее сортировки слияниями ,но на некоторых специально подобранных работает за O(n^2).


5. Пирамидальная - турнирная- HeapSort сортировка

Код
Type
arrType = Array[1 .. n] Of Integer;

Procedure HeapSort(Var ar: arrType; n: Integer);
Var
i, Left, Right: integer;
x: Integer;

Procedure sift;
Var
i, j: Integer;
Begin
i := Left; j := 2*i; x := ar[i];
While j <= Right Do
Begin
If j < Right Then
If ar[j] < ar[Succ(j)] Then Inc(j);

If x >= ar[j] Then Break;
ar[i] := ar[j];
i := j; j := 2 * i
End;

ar[i] := x
end;

Var T: Integer;
Begin
Left := Succ(n div 2); Right := n;
While Left > 1 Do
Begin
Dec(Left); sift
End;

While Right > 1 Do
Begin
T := ar[ Left ]; ar[ Left ] := ar[ Right ]; ar[ Right ] := T;
Dec(Right); sift
End
End;

Сложность O(n*logn), самая стабильная сортировка, на любых входных данных работает за одинаковое время. Но зато немного медленнее чем слияниями и быстрая.

Материал подготовил(и): volvo

Распределяющая сортировка - RadixSort - цифровая - поразрядная

Пусть имеем максимум по k байт в каждом ключе (хотя за элемент сортировки вполне можно принять и что-либо другое, например слово - двойной байт, или буквы, если сортируются строки). k должно быть известно заранее, до сортировки.
Разрядность данных ( количество возможных значений элементов ) - m, также должна быть известна заранее и постоянна. Если мы сортируем слова, то элемент сортировки - буква, m = 33. Если в самом длинном слове 10 букв, k = 10.
Обычно мы будем сортировать данные по ключам из k байт, m=256.

Пусть у нас есть массив source из n элементов по одному байту в каждом.

Для примера можете выписать на листочек массив source = { 7,9,8,5,4,7,7 }, и проделать с ним все операции, имея в виду m=9.

I. Составим таблицу распределения. В ней будет m ( = 256 ) значений и заполняться она будет так:
Код
for i := 0 to Pred(255) Do distr[i]:=0;
for i := 0 to Pred(n) Do distr[source[i]] := distr[[i]] + 1;


Для нашего примера будем иметь distr = ( 0, 0, 0, 0, 1, 1, 0, 3, 1, 1 ), то есть i-ый элемент distr[] - количество ключей со значением i.

II. Заполним таблицу индексов:

Код
index: array[0 .. 255] of integer;
index[0]:=0;
for i := 1 to Pred(255) Do index[i]=index[i-1]+distr[i-1];


В index[i] мы поместили информацию о будущем количестве символов в отсортированном массиве до символа с ключом i.

Hапример, index[8] = 5 : имеем 4, 5, 7, 7, 7, 8.

А теперь заполняем новосозданный массив sorted размера n:
Код
for i := 0 to Pred(n) Do
  Begin
    sorted[ index[ source[i] ] ]:=source[i];
    { попутно изменяем index уже вставленных символов, чтобы
       одинаковые ключи шли один за другим: }
    index[ source[i] ] := index[ source[i] ] +1;
  End;


Итак, мы научились за O(n) сортировать байты. А от байтов до строк и чисел - 1 шаг. Пусть у нас в каждом числе - k байт.

Будем действовать в десятичной системе и сортировать обычные числа ( m = 10 ).
Цитата
сначала они в сортируем по младшему на один
беспорядке: разряду: выше: и еще раз:
523 523 523 088
153 153 235 153
088 554 153 235
554 235 554 523
235 088 088 554



Hу вот мы и отсортировали за O ( k*n ) шагов. Если количество возможных различных ключей ненамного превышает общее их число, то поразрядная 'сортировка' оказывается гораздо быстрее даже 'быстрой сортировки'!

Реализация алгоритма "распределяющей" сортировки:

Скачать:
Код
Const
n = 8;

Type
arrType = Array[0 .. Pred(n)] Of Byte;

Const
m = 256;
a: arrType =
(44, 55, 12, 42, 94, 18, 6, 67);

Procedure RadixSort(Var source, sorted: arrType);
Type
indexType = Array[0 .. Pred(m)] Of Byte;
Var
distr, index: indexType;

i: integer;
begin
fillchar(distr, sizeof(distr), 0);
for i := 0 to Pred(n) do
inc(distr[source[i]]);

index[0] := 0;
for i := 1 to Pred(m) do
index[i] := index[Pred(i)] + distr[Pred(i)];

for i := 0 to Pred(n) do
begin
sorted[ index[source[i]] ] := source[i];
index[source[i]] := index[source[i]]+1;
end;
end;

var
b: arrType;
begin
RadixSort(a, b);
end.


Материал подготовил(и): klem4

Пузырьковая сортировка с просеиванием

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

Приимущество: простой метод пузырька работает крайне медленно, когда мин/макс (в зависимости от сортировки) элемент массива стоит в конце, этот алгоритм намного быстрее.

Код
const n=10;
var x:array[1..n] of integer;
i,j,t:integer;
flagsort:boolean;

procedure bubble_P;
begin
repeat
flagsort:=true;
for i:=1 to n-1 do
if not(x[i]<=x[i+1]) then
begin
t:=x[i];
x[i]:=x[i+1];
x[i+1]:=t;
j:=i;

while (j>1)and not(x[j-1]<=x[j]) do
begin
t:=x[j];
x[j]:=x[j-1];
x[j-1]:=t;
dec(j);
end;
flagsort:=false;
end;
until flagsort;
end;


Добавлено: Тестировалось на массиве целых чисел (25000 элементов). Прирост скорости относительно простой пузырьковой сортировки - около 75%...

Материал подготовил(и): volvo

Древесная сортировка (TreeSort)

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

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

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

Код
Const n = 8;
Type
TType = Integer;
arrType = Array[1 .. n] Of TType;

Const
a: arrType =
(44, 55, 12, 42, 94, 18, 6, 67);

(* Сортировка с помощью бинарного дерева *)
Type
PTTree = ^TTree;
TTree = Record
a: TType;
left, right: PTTree;
End;

{ Добавление очередного элемента в дерево }
Function AddToTree(root: PTTree; nValue: TType): PTTree;
Begin
(* При отсутствии преемника создать новый элемент *)
If root = nil Then
Begin
root := New(PTTree);
root^.a := nValue;
root^.left := nil;
root^.right := nil;
AddToTree := root; Exit
End;

If root^.a < nValue Then
root^.right := AddToTree(root^.right, nValue)
Else
root^.left := AddToTree(root^.left, nValue);
AddToTree := root
End;


(* Заполнение массива *)
Procedure TreeToArray(root: PTTree; Var a: arrType);
Const maxTwo: Integer = 1;
Begin
(* При отсутствии преемников рекурсия остановится *)
If root = nil Then Exit;

(* Левое поддерево *)
TreeToArray(root^.left, a);
a[maxTwo] := root^.a; Inc(maxTwo);

(* Правое поддерево *)
TreeToArray(root^.right, a);
Dispose(root)
End;

(* Собственно процедура сортировки *)
Procedure SortTree(Var a: arrType; n: Integer);
Var
root: PTTree;
i: Integer;
Begin
root := nil;
For i := 1 To n Do
root := AddToTree(root, a[i]);
TreeToArray(root, a)
End;

Var i: Integer;
Begin
WriteLn('До сортировки:')
For i := 1 To n Do Write(a[i]:4);
WriteLn;

SortTree(a, n);

WriteLn('После сортировки:')
For i := 1 To n Do Write(a[i]:4);
WriteLn
End.


Общее быстродействие метода O(n*logn). Поведение неестественно, устойчивости, вообще говоря, нет.
Основной недостаток этого метода - большие требования к памяти под дерево. Очевидно, нужно n места под ключи и, кроме того, память на 2 указателя для каждого из них.

Поэтому TreeSort обычно применяют там, где:
  1. построенное дерево можно с успехом применить для других задач;
  2. данные уже построены в "дерево";
  3. данные можно считывать непосредственно в дерево. Hапример, при потоковом вводе с консоли или из файла.
Т.е. там, где не требуется дополнительной памяти...

Материал подготовил(и): klem4

Сортировка методом поиска нового номера
, в новый массив:

Краткая теория: Последовательно для каждого элемента массива вычисляется его новая позиция в отсортированном массиве, рассчитывается кол-во элементов , значения которых
1) < значения анализируемого
2) значения которых = значению анализируемого элемента и номера которых <= номера анализируемого.

Особенности: Требуется дополнительный массив, не чувствительный к изначальной упорядоченности.

Оценка числа операций : N*N

type
TArr = array[1..100] of integer;

var
mass1,NewMass : TArr;
n : integer;

{
n-размерность массива, mass1 - исходный массив,
NewMass - удет состоять из отсотртированных элементов массива mass1
}

procedure NewNSort(var mass,Nmass:TArr; size:integer);
var
i,j,NewN : integer;

begin
for i:=1 to size do begin
NewN:=0;
for j:=1 to size do
if (mass[j]<mass[i])or((mass[j]=mass[i])and(j<=i)) then inc(NewN);
Nmass[NewN]:=mass[i];
end;
end;



Пример использования :

NewNSort(mass1,NewMass,n);


Массив NewMassбудет состоять из элементов массива mass1, но уже отсортированный.

На небольших массивах работает неплохо.

Тесты на скорость (в условных единицах):

1. (набор данных - массив из 8 элементов типа integer)

Количество тестов: n = 4 000 000
#1: 292 (метод нового номера)
#2: 558 (сортировка пузырьком)
#3: 490 (поразрядная сортировка - radixsort)

2. (набор данных - массив из 800 элементов типа integer)

Количество тестов: n = 225
#1: 95 (метод нового номера)
#2: 174 (сортировка пузырьком)
#3: 2 (поразрядная сортировка - radixsort)

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


Материал подготовил(и): klem4

Метод последовательного поиска минимумов

Теория: Просматривается весь массив, ищется минимальный элемент и ставится на место первого, "старый" первый элемент ставится на место найденного
type
TArr = array[1..100] of integer;

var
mass1 : TArr;
n : integer;

procedure NextMinSearchSort(var mass:TArr; size:integer);
var
i,j,Nmin,temp:integer;
begin
for i:=1 to size-1 do begin
nmin:=i;
for j:=i+1 to size do
if mass[j]<mass[Nmin] then
Nmin:=j;

temp:=mass[i];
mass[i]:=mass[Nmin];
mass[Nmin]:=temp;
end;
end;


Вызов:
NextMinSearchSort(mass1, n);


Тесты на скорость (в условных единицах):

1. (набор данных - массив из 15 элементов типа integer)

Количество тестов: n = 1 000 000
#1: 159 (метод нового номера)
#2: 127 (поразрядная сортировка - radixsort)
#3: 61 (метод поиска минимумов)

2. (набор данных - массив из 800 элементов типа integer)

Количество тестов: n = 225
#1: 107 (метод нового номера)
#2: 1 (поразрядная сортировка - radixsort)
#3: 25 (метод поиска минимумов)

3. (набор данных - массив из 10000 элементов типа integer)

Количество тестов: n = 9
#1: 597 (метод нового номера)
#2: 2 (поразрядная сортировка - radixsort)
#3: 147 (метод поиска минимумов)
Комментарии: (0) | Pascal & Delphi | 2006-06-07

Защищаем Apache 2. Шаг за шагом

Защищаем Apache 2. Шаг за шагом

Артур Май
При выборе Web сервера, Apache очень часто побеждает своих конкурентов из-за стабильности, высокой производительности, открытого исходного кода и множеством других преимуществ. Сейчас Apache существует в виде двух версий - устойчивая версия 1.3, используемая миллионами пользователей и, с другой стороны, усовершенствованная и перепроектированная версия 2.0.

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

Продолжая серию предыдущих статей (Apache, PHP, MySQL), в этой статье мы расскажем о пошаговой установке и конфигурировании Apache 2.0, чтобы снизить риск неавторизованного доступа или успешного взлома в случае применения новой уязвимости, обнаруженной в Apache Web сервере. В результате, можно будет пользоваться новыми особенностями Apache Web сервера 2.0, не слишком волнуясь о новых ошибках защиты, которые могут представлять серьезную угрозу

Функциональные требования

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

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

Поэтому, перед установкой Apache 2, очень важно знать, какие функциональные возможности мы действительно ожидаем от Web сервера. Это позволит нам подготовить список модулей, которые мы оставим включенными, а остальные будут отключены в процессе установки.

Согласно этому правилу, мы предполагаем, что будут использоваться только следующие основные особенности Apache 2:

  1. Обрабатываться будут только статические HMTL страницы.
  2. Сервер должен поддерживать механизм виртуального хостинга.
  3. Доступ к некоторым Web страницам может быть ограничен по IP адресам или пользователям (basic authentication).
  4. Сервер должен регистрировать все Web запросы (включая информацию о web браузере).
Обратите внимание, что вышеупомянутые функциональные возможности не поддерживают CGI сценарии, SSL протокол или другие полезные особенности Apache сервера. Это сделано так, потому что главная цель статьи состоит в том, чтобы представить общий метод защиты Apache 2.0, не сосредотачиваясь на специфическом выполнении. Если есть потребность в дополнительных функциональных возможностях, читатели
  • могут использовать представленное решение как отправную точку, и расширить его, включая дополнительные модули, например mod_ssl, mod_cgi и тд.

    Предположения защиты

    Чтобы обеспечить наиболее возможный уровень защиты, и в то же самое время сделать это решение переносимым среди различных Linux/BSD систем, мы будем использовать следующие уровни защиты:

    Операционная система

    • операционная система должна быть укреплена в максимально возможной степени; все ненужные компоненты должны быть удалены из системы.
    • Операционная система не должна позволять выполнять программы на стеке (если поддерживается).
    • Все ненужные сетевые службы должны быть заблокированы.
    • Число SUID/SGID файлов должно быть минимизировано.

    Apache web server

    • Включены быть только абсолютно необходимые модули Apache; остальное должно быть заблокировано в процессе компиляции
    • Должны быть выключены все диагностические web-страницы и автоматическая служба индексации каталога.
    • Cервер должен раскрыть наименьшее количество количества информации о себе насколько возможно - политика запутывания. Хотя это - не реальный уровень защиты, его применение делает возможные проникновения трудно осуществимыми.
    • Web сервер должен выполнятся под выделенным UID/GID, который не используется другими системными процессами.
    • Apache процесс должен иметь ограниченный доступ к файловой системе (chrooting).
    • В Apache chrooted среде не должно присутствовать никаких программных оболочек (/bin/sh, /bin/csh и т.п.) - это позволяет намного усложнить процесс выполнения вредоносного кода.
    Установка операционной системы Прежде всего, мы должны выбрать операционную систему, на которой будет выполняться Web сервер. Основная часть этой статьи описывает защиту Apache на FreeBSD (5.1), однако читатели могут свободно использовать их любимую Unix, BSD, Linux или Linux-подобную операционную систему.

    Относительно наших предположений защиты, после установки операционной системы она должна быть защищена против удаленных и локальных нападений. Независимо от выбора UNIX/Linux/BSD дистрибутива, очень важно установить только основную операционную систему и удалить любые избыточные пакеты и применять на современном уровне исправления к ядру и всему установленному программному обеспечению.

    Также рекомендуют периодически синхронизировать локальное время с доверенным сервером времен, используя часы с сервера времени, которому доверяют, используя Network Time Protocol (NTP), и посылать журналы регистрации удаленному, выделенному регистрационному серверу.

    После того, как система подготовлена, мы можем начать устанавливать Apache 2.0. Первым шагом мы должены добавить новую группу и правильного пользовател,я названного Apache. Пример для FreeBSD показан ниже:

    pw groupadd apache
    pw useradd apache -c "Apache Server" -d /dev/null -g apache -s /sbin/nologin
    
    Дочерние Apache процессы должны выполнятся с привилегиями группы и пользователя apache. вышеупомянутая учетная запись будет выделена Apache Web серверу, это поможет обеспечить разделение привилегий и избежать потенциальных проблем защиты, когда несколько различных процессов выполняются под той же самой учетной записью, например под пользователем nobody.

    Загрузка программного обеспечения

    Далее, нам необходимо загрузить последнюю версию Apache Web сервера из Web сайта Apache. Так как мы хотим отключить ненужные модули в процессе компиляции, очень важно загрузить исходный код Apache. Также важно проверить загруженное программное обеспечение против PGP сигнатуры, чтобы удостовериться, что загруженная версия немодифицирована.
    lynx http://httpd.apache.org/download.cgi
        
    gpg --import KEYS
    gpg httpd-2.0.49.tar.gz.asc
        gpg: Good signature from "Sander Striker "
    tar zxvf httpd-2.0.49.tar.gz
    cd ./httpd-2.0.49/
    

    Выбор Apache модулей

    После того, как распакован исходный код Apache, мы должны выбрать, какие модули останутся, и какие должны быть удалены. Краткое описание всех модулей, доступных в Apache 2.0, могут быть найдены в http://httpd.apache.org/docs-2.0/mod/. Выполняя функциональные возможности и требования защиты, принятые в начале этой статьи, мы компилируем только следующие модули:

    Имя модуля

    Описания

    core

    Основное ядро Apache, необходимое для инсталляции.

    http_core

    Основное HTTP ядро, необходимое для Apache 2.0 инсталляции.

    prefork

    Модуль мультизадачного режима (MPM), для обеспечения многозадачной работы.

    mod_access

    Обеспечивает управление доступом, основанным на имени хоста клиента, IP-адресе и других характеристиках запроса клиента. Поскольку этот модуль необходим, чтобы использовать директивы "order", "allow" и "deny", он должен оставаться доступным.

    mod_auth

    Требуется для осуществления пользовательской идентификации (базовая HTTP идентификация).

    mod_dir

    Требуется, для поиска и обслуживания каталога с индексными файлами: "index.html", "default.htm", и т.д.

    mod_log_config

    Требуется для регистрации запросов, сделанных на сервер.

    mod_mime

    Требуется для установки набора символов, content encoding, обработчика, content-language, и документов MIME типа.

    Так как мы хотим использовать только минимальное число модулей, мы компилируем все модули статически. Благодаря этому, мы устраним возможность применения уязвимости еще в одном модуле - mod_so.

    Компилирование и установка программного обеспечения

    В этом шаге мы конфигурируем, компилируем, и устанавливаем Apache Web сервер следующим образом:
    ./configure  
    --prefix=/usr/local/apache2  
    --with-mpm=prefork  
    --disable-charset-lite  
    --disable-include  
    --disable-env  
    --disable-setenvif  
    --disable-status  
    --disable-autoindex  
    --disable-asis  
    --disable-cgi  
    --disable-negotiation  
    --disable-imap  
    --disable-actions  
    --disable-userdir  
    --disable-alias  
    --disable-so 
    make 
    su 
    umask 022 
    make install 
    chown -R root:sys /usr/local/apache2
    
    
    После того, как Apache установлен, мы должны удостовериться, что используются только следующие модули:
     /usr/local/apache2/bin/httpd -l 
    Compiled in modules: 
      core.c 
      mod_access.c 
      mod_auth.c 
      mod_log_config.c 
      prefork.c 
      http_core.c 
      mod_mime.c 
      mod_dir.c
     
    

    Конфигурирование Apache

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

    Таким образом, мы должны удалить/usr/local/apache2/conf/httpd.conf файл и создать новый httpd.conf в его месте, со следующим содержанием:

    # =================================================
    # Basic settings
    # =================================================
    Listen 0.0.0.0:80
    User apache
    Group apache
    ServerAdmin webmaster@www.ebank.lab    
    UseCanonicalName Off
    ServerSignature Off
    HostnameLookups Off
    ServerTokens Prod
    ServerRoot "/usr/local/apache2"
    DocumentRoot "/www"
    PidFile /usr/local/apache2/logs/httpd.pid
    ScoreBoardFile /usr/local/apache2/logs/httpd.scoreboard
    
        DirectoryIndex index.html
    
    
    # =================================================
    # HTTP and performance settings
    # =================================================
    Timeout 300
    KeepAlive On
    MaxKeepAliveRequests 100
    KeepAliveTimeout 15
    
    
        MinSpareServers 5
        MaxSpareServers 10
        StartServers 5
        MaxClients 150
        MaxRequestsPerChild 0
    
    
    # =================================================
    # Access control
    # =================================================
    
        Options None
        AllowOverride None
        Order deny,allow
        Deny from all
    
    
        Order allow,deny
        Allow from all
    
    
    
        Order allow,deny
        Allow from all
    
    
    # =================================================
    # MIME encoding
    # =================================================
    
        TypesConfig /usr/local/apache2/conf/mime.types
    
    DefaultType text/plain
    
    
        AddEncoding x-compress .Z
        AddEncoding x-gzip .gz .tgz
        AddType application/x-compress .Z
        AddType application/x-gzip .gz .tgz
        AddType application/x-tar .tgz
    
    
    # =================================================
    # Logs
    # =================================================
    LogLevel warn
    LogFormat "%h %l %u %t "%r" %>s %b "%{Referer}i" "%{User-Agent}i"" combined
    LogFormat "%h %l %u %t "%r" %>s %b" common
    LogFormat "%{Referer}i -> %U" referer
    LogFormat "%{User-agent}i" agent
    ErrorLog /usr/local/apache2/logs/error_log
    CustomLog /usr/local/apache2/logs/access_log combined
    
    # =================================================
    # Virtual hosts
    # =================================================
    NameVirtualHost *
    
           DocumentRoot "/www/www.ebank.lab"
           ServerName "www.ebank.lab"
           ServerAlias "www.e-bank.lab"
           ErrorLog logs/www.ebank.lab/error_log
           CustomLog logs/www.ebank.lab/access_log combined
    
    
    
           DocumentRoot "/www/www.test.lab"
           ServerName "www.test.lab"
           ErrorLog logs/www.test.lab/error_log
           CustomLog logs/www.test.lab/access_log combined
    
    
    По сравнению с заданным по умолчанию файлом конфигурации, были сделаны следующие важные изменения:
    • Уменьшено до минимума число допускаемых модулей
    • Процессы Apache (кроме rootпроцесса) установлены, чтобы выполнятся с уникальными привилегиями пользователя/группы.
    • Apache раскрывает наименьшее количество информации о себе насколько это возможно.
    • Установлены более ограниченные права доступа к содержанию сайта.
    Согласно нашим требованиям, вышеупомянутая конфигурация предполагает, что есть два виртуальных хоста, поддержавшие Apache:
    • www.ebank.lab(псевдоним:www.e-bank.lab)
    • www.test.lab
    Содержание вышеупомянутых виртуальных хостов физически хранятся под /www каталогом, поэтому перед запуском Apache, мы также должны создать соответствующие каталоги с типовыми web-страницами:
    mkdir -p /www/www.ebank.lab
    mkdir -p /www/www.test.lab
    echo "eBank.labeBank.lab 
         works!" > /www/www.ebank.lab/index.html
    echo "test.labTest.lab 
         works!" > /www/www.test.lab/index.html
    chmod -R 755 /www 
    chown -R root:sys /www
    
    
    Мы должны также подготовить каталоги для хранения журналов регистраций:
    mkdir -p /usr/local/apache2/logs/www.ebank.lab 
    mkdir -p /usr/local/apache2/logs/www.test.lab 
    chmod -R 755 /usr/local/apache2/logs 
    chown -R root:sys /usr/local/apache2/logs 
    
    Наконец, мы можем попробовать выполнить Apache, и проверить, что все работает должным образом:
    /usr/local/apache2/bin/apachectl start
    
    Если доступен сайт www.ebank.lab через web-браузер, мы можем завершение Apache:
    /usr/local/apache2/bin/apachectl stop 
    
    И затем перейдем к chroot сервера. Если возникли проблемы, должны быть проанализированы журналы регистрации или команда truss (для BSD и Solaris пользователей) следующим образом:
    truss /usr/local/apache2/bin/httpd
    
    Обратите внимание, что для Linux пользователей, эквивалентная команда - strace. Анализ данных, представленных командами truss (или strace), могут помочь в решении возникших проблем.

    Chrooting сервера

    Далее, ограничим доступ Apache процесса к файловой системе. Техника chrooting подробно описана в предыдущей статье, поэтому в этом пункте мы просто создадим структуру директорий для нашего нового Apache:
     
    mkdir -p /chroot/httpd/dev 
    mkdir -p /chroot/httpd/etc 
    mkdir -p /chroot/httpd/var/run 
    mkdir -p /chroot/httpd/usr/lib 
    mkdir -p /chroot/httpd/usr/libexec 
    mkdir -p /chroot/httpd/usr/local/apache2/bin 
    mkdir -p /chroot/httpd/usr/local/apache2/lib 
    mkdir -p /chroot/httpd/usr/local/apache2/logs/www.ebank.lab 
    mkdir -p /chroot/httpd/usr/local/apache2/logs/www.test.lab 
    mkdir -p /chroot/httpd/usr/local/apache2/conf 
    mkdir -p /chroot/httpd/usr/local/lib 
    mkdir -p /chroot/httpd/www
    
    Владелец весь выше каталогов должен быть root, и права доступа не должны позволить обычным пользователям выполнять любые изменения в этих каталогах:
    chown -R root:sys /chroot/httpd 
    chmod -R 0755 /chroot/httpd
    
    Затем, мы создадим специальный файл устройства,/dev/null:
    ls -al /dev/null 
      crw-rw-rw- 1 root wheel 2, 2 Mar 14 12:53 /dev/null 
    mknod /chroot/httpd/dev/null c 2 2 
    chown root:sys /chroot/httpd/dev/null 
    chmod 666 /chroot/httpd/dev/null
    
    
    Мы также должны создать /chroot/httpd/dev/log устройство, которое необходимо для нормальной работы сервера. В случае нашей FreeBSD системы, нужно добавить следующую строкe к /etc/rc.conf: syslogd_flags="-l /chroot/httpd/dev/log"

    Для того, чтобы вступили в силу наши изменения, мы также должны перезапустить syslogd демон с новым параметром:

    kill `cat /var/run/syslog.pid` 
    /usr/sbin/syslogd -ss -l /chroot/httpd/dev/log 
    
    Далее скопируем все необходимые программы, библиотеки и файлы конфигурации в новое дерево каталогов. В случае FreeBSD 5.1 список требуемых файлов следующий:
    cp /usr/local/apache2/bin/httpd /chroot/httpd/usr/local/apache2/bin/ 
    cp /usr/local/apache2/lib/libaprutil-0.so.9 /chroot/httpd/usr/local/apache2/lib/ 
    cp /usr/local/apache2/lib/libapr-0.so.9 /chroot/httpd/usr/local/apache2/lib/ 
    cp /usr/local/apache2/conf/mime.types /chroot/httpd/usr/local/apache2/conf/ 
    cp /usr/local/apache2/conf/httpd.conf /chroot/httpd/usr/local/apache2/conf/ 
    cp /usr/local/lib/libexpat.so.4 /chroot/httpd/usr/local/lib/ 
    cp /usr/lib/libc.so.5 /chroot/httpd/usr/lib/ 
    cp /usr/lib/libcrypt.so.2 /chroot/httpd/usr/lib/ 
    cp /usr/lib/libm.so.2 /chroot/httpd/usr/lib/ 
    cp /usr/libexec/ld-elf.so.1 /chroot/httpd/usr/libexec/ 
    cp /var/run/ld-elf.so.hints /chroot/httpd/var/run/ 
    cp /etc/hosts /chroot/httpd/etc/ 
    cp /etc/nsswitch.conf /chroot/httpd/etc/ 
    cp /etc/resolv.conf /chroot/httpd/etc/ 
    cp /etc/group /chroot/httpd/etc/ 
    cp /etc/master.passwd /chroot/httpd/etc/passwords
    
    В случае других Unix, BSD, Linux и Linux-подобных систем, список требуемых файлов может быть определен, используя команды типа ldd, strace, , truss или strings, как было описанр в предыдущей статье. После того, как сделаны вышеупомянутые шаги, мы должны подготовить базу данных пароля, которая должна присутствовать в chrooted файловой системе. Таким образом, от /chroot/httpd/etc/passwords и/chroot/httpd/etc/group мы должны удалить все строки кроме apache. Затем, мы должны формировать базу данных пароля следующим образом:
    cd /chroot/httpd/etc 
    pwd_mkdb -d /chroot/httpd/etc passwords 
    rm -rf /chroot/httpd/etc/master.passwd
    
    Вышеупомянутые команды должны быть выполнены при использовании FreeBSD. В других системах может быть достаточно редактировать /chroot/httpd/etc/passwd и /chroot/httpd/etc/shadow файлы. Наконец, мы можем копировать типовое содержание сайта к chrooted среде:
    cp -R /www/* /chroot/httpd/www/ 
    
    И проверить корректную работу Apache Web сервера:
    chroot /chroot/httpd /usr/local/apache2/bin/httpd
    

    Заключительные шаги

    Если теперь ваш Apache работает должным образом, нам осталось создать сценарий, который запустит Apache во время начальной загрузки системы. Для этого может использоваться следующий сценарий: #!/bin/sh CHROOT=/chroot/httpd HTTPD=/usr/local/apache2/bin/httpd PIDFILE=/usr/local/apache2/logs/httpd.pid echo -n " apache" case "" in start) /usr/sbin/chroot $CHROOT $HTTPD ;; stop) kill `cat ${CHROOT}/${PIDFILE}` ;; *) echo "" echo "Usage: `basename {PAGE_ROW_TEXT}` {start|stop}" >&2 exit 64 ;; esac exit 0 Вышеупомянутый сценарий должен быть скопирован в каталог, где находятся по умолчанию сценарии запуска. В случае с FreeBSD это - /usr/local/etc/rc.d каталог. Права доступа к тому файлу должны быть установлены следующим образом:
    chown root:sys/usr/local/etc/rc.d/apache.sh 
    chmod 711/usr/local/etc/rc.d/apache.sh 
    
    

    Выводы

    Главная цель этой статьи состояла в том, чтобы представить метод защиты Apache 2.0, который позволяет читателям смягчать риск успешного взлома, даже если используется новая уязвимость. Было показано, как установить Apache с минимальным номером модулей, как установить более ограничительную конфигурацию, и как осуществить защиту против большого количества эксплоитов, выполняя Web сервер в chrooted среде, без использования любых программ оболочки. И хотя никакой метод не может предоставить 100% защиты, применяя вышеупомянутые рекомендации, будет намного труднее выполнить нападение против Apache 2.0 по сравнению с заданной по умолчанию инсталляцией.

Статья взята с сайта OpenNet

Комментарии: (0) | Безопасность | 2006-06-07


Страница 7 из 51Первая«45678910 »Последняя