В СУБД Oracle операции над множествами можно выполнять, как минимум, в трех контекстах с помощью трех различных механизмов. Это
- операции над битовыми полями,
- операции над вложенными таблицами,
- операции над множествами строк таблиц.
В этом порядке они и будут рассмотрены ниже, но сначала - суперкраткое введение в понятие множества.
"Множество есть совокупность отличных друг от друга объектов, мыслимая как единое целое." Когда я был первокурсником, примерно с такого определения началось мое знакомство с теорией множеств.
{1,2,3}- это множество, элементы которого числа 1, 2, 3.{1,2,3,2}- это не множество, поскольку число 2 встречается два раза.{}- это пустое множество, не содержащее элементов.
Одни множества могут быть подмножествами других множеств:
{1,2,3}есть подмножество множества{1,2,3,4,5}.{1,2,3}есть подмножество множества{1,2,3}, поскольку каждое множество является подмножеством самого себя.{}есть подмножество всякого множества.
Важно, что порядок элементов множества не задан. Поэтому {1,2,3}, {2,3,1} и {3,2,1} - это три обозначения одного и того же множества.
Помимо проверки, является ли одно множество подмножеством другого, над множествами определены следующие бинарные операции:
-
объединение двух множеств дает множество, элементами которого являются элементы обеих множеств-операндов, например:
- объединение
{1,2,3}и{4,5,6}есть{1,2,3,4,5,6} - объединение
{1,2,3}и{3,4,5}есть{1,2,3,4,5} - объединение
{}и{1,2,3}есть{1,2,3}
- объединение
-
пересечение двух множеств дает множество, все элементы которого входят в каждое из множеств-операдов:
- пересечение
{1,2,3}и{4,5,6}есть{} - пересечение
{1,2,3}и{3,4,5}есть{3} - пересечение
{}и{1,2,3}есть{}
- пересечение
-
разность двух множеств дает множество, элементы которого входят в первое множество, но не входят во второе:
- разность
{1,2,3}и{4,5,6}есть{1,2,3} - разность
{1,2,3}и{3,4,5}есть{1,2} - разность
{}и{1,2,3}есть{}
- разность
Нам также понадобится понятие мультимножество (multiset). Мультимножество - это множество, в котором допускаются одинаковые элементы. Например, {1,2,3,2} или {1,1}. Все операции над множествами применимы также к мультимножествам.
Как представляются множества в компьютере?
В простейшем случае - как последовательность - список или массив - элементов, принадлежащих множеству. Поскольку порядок элементов множества не имеет значения, то список и массив, элементы которых упорядочены, обладают семантической избыточностью. С другой стороны, они же обладают и семантической недостаточностью, поскольку позволяют в разных элементах держать одно и то же значение, что противоречит определению множества (но существенно для мультимножества). В ряде языков программирования для множества существует специальный тип данных.
В областях, где приходится интенсивно оперировать подмножествами некоторого множества, имеющего небольшое число элементов, оказывается удобным представить множество как битовое поле. В битовом поле каждый бит соответствует определенному элементу множества. При этом единичное значение бита означает наличие элемента, а нулевое значение - его отсутствие. Например,
- бит 1,
0001- яблоко - бит 2,
0010- груша - бит 3,
0100- абрикос - бит 4,
1000- слива
Тогда
| Биты | 16-ное | Множество |
|---|---|---|
0000 | 0 | пустое множество {} |
0011 | 3 | {яблоко, груша} |
1010 | A | {слива, груша} |
1111 | F | {яблоко, груша, абрикос, слива} - полное множество, подмножествами которого являются перечисленные выше. |
При представлении множества в виде битового поля операции над множествами реализуются побитовыми логическими операциями над битовыми полями. Частным случаем битового поля является целочисленный тип, например, 32-х или 64-хразрядное целое, для которого определены побитовые операции.
Рассмотрим проверку, является ли одно множество подмножеством другого.
-
Является
{абрикос,груша}подмножеством{груша, яблоко}?-
(0110 И 0011)не равно0110- не является
-
-
Является
{абрикос}подмножеством{абрикос, слива}?-
(0100 И 1100)равно1000- является
-
-
Является
{}подмножеством{абрикос, слива}?-
(0000 И 1100)равно0000- является
-
Проверка вхождения единственного элемента в множество еще проще:
-
Входит ли
абрикосв множество{груша, яблоко}?-
(0100 И 0011)дает0- не является
-
-
Входит ли
абрикосв множество{абрикос, слива}?-
(0100 И 1100)дает отличное от0значение - является
-
Продемонстрирую другие операции над множествами, представленными в виде битовых полей. Параллельно привожу целочисленное представление битовых полей:
-
Объединение {яблоко} и {груша, абрикос} есть {яблоко, груша, абрикос}
- 0001 ИЛИ 0110 дает 0111
- 1 ИЛИ 6 дает 7
-
Объединение {} и {яблоко, груша} есть {яблоко, груша}
- 0000 ИЛИ 0011 дает 0011
- 0 ИЛИ 3 дает 3
-
Пересечение {яблоко} и {груша, абрикос} есть {}
- 0001 И 0110 дает 0000
- 1 И 6 дает 0
-
Пересечение {яблоко, груша} и {яблоко, груша} есть {яблоко, груша}
- 0011 И 0011 дает 0011
- 3 И 3 дает 3
-
Разность {яблоко} и {груша, абрикос} есть {яблоко}
- (0001 ИСКЛ.ИЛИ 0110) И 0001 дает 0001
- (1 ИСКЛ.ИЛИ 6) И 1 дает 1
-
Разность {} и {яблоко, груша} есть {}
- (0000 ИСКЛ.ИЛИ 0011) И 0000 дает 0000
- (0 ИСКЛ.ИЛИ 3) И 0 дает 0
Как видим, разность множеств реализуется с помощью двух побитовых операций: вначале ИСКЛЮЧАЮЩЕЕ ИЛИ, затем И. Операция ИСКЛЮЧАЮЩЕЕ ИЛИ сама по себе дает симметричную разность двух множеств-операндов, а последующая операция И исключает из результата биты, отсутствующие в первом множестве.
Поскольку побитовые операции над целыми числами эффективно реализуются на компьютерах всех архитектур (на уровне процессора), то операции над множествами, представленными в виде битовых полей, также являются очень эффективными.
СУБД Oracle, предоставляя пользователю язык программирования четвертого поколения SQL, в то же время тщательно скрывает физические структуры представления данных. Поэтому побитовые операции в СУБД Oracle нужно еще поискать. Но поиск вознаграждается находками:
- функции пакета
UTL_RAWдля операндов с типом данныхRAW, - побитовые операции языка Java, исполняемые встроенной JVM.
Последний вариант, как более экзотический по сравнению в первым, я здесь не стану рассматривать. Хотя не составляет большого труда написать класс на языке Java со статическими методами, реализующими побитовые операции над целочисленными параметрами, и опубликовать эти методы через PL/SQL функции-обертки (см. мои статьи Java в СУБД Oracle).
Продемонстрирую побитовые "операции над множествами", реализованные в пакете UTL_RAW. Операнды и результаты функций bit_or, bit_xor и bit_and имеют тип RAW и их значения представлены в шестнадцатеричном виде:
SQL> -- Объединение {яблоко} и {груша,абрикос} есть {яблоко, груша, абрикос}
SQL> SELECT utl_raw.bit_or('01', '06') FROM dual;
UTL_RAW.BIT_OR('01','06')
--------------------------------------------------------------------------------
07
SQL> -- Пересечение {яблоко} и {яблоко, груша} есть {яблоко}
SQL> SELECT utl_raw.bit_and('01', '03') FROM dual;
UTL_RAW.BIT_AND('01','03')
--------------------------------------------------------------------------------
01
SQL> -- Разность {яблоко} и {груша, абрикос} есть {яблоко}
SQL> SELECT utl_raw.bit_and(utl_raw.bit_xor('01', '06'), '01') FROM dual;
UTL_RAW.BIT_AND(UTL_RAW.BIT_XO
--------------------------------------------------------------------------------
01
SQL> -- симметричная разность {яблоко} и {груша, абрикос} есть {яблоко, груша, абрикос}
SQL> SELECT utl_raw.bit_xor('01', '06') FROM dual;
UTL_RAW.BIT_XOR('01','06')
--------------------------------------------------------------------------------
07
Проверка, является ли множество подмножеством другого, выполняется так:
SQL> SELECT 1 FROM dual WHERE utl_raw.bit_and('03', '07') = '03';
1
----------
1
Проверка, имеют ли два множества хотя бы один общий элемент:
SQL> SELECT 1 FROM dual WHERE utl_raw.bit_and('03', '05') != '00';
1
----------
1
Другой контекст, в котором мы встречаем операции над множествами, а точнее, над мультимножествами, это операции над вложенными таблицами (nested tables). Вложенные таблицы - один из коллекционных типов данных в Oracle SQL (TABLE OF ...). Другие коллекционные типы данных - ассоциативный массив (TABLE OF ... INDEX BY ...) и массив переменной длины (VARRAY(N) OF ...).
Начиная с версии 10 СУБД Oracle поддерживает следующие операции над вложенными таблицами:
MULTISET UNION [ALL|DISTINCT]- объединение мультимножеств,MULTISET INTERSECT [ALL|DISTINCT]- пересечение мультимножеств,MULTISET EXCEPT [ALL|DISTINCT]- разность мультимножеств.
За что мне нравятся вложенные таблицы, это за возможность инициализировать их непосредственно при создании значений данного типа в SQL и PL/SQL. С ассоциативным массивом такой номер не пройдет - в PL/SQL коде придется объявлять переменную и присваивать значения каждому элементу массива отдельно.
Создам тип number_nt и продемонстрирую операции над множествами, представленными с помощью вложенных таблиц.
SQL> CREATE TYPE number_nt AS TABLE OF NUMBER;
2 /
Type created
SQL> -- инициализация вложенной таблицы при ее создании
SQL> SELECT number_nt(1,2,3,4,5) FROM dual;
NUMBER_NT(1,2,3,4,5)
--------------------------------------------------------------------------------
NUMBER_NT(1, 2, 3, 4, 5)
SQL> -- объединение {1,2,3} и {3,4,5} есть мультимножество {1,2,3,3,4,5}
SQL> SELECT number_nt(1,2,3) MULTISET UNION number_nt(3,4,5) FROM dual;
NUMBER_NT(1,2,3)MULTISETUNIONNUMBER_NT(3,4,5)
--------------------------------------------------------------------------------
NUMBER_NT(1, 2, 3, 3, 4, 5)
SQL> -- объединение {1,2,3} и {3,4,5} есть множество {1,2,3,4,5}
SQL> SELECT number_nt(1,2,3) MULTISET UNION DISTINCT number_nt(3,4,5) FROM dual;
NUMBER_NT(1,2,3)MULTISETUNIONDISTINCTNUMBER_NT(3,4,5)
--------------------------------------------------------------------------------
NUMBER_NT(1, 2, 3, 4, 5)
SQL> -- пересечение {1,2,3,3} и {3,3,4,5} есть мультимножество {3,3}
SQL> SELECT number_nt(1,2,3,3) MULTISET INTERSECT number_nt(3,3,4,5) FROM dual;
NUMBER_NT(1,2,3,3)MULTISETINTERSECTNUMBER_NT(3,3,4,5)
--------------------------------------------------------------------------------
NUMBER_NT(3, 3)
SQL> -- пересечение {1,2,3,3} и {3,3,4,5} есть множество {3}
SQL> SELECT number_nt(1,2,3) MULTISET INTERSECT DISTINCT number_nt(3,3,4,5) FROM dual;
NUMBER_NT(1,2,3)MULTISETINTERSECTDISTINCTNUMBER_NT(3,3,4,5)
--------------------------------------------------------------------------------
NUMBER_NT(3)
SQL> -- разность {1,2,2,3} и {3,4,5} есть мультимножество {1,2,2}
SQL> SELECT number_nt(1,2,2,3) MULTISET EXCEPT number_nt(3,4,5) FROM dual;
NUMBER_NT(1,2,2,3)MULTISETEXCEPTNUMBER_NT(3,4,5)
--------------------------------------------------------------------------------
NUMBER_NT(1, 2, 2)
SQL> -- разность {1,2,2,3} и {3,4,5} есть множество {1,2}
SQL> SELECT number_nt(1,2,2,3) MULTISET EXCEPT DISTINCT number_nt(3,4,5) FROM dual;
NUMBER_NT(1,2,2,3)MULTISETEXCEPTDISTINCTNUMBER_NT(3,4,5)
--------------------------------------------------------------------------------
NUMBER_NT(1, 2)
Добавлю, что не только вложенные таблицы, инициализированные, как в примерах выше, или извлеченные из столбцов таблиц БД, могут служить операндами для операций над мультимножествами. При помощи параметра MULTISET функции CAST можно результат команды SELECT привести к типу вложенной таблицы:
SQL> SELECT
2 CAST(MULTISET(SELECT level lvl FROM dual CONNECT BY level < 5) AS number_nt)
3 MULTISET UNION
4 CAST(MULTISET(SELECT ROWNUM FROM all_users WHERE ROWNUM < 3) AS number_nt)
5 FROM dual;
CAST(MULTISET(SELECTLEVELLVLFROMDUALCONNECTBYLEVEL<5)ASNUMBER_NT)MULTISETUNIONCA
--------------------------------------------------------------------------------
NUMBER_NT(1, 2, 3, 4, 1, 2)
Проверка, является ли мультимножество подмультимножеством (!) другого, выполняется с помощью оператора SUBMULTISET:
SQL> SELECT 1
2 FROM dual
3 WHERE number_nt(1,2) SUBMULTISET OF number_nt(1,2,3);
1
----------
1
SQL> SELECT 1
2 FROM dual
3 WHERE number_nt(1,2) SUBMULTISET OF number_nt(1,2);
1
----------
1
SQL> SELECT 1
2 FROM dual
3 WHERE number_nt() SUBMULTISET OF number_nt(1,2,3);
1
----------
1
Наконец, третий контекст, в котором в СУБД Oracle реализованы операции над множествами - это операции над множествами строк таблиц. Из трех рассматриваемых в этой статье контекстов работы с множествами данный контекст, пожалуй, в первую очередь встречается изучающим SQL.
В языке SQL множество строк таблицы, над которым выполняется некоторая операция, определяется через условие WHERE или через его отсутствие - в последнем случае операция выполняется над всеми строками таблицы.
SELECT * FROM all_users; |
все пользователи СУБД Oracle |
SELECT * FROM all_users |
пользователи, созданные за последний год |
SELECT * FROM all_users |
пустое множество пользователей |
SELECT created FROM all_users; |
мультимножество дат создания пользователей |
SELECT DISTINCT created FROM all_users; |
множество дат - дубли подавлены |
Операции объединения, пересечения и разности множеств в языке SQL задаются ключевыми словами UNION [ALL], INTERSECT и MINUS, соответственно:
SQL> -- объединение множеств есть множество
SQL> SELECT * FROM all_users WHERE username LIKE 'A%'
2 UNION
3 SELECT * FROM all_users WHERE username LIKE 'S%';
USERNAME USER_ID CREATED
------------------------------ ---------- -----------
ANONYMOUS 35 27.08.2011
APEX_040000 47 27.08.2011
APEX_PUBLIC_USER 45 27.08.2011
AY 48 06.08.2014
SYS 0 27.08.2011
SYSTEM 5 27.08.2011
6 rows selected
SQL> -- UNION ALL дает мультимножество в результате
SQL> SELECT created FROM all_users WHERE username LIKE 'A%'
2 UNION ALL
3 SELECT created FROM all_users WHERE username LIKE 'S%';
CREATED
-----------
06.08.2014
27.08.2011
27.08.2011
27.08.2011
27.08.2011
27.08.2011
6 rows selected
SQL> -- пересечение множеств есть множество
SQL> SELECT * FROM all_users WHERE username LIKE 'S%'
2 INTERSECT
3 SELECT * FROM all_users WHERE username LIKE '%S';
USERNAME USER_ID CREATED
------------------------------ ---------- -----------
SYS 0 27.08.2011
SQL> -- разность множеств есть множество
SQL> SELECT * FROM all_users WHERE username LIKE '%S'
2 MINUS
3 SELECT * FROM all_users WHERE username LIKE 'S%';
USERNAME USER_ID CREATED
------------------------------ ---------- -----------
ANONYMOUS 35 27.08.2011
CTXSYS 32 27.08.2011
FLOWS_FILES 44 27.08.2011
MDSYS 42 27.08.2011
Как можно проверить равенство двух множеств? Множества равны, если их симметричная разность есть пустое множество:
SQL> (SELECT level lvl FROM dual CONNECT BY level < 5
2 MINUS
3 SELECT ROWNUM FROM all_users WHERE ROWNUM < 5)
4 UNION
5 (SELECT ROWNUM FROM all_users WHERE ROWNUM < 5
6 MINUS
7 SELECT level lvl FROM dual CONNECT BY level < 5)
8 ;
no rows selected
Проверка на вхождение элемента в мультимножество строк, возвращаемых командой SELECT, выполняется так:
SQL> SELECT 1
2 FROM dual
3 WHERE 'SYSTEM' IN (SELECT username FROM all_users);
1
----------
1
SQL> SELECT 1
2 FROM dual
3 WHERE (2, 'SYSTEM') IN (SELECT user_id, username FROM all_users);
no rows selected
Команда SELECT может вернуть 0 строк, или пустое множество, что оказывается эквивалентно NULL:
SQL> SELECT 1
2 FROM dual
3 WHERE (SELECT username FROM all_users WHERE 1 != 1) IS NULL;
1
----------
1
Однако NULL не годится на роль пустого множества с оператором IN. Тогда как пустое множество является подмножеством всякого множества, NULL не входит ни в одно из множеств строк, возвращаемых SELECT:
SQL> SELECT 1
2 FROM dual
3 WHERE NULL IN (SELECT username FROM all_users);
no rows selected
SQL> SELECT 1
2 FROM dual
3 WHERE NULL IN (SELECT username FROM all_users WHERE 1 != 1);
no rows selected
Я разбирал некоторые особенности поведения NULL в статье Многоликий NULL.
На этом закончу рассмотрение операций над множествами в СУБД Oracle. Для экспериментов с вложенными таблицами выше я создал тип number_nt - думаю, он может пригодиться для самых разных приложений. Например, если мне понадобится таблица из нескольких конкретных чисел, я смогу написать:
SQL> SELECT column_value FROM TABLE(number_nt(1966, 1991, 1999, 2014));
COLUMN_VALUE
------------
1966
1991
1999
2014
Комментариев нет:
Отправить комментарий