Не сравнивайте несравнимое!

Сергей Кузнецов

1. Введение

К написанию этой заметки меня подвигла публикация в нашей библиотеке статьи А.Е. Васильева "Развитие логических моделей данных". Сразу хочу сказать, что я очень симпатизирую работе, выполняемой коллективом под руководством автора (разработке многомерной СУБД UMS-FAD). Однако, поскольку я являюсь редактором раздела "Базы данных" нашей библиотеки, и публикация статьи А.Е. Васильева подготовлена мной, я просто не могу не заявить, что во многом с этой статьей не согласен.

Конечно, можно было бы, соблюдая идейную чистоту раздела, просто не публиковать статью, но, в-первых, как я уже сказал выше, сама работа группы Васильева мне нравится. Во-вторых, та путаница, которая, на мой взгляд, присутствует в статье, свойственна умам многих разработчиков, которые примыкают к сообществу баз данных, не имея исходной теоретической подготовки. Особенно отчетливо это проявляется в последнее время в связи с новой линией "пусть расцветают сто цветов", которая сопутствует концепции Майкла Стоунбрейкера "один размер не пригоден для всех" – см. [1-3] и др. статьи на эту тему.

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

Что же такое "модель данных"?

В [4] Эдгар Кодд пишет: "Реляционная модель предоставляет средства описания данных на основе только их естественной структуры, т.е. без потребности введения какой-либо дополнительной структуры для целей машинного представления. Соответственно, эта модель обеспечивает основу языка данных высокого уровня, который поддерживает максимальную независимость программ, с одной стороны, и машинного представления и организации данных с другой." Более общее определения понятия модели данных приводится в [5]: "Модель – это абстрактное, замкнутое, логическое определение объектов, операций и т.д., совместно представляющих абстрактную машину, с которой взаимодействуют пользователи". Оба эти определения являются существенными.

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

Собственно, о том же говорят и Дейт с Дарвеном в [5], только уже по отношению к любой модели данных. В определении из [5] ключевые слова – абстрактное, замкнутое, логическое определение. Т.е. в этом определении не должно содержаться ничего лишнего, что в принципе может изменяться от одной реализации к другой. Этому определению соответствует реляционная модель в смысле Кодда, "истинно" реляционная модель в смысле "Третьего манифеста" [5], модель данных SQL и объектно-ориентированная модель данных ODMG 3.0 (см. например, [6]).

Например, в случае модели данных SQL родовой структурой данных является таблица (мультимножество строк), а языком – сам язык SQL с его операциями SELECT, INSERT, DELETE, UPDATE. В случае модели данных ODMG 3.0 структуры хранимых данных задаются средствами определения атомарных объектных типов и объектных типов коллекций, а для доступа к данным определяется язык OQL. В языковых средствах некоторых моделей данных присутствуют явные операции обновления данных (например, в модели SQL), в некоторых моделях они полностью отсутствуют (т.е. отдаются на откуп реализациям; например, в модели ODMG), в третьих моделях в качестве единственной операции обновления базы данных вводится операция присваивания).

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

Отмеченная сложность проистекает из того, что во всех современных моделях данных (в "истинно" реляционной модели, модели данных SQL и объектно-ориентированной модели) предусматриваются возможности определения произвольно сложных типов данных, позволяющих, например, определять вложенные иерархические структуры данных в реляционной модели и модели данных SQL и хранимые мультимножества строк в объектно-ориентированной модели. Так что очень трудно сказать, какую из моделей стоило бы выбрать, если вообще на касаться вопросов их реализации.

Наконец, необходимо заметить, что, несмотря на наличие большого числа реализаций СУБД, создатели которых утверждают о поддержке многомерной модели данных (например, многомерная аналитическая СУБД Essbase, "послепиковские" СУБД Universe и Unidata, основанная на M-технологии СУБД Caché, основанная на "многомерных массивах" SciDB и т.д.), мне никогда не встречалось ни одной попытки общего определения многомерной модели данных.

Поэтому, чтобы иметь возможность сравнивать многомерную модель данных с какой-либо другой моделью, неоходимо ее сначала определить, хотя бы на таком не слишком строгом уровне, как это сделал Эдгар Кодд в своей первой статье о реляционной модели данных (вернее, во второй статье, первой была [7]). Наверное, сообществу "многомерных СУБД" следовало бы поискать в своих рядах нового "Кодда", который решился бы на эту (скорее всего, неблагодарную) работу. По крайней мере, в ее результате можно было бы понять, насколько правомерно использование одного и того же термина multidimensional применительно к настолько разным системам. А пока такой модели нет, можно позволить себе только сравнивать "многомерные" реализации с другими "многомерными" или "немногомерными" реализациями.

Как сравнивать реализации?

Вообще-то для сравнения разных реализаций на однотипной рабочей нагрузке принято использовать эталонные тестовые наборы (benchmark). Наиболее авторитетной организацией, поставляющей такие тестовые наборы, является Transaction Processing Performance Council (TPC). В типичную спецификацию тестового набора входит структура и содержимое тестовой базы данных и правила построения тестовых приложений. Все ведущие производители СУБД регулярно производят испытания своих продуктов на основе разных тестовых наборов TPC и публикуют свои результаты.

К сожалению, существуют достаточно жесткие ограничения относительно сравнительных испытаний на одном и том же тестовом наборе и одной и той же аппаратуре своей СУБД и какой-либо системы другого производителя (обычно открытая публикация результатов таких испытаний запрещается под угрозой судебного преследования). Но эти ограничения можно обойти (как это делается, например, в [2]), если аккуратно сохранять анонимность системы, с которой производится сравнение.

Итак, количественное и даже качественное сравнение двух реализаций СУБД можно производить только на одной и той же рабочей нагрузке (в случае количественного сравнения требуется использовать одну и ту же базовую аппаратно-программную платформу). Обычно эталонный тестовый набор специфицируется в терминах некоторой модели данных (как правило, SQL). Если требуется применить его к системе, реализующей некоторую другую модель, необходимо аккуратнейшим образом реализовать эту спецификацию в терминах своей модели данных (или реализации, если модель, как таковая отсутствует). И даже после этого в сравнении с использованием такого "неканонического" тестового набора будет каким-то образом отражаться специфика его представления в другой модели данных.

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

Например, в статье А.Е. Васильева неверно представляется, что в реализациях модели данных SQL в листовых вершинах индексных В⁺-деревьев хранятся идентификаторы записей данных, при использовании которых для доступа к записям требуется дополнительный двоичный поиск в самих таблицах. Это не так. Идентификатор строки, хранящийся в индексной структуре, представляет собой "почти" прямой физический адрес в дисковой памяти, и никакого дополнительного поиска после нахождения идентификатора не требуется.

Более того, в некоторых реализациях (например, в Oracle) допускается очень быстрый доступ на уровне языка SQL к строкам таблиц по их "почти" физическим идентификаторам (rowid). И, конечно, если сравнивать реализацию Oracle с реализацией какой-либо "многомерной" СУБД, эту особенность скрытой от пользователей явной навигации нужно иметь в виду.

Кстати, SQL поддерживается и во многих СУБД, которые изначально разрабатывались как явно навигационные (например, в IMS, IDMS, той же Caché). С одной стороны, можно считать, что и эти системы являются реализациями модели данных SQL, но, с другой стороны, это совсем не такие реализации, как у систем, изначально разрабатывавшихся как SQL-ориентированные. И эти реализационные особенности систем тоже неоходимо иметь в виду при каких-либо сравнениях с их участием.

4. Заключение

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

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

Литература

1. Michael Stonebraker, Ugur Cetintemel. "One Size Fits All": An Idea Whose Time Has Come and Gone, 21st International Conference on Data Engineering (ICDE'05), Tokyo, Japan, April 5-8, 2005.
Имеется перевод на русский язык: Майкл Стоунбрейкер, Угур Кетинтемел. Один размер пригоден для всех»: идея, время которой пришло и ушло, 2007.

2. Michael Stonebraker, Chuck Bear, Ugur Cetintemel, Mitch Cherniack, Tingjian Ge, Nabil Hachem, Stavros Harizopoulos, John Lifter, Jennie Rogers, and Stan Zdonik. One Size Fits All? – Part 2: Benchmarking Results, Proceedings of the 3rd Biennial Conference on Innovative Data Systems Research (CIDR), January 7-10, 2007, Asilomar, California, USA.
Имеется перевод на русский язык: Майкл Стоунбрейкер, Чак Беэ, Угур Кетинтемел, Мич Черняк, Тиньян Ге, Набил Хачем, Ставрос Харизопулос, Джон Лифтер, Дженни Роджерс, Стэн Здоник. Пригоден ли один размер для всех? Часть 2: результаты тестовых испытаний, 2007.

3. Сергей Кузнецов. Универсальность и специализация: время разбивать камни?, 2007.

4. E.F. Codd. A Relational Model of Data for Large Shared Data Banks. Communications of the ACM, Volume 13, Number 6, June, 1970.
Перевод на русский язык: Е.Ф. Кодд. Реляционная модель данных для больших совместно используемых банков данных, 2009.

5. К. Дж. Дейт, Хью Дарвен. "Основы будущих баз данных. Третий манифест", М., Янус-К, 2004.

6. Сергей Кузнецов. Базы данных. Вводный курс, 2004. Лекция 2. Понятие модели данных. Обзор разновидностей моделей данных.

7. E. F. Codd. Derivability, Redundancy and Consistency of Relations Stored in Large Data Banks, ACM SIGMOD Record, March 2009 (Vol. 38, No. 1).
Перевод на русский язык: Выводимость, избыточность и согласованность отношений, хранимых в крупных банках данных, 2009.