Правильная ссылка на эту страницу
http://az-design.ru/Support/DataBase/SQL/CelkoJ/01h027.shtml

Глава 27. Подмножества

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

27.1. Каждый n-ый элемент таблицы

       Эту задачу прислал в журнал Explain Рори Мэрчисон, преподаватель курсов по DB2 из института Этны (Murchison n.d.). SQL представляет собой ориентированный на множества язык и не может идентифицировать индивидуальные строки по их положению в таблице. Вместо этого с помощью логических выражений обнаруживаются уникальные ключи. Если вам дан файл с описанием сотрудников не в формате SQL, и вы хотите для обзора извлечь информацию о каждом n-ом сотруднике, причем порядок следования сотрудников зависит от их идентификационных номеров, задача становится сравнительно легкой. Вы просто пишете процедуру с вложенными циклами, которая читает записи и записывает каждую n-ую запись в другой файл.
       Может показаться, что для реализации на языке SQL этой возможности надо вычислить функцию MOD(empiro, :n), где MOD — это функция модуля, присутствующая в большинстве продуктов SQL, и сохранить те строки сотрудников, где значение функции равно нулю. Проблема заключается в том, что идентификационные номера сотрудников не являются последовательными, хотя они и уникальны.
       Очень часто, хотя и не всегда, продукты разработчиков содержат идентификатор строки, используемый процедурными расширениями для этих целей. В качестве примера можно назвать Informix/SQL. Это упрощает написание кода SQL:

SELECT *
  FROM Personnel
 WHERE MOD(RowNumber, :n) = 0 
 ORDER BY empno;

       Однако такой запрос можно составить, даже если процессор БД не поддерживает идентификатора строки. Он требует соединения таблицы Personnel с собой, чтобы можно было разделить ее на вложенную серию сгруппированных таблиц. После этого в каждой группе извлекается максимальное значение. Столбец empno можно проиндексировать или наложить на него ограничение уникальности, тогда выполнение предиката EXISTS значительно ускорится. Имейте в виду, что идентификаторы строк не только не входят в стандарт, они также способны привести к проблемам при использовании в запросах с сортировкой, поскольку вы не знаете, соответствует ли идентификатор положению в строке до или после сортировки. Пользователи, просматривающие одну и ту же базовую таблицу посредством различных представлений, могут получить, а могут и не получить одни и те же идентификаторы строки для одних и тех же физических строк. Еще одна проблема связана с вводом и удалением строк. Что происходит при удалении строки или вводе в таблицу новой? Сохраняются ли идентификаторы удаленных строк?

SELECT empno
  FROM Personnel AS P1 
 WHERE EXISTS (SELECT MAX(empno)
                 FROM Personnel AS P2 
                WHERE P1.empno >= P2.empno 
               HAVING MOD(COUNT(*)- :n) = 0);

       Версия того же запроса без вложений выглядит так:

SELECT P1.empno
  FROM Personnel AS P1, Personnel AS P2
 WHERE P1.empno >= P2.empno
 GROUP BY P1.empno 
HAVING MOD (COUNT(*), :n) = 0;

27.2. Выбор строк из таблицы случайным образом

       Язык SQL не позволяет выбирать строки в таблице случайным образом. В стандарте не предусмотрена функция "случайного" выбора, и разработчики, как правило, не предоставляют никакого генератора псевдослучайных чисел.
       Очень удобно было бы выбирать из таблицы строки случайным образом для статистической обработки, в других языках эго легко сделать с помощью генератора случайных чисел. Случайная выборка из множества осуществляется двумя способами: с заменой и без замены. Если бы стандарт SQL содержал функцию случайного числа, вероятно, она имела бы вид RANDOM(х) и RANDOM (DISTINCT x). К сожалению, такой функции в SQL нет и не планируется. Проблема в том, что язык SQL ориентирован на множества и все операции делает сразу на всем правильно определенном множестве строк. Случайная выборка не является правильно определенной — это означает, что для ее конструирования приходится использовать процедуру, а не логическое выражение.
       Лучше всего осуществить такую выборку, добавив к таблице столбец для случайных чисел, а затем, воспользовавшись процедурным языком с хорошим генератором псевдослучайных чисел, загрузить случайные значения в данный столбец с помощью курсора в базовом языке. Это необходимо, так как генераторы случайных чисел из других обращений к функциям работают по-другому. Они используют начальное значение, или начальное число (seed), которое задается пользователем или системными часами. Начальное число позволяет создать первое число в последовательности, Random(1). Каждое обращение к функции использует предыдущее число для генерации следующего (Random(n+1)). Нет способа выполнить последовательность действий в SQL без курсора, поэтому вам придется работать из процедурного кода.
       Генератор псевдослучайных чисел часто называют генератором случайных чисел, но технически это неправильно. Все генераторы рано или поздно начинают повторяться, возвращая значения, уже бывшие в последовательности, и она замыкается в цикл. Все процедуры являются детерминистскими, с их помощью нельзя получить истинно случайный результат. Однако, если цикл очень большой и значения в нем соответствуют различным критериям случайной выборки, мы можем его использовать.
       Есть много типов генераторов. Семейство, работающее по принципу линейной конгруэнтности, использует следующие формулы:

Random(n + 1)  := MOD ((x * Random(n) + у),   m);

       где n — число бит в результате
       х = 3 или 5
       у — целочисленная константа
       т — любое целое число (2n)
       х и n зависят друг от друга — (n + log2(x)+1) <n
       Программистами С часто используются следующие представители этого семейства:

Random(n + 1) := (Random(n) * 1103515245) + 12345;
Random(n + 1) := MOD ((16807 * Random(n)), ((231) - 1));

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

Random(n + 1) := MOD ((48271  * Random(n)), ((231) - 1));

       Обратите внимание, что модуль стоит на первом месте. Период этого генератора составляет ((231)-2), или 2147483646, т.е. приблизительно через 2 млрд. чисел последовательность повторяется. Решите, достаточно ли это для вашего приложения.
       Если ваша реализация поддерживает функцию XOR, можно воспользоваться алгоритмами сдвига регистра. XOR представляет собой побитовое исключающее ИЛИ (OR), применимое к любому целому числу, которое может сохраняться в компьютере (полагаю, что на самых слабых компьютерах размер этого числа достигает 32 бита). Можно привести следующие полезные алгоритмы сдвига регистра:

Random(n + 1) := Random(n - 103) XOR Random(n - 250);
Random(n + 1) := Random(n - 1063) XOR Random(n - 1279);

       Но что делать, если вам надо что-либо динамически генерировать? В некоторых реализациях SQL можно использовать функции S0UNDEX() и SIMILAR(). Обе принимают строку и конвертируют ее в число.
       Убедитесь, что поставляемая в составе вашего продукта SQL функция SOUNDEX() не является оригинальной функцией Soundex — последняя создает строку из четырех символов, начинающуюся с буквы. В таком случае вам придется сократить ее и преобразовать в число.
       Функция SIMILAR() несколько отличается от SOUNDEX(), но это также строковая функция, применяемая в основном к именам. Она сравнивает две строки и выдает степень их соответствия: 100 — это точное соответствие символов и их положений, а 0 — отсутствие соответствия.
       Смешивая две функции, можно динамически создать грубое случайное число. При этом используется столбец типа CHAR(n) с именами или другими уникальными строками — не используйте алфавитный код! В таком столбце будет много дубликатов. Например, к таблице Personnel можно применить следующий запрос:

SELECT empnum, empname,
       ABS(SOUNDEX(empname) + SIMILAR(empname, 'etoin')
    + SIMILAR(empname, 'shurld') + SIMILAR(empname, 'kpml')) AS random
FROM Personnel;

       В реализации WATCOM 4.0 этот запрос даст следующий ответ:

Results
empnum    empname    ranaom
 1        'Tom'         788
 5        'Dick'        367
12        'Harry'       872
13        'Melvin'    22913
14        'Mary'        877
23        'George'     2923
27        'Brad'       3943
30        'Seymour'    6910
32        'Lucy'        370
39        'Wendy'      3840
42        'Sally'       632
43        'Janet'      3833

       Некоторые функции SOUNDEX() возвращают отрицательный результат, поэтому для гарантии получения положительных величин я использую функцию абсолютных значений. Чтобы значения находились в определенном вами диапазоне, воспользуйтесь функцией MIN() или выполните другие математические преобразования. Не следует также связывать обращения к функциям SIMILAR() знаками умножения — получив ноль в одной из строк, вы уничтожите свое распределение.
       Выбор слов во втором параметре функции SIMILAR() не является случайным. Эти строки содержат самые распространенные символы английского языка. Идея состоит в гарантировании того, что для любого слова в столбце начального числа будет найдено некоторое соответствие.
       Вероятно, существует и более эффективный способ выбора бессмысленных слов для любого конкретного столбца начального числа, если только вы знаете распределение букв. Подобным образом в формуле можно использовать и несколько столбцов. Читатель может, видимо, предложить и свои версии в зависимости от его данных.
       Другой метод заключается в использовании столбцов PRIMARY KEY или UNIQUE и алгоритма хеширования. Для получения функции хеширования можно воспользоваться одним из описанных ранее генераторов случайных чисел и уникальными значениями в качестве начального числа. Алгоритмы хеширования пытаются придерживаться универсального распределения, и сумев найти подходящий алгоритм, вы очень близко подойдете к уникальному случайному распределению. Задача лишь в том, что этот алгоритм должен быть достаточно прост, чтобы можно было реализовать его с помочцью доступных в SQL ограниченных средств.

27.3. Операторы включения

       В теории множеств для подмножеств определено два символа. Один из них, <=, означает, что множество А входит в состав множества В, иногда его называют оператором правильного подмножества. Символ <= означает, что множество А входит в состав или совпадает с множеством В, его называют просто оператором подмножества или включения.
       Стандарт SQL никогда не предусматривал оператора сравнения таблиц друг с другом на равенство или включение. В некоторых учебниках по реляционным БД встречается упоминание о предикате CONTAINS, отсутствующем в стандартах SQL-89 или SQL-92. Такой предикат существовал в первой экспериментальной системе SQL компании IBM под названием System R, но затем был удален из-за того, что требовал большого количества ресурсов компьютера.

27.3.1. Операторы правильных подмножеств

       Для проверки принадлежности к множеству используется предикат IN. В теории множеств принадлежность к множеству обозначается стилизованной буквой эпсилон, причем содержащее множество располагается с правой его стороны, а £ А. Понятие принадлежности к множеству определено для одного элемента. Подмножество само представляет собой множество. В качестве примера использования предиката подмножества рассмотрим запрос, выводящий имена всех сотрудников, работающих над всеми проектами отдела 5. В соответствии с синтаксисом продукта System R мы получим:

SELECT name   -- Неправильный код SQL
  FROM Personnel
 WHERE (SELECT projectno
          FROM WorksOn
         WHERE Personnel.employeeno = WorksOn.employeeno)
      CONTAINS
       (SELECT projectno
          FROM Projects
         WHERE deptno = 5);

       Во втором операторе SELECT предиката CONTAINS создается таблица всех проектов пятого отдела. В первом операторе SELECT этого предиката содержится коррелированный подзапрос, создающий таблицу всех проектов, над которыми работает каждый сотрудник. Если таблица проектов сотрудников совпадает или входит в таблицу пятого отдела, предикат дает значение TRUE.
       Сначала надо решить, как поступать с дубликатами строк в любой или обеих таблицах. Входит ли мультимножество {а, b, b) во множество {а, b, с}, или нет? Некоторые операторы SQL, такие как UNION и SELECT, позволяют удалять дубликаты из результата или сохранять их (как в случае UNION ALL или SELECT ALL). Лично я предлагаю дубликаты игнорировать и рассматривать мультимножество как подмножество. Для примера рассмотрим таблицу сотрудников и другую таблицу с именами участников команды по боулингу, она должна быть правильным подмножеством таблицы Personnel. Для этого каждый игрок должен быть сотрудником компании, или, иными словами, не должно быть игроков, которые бы сотрудниками не были.

NOT EXISTS (SELECT * 
              FROM Bowling AS B1
             WHERE B1.empno NOT IN (SELECT empno FROM Personnel))

27.3.2. Равенство множеств

       Если два множества А и В равны, то:
       1. Оба содержат одинаковое количество элементов.
       2. Нет элементов множества А, которые не входили бы во множество В.
       3. Нет элементов множества В, которые не входили бы во множество А.
       4. Множество А равно пересечению множеств А и В.
       5. Множество В равно пересечению множеств А и В.
       6. Множество В является подмножеством множества А.
       7. Множество А является подмножеством множества В.
       Элементы 2 и 3 можно реализовать с помощью предиката NOT EXISTS().

WHERE NOT EXISTS (SELECT * 
                    FROM A 
                   WHERE A.keycol NOT IN (SELECT keycol
                                            FROM В
                                           WHERE A.keycol = В.keyed))
                     AND NOT EXISTS (SELECT * 
                                       FROM В 
                                      WHERE B.keycol NOT IN (SELECT keycol
                                                               FROM A 
                                                              WHERE A.keycol = B.keycol))

       Однако утверждения 1, 4 и 5 могут привести к следующему ответу:

WHERE (SELECT COUNT(*)
         FROM A) = (SELECT COUNT(*)
                      FROM A 
                           INNER JOIN В
                           ON A.keycol = В keycol)
  AND (SELECT COUNT(*)
         FROM B)  =  (SELECT COUNT(*)
                       FROM A
                            INNER JOIN В
                            ON A.keycol = В keycol)

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

CREATE TABLE SupParts 
   (sno   CHAR(2) NOT NULL,
    pno   CHAR(2) NOT NULL,
PRIMARY KEY (sno, pno));

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

SELECT SP1.sno AS Supplier1, SP2.sno AS Supplier2
  FROM SupParts AS SP1
       INNER JOIN SupParts AS SP2 ON (SP1.pno = SP2.pno AND SP1.sno < SP2.sno)
 GROUP BY Supplier1, Supplier2 
HAVING COUNT(*) = (SELECT COUNT(*)
                     FROM SupParts AS SP3
                    WHERE SP3.sno = SP1.sno)
   AND COUNT(*) = (SELECT COUNT(*)
                     FROM SupParts AS SP4
                    WHERE SP4.sno = SP2.sno);

       В этом решении используется несколько новых возможностей SQL-92, но его легко переписать и в соответствии с SQL-89. Если в таблице SupParts номер поставщика проиндексировать, число поставщиков можно получить непосредственно, индекс также помогает работе операции соединения.
       Не следует забывать и о проблеме NULL-значений и избыточных дубликатов значений. Если две таблицы содержат одни и те же значения, но их там разное количество, считаются они равными или нет? Иными словами, надо ли применять для теста равенства ключевые слова ALL и DISTINCT?
       В заключение хотелось бы сказать, что операторы INTERSECT и UNION стандарта SQL-92 позволяют осуществлять проверку на равенство в соответствии с любым выбранным вами определением.




<<< Пред. Оглавление
 
След. >>>

Дата последнего изменения:
Thursday, 21-Aug-2014 09:10:55 MSK


Постоянный адрес статьи:
http://az-design.ru/Support/DataBase/SQL/CelkoJ/01h027.shtml