Автор: Александр ДЕНИСЕНКО aden@online.ru, aledin@academy.ru
Говоря о таблице как основном объекте базы данных, зачастую
упускается такая подробность, как упорядоченность строк или
отсутствие таковой. Это уточняет семантику операции сравнения
таблиц. Равны ли две таблицы, если их состав по строкам
одинаков? Такие вопросы редко задают себе программисты, чаще с
этой проблемой сталкиваются дотошные администраторы (после
восстановления базы из архива или перед ним хочется узнать,
одинаковы ли две таблицы - в архиве и базе, двух базах или на
двух машинах, участвующих в репликации.
С математической
(точнее методологической) точки зрения понятие равенства,
совпадения и одинаковости нуждается в уточнении, которое
выходит за рамки настоящей заметки. Понятие равенства объектов
зачастую корректно лишь с указанием 'точности'; следует
различать в операции сравнения разные её варианты - полное
совпадение (философы именуют его тождеством) или частичное - с
точностью, например, до порядка. Так, множества {a,b,c} и
{c,a,b} равны как множества математически, но не равны с
точностью до порядка следования элементов.
В случае с
таблицами ситуация ещё сложнее - необходимо учитывать порядок
и строк и столбцов. Возможно, это одна из причин отсутствия в
распространенных базах данных такой казалось бы элементарной
операции над таблицами, как проверка на равенство.
Мы
сейчас сыграем на этой недоговоренности, чтобы высветить сам
феномен кодирования информации событийным временем вместо
классической битовой ленты машины Тьюринга.
Рассмотрим
таблицу T, состоящую из N строк. Предположим, что порядок
строк не оговорён, то есть таблица T может иметь несколько
вариаций - T1,…,TN, отличающихся лишь порядком следования
строк. Это в свою очередь означает, что таблица - помимо
собственно информации об объектах (строки) содержит ещё и
информацию о порядке следования строк. Значит, имея таблицу в
машине, мы на самом деле имеем некоторую дополнительную
информацию - помимо её непосредственного состава в обыденном
понимании. Если элементов N, то их можно упорядочить N!
способами (! - это факториал, а не восклицание).
Теперь
остаётся договориться о том, какую именно информацию несёт
каждый вариант порядка. И всё.
Разъяснение
Порядок строк в таблице отслеживается в операциях с
курсорами и в сеансовых протоколах сетевых компонент.
Передавая по сети таблицу из десяти строк, машина фактически
передаёт (или не передаёт) порядок этих строк. Обычный
оператор выборки строк из таблицы (SELECT) этого порядка не
отслеживает. Порядок не отслеживается и обычными протоколами
транспортного уровня операционных систем (например, TCP/IP),
хотя на принимающей стороне воссоздаётся порядок пакетов,
хранящихся на передающей стороне - в составе заголовка каждого
пакета есть его номер в исходном варианте, так что принимающая
сторона восстанавливает порядок, имевшийся на передающей
стороне). А где информация о фактическом порядке при передаче?
При использовании стандартного стека протоколов она
уничтожается в момент сборки пакетов принимающей стороной. Но
если воспользоваться сеансовым уровнем протоколов (так
называемой семиуровневой модели OSI), то порядок на
принимающей стороне совпадёт с порядком на стороне передающей.
А это означает, что можно извлечь достаточно много информации
(например, 5! = 120 вариантов перестановок из пяти пакетов или
строк), не искажая и не шифруя содержимого строк (тем самым не
нарушая режима открытой передачи информации). Достаточно лишь
знать базовый порядок элементов и фактически переданный.
В
случае с Интернетом, например, совершенно неважно, что
передавать по сети, контролируемой на источнике и приёмнике
(фото Вашей бабушки или президента на лужайке вполне сгодится
и не потребует ни одного дополнительного бита!). Также
сгодится и репликация таблиц (например, полная - в терминах
Микрософт SQL2000 это snapshot replication - репликация не
сохраняет порядка, а репликация записей журнала сохраняет).
Математика даёт астрономическоё число вариантов перестановок
из элементов множества большой мощности.
Дальнейшее
развитие этой схемы возможно при наличии нескольких каналов
передачи. Оценка числа вариантов упорядочения для N элементов
из курса школьной комбинаторики получена в предположении так
называемого линейного (одномерного) порядка. Если же порядок
не обязательно линеен, то число вариантов ещё больше. Здесь не
место формулам, но очевидно, что даже два элемента при
передаче по сети с двумя параллельными каналами имеют не два
варианта упорядочения, а пять. Передача элемента по сети - это
интервал во времени. А два интервала во времени могут
соотноситься пятью способами (второй интервал следует до
первого, после первого, внутри первого; начало второго
интервала-до начала первого, окончание второго интервал -
внутри первого; начало второго интервала - внутри первого,
окончание - за первым интервалом). Для N интервалов вариантов
порядка при передаче по К каналам очень велико. Заметим, что
пакеты при передаче по сети могут проходить по произвольному
количеству маршрутов - это также не нарушает режима открытой
передачи данных, при котором вся передаваемая информация
доступна контролирующей стороне).
[В начало]