iv_an_ru (iv_an_ru) wrote,
iv_an_ru
iv_an_ru

Category:

Облако и куб: RDF в аналитической базе данных. Часть 1/2

Просили писать про базы данных всё подряд, не только хохмочки? Получайте.

Удешевление массовой памяти и появление дешёвой широкополосной связи сделали большие публичные массивы данных доступными для бизнеса. Вместе с тем качественная интеграция внутренних данных предприятия и несогласованных друг с другом внешних данных продолжает оставаться проблемой. Традиционные методы работы с реляционными данными плохо пригодны для настолько нерегулярных данных. В то же время традиционные "семантические" инструменты не обеспечивают нужной масштабируемости. Здесь описывается опыт совмещения этих двух подходов в СУБД OpenLink Virtuoso.

(Изначально это был конспект моего доклада на Третьем семинаре "Знания и Онтологии *ELSEWHERE*", Новосибирск, 1 июля 2011. Забавно, насколько же за прошедшие восемь лет ничего не изменилось принципиально, при очень больших изменениях в подробностях реализаций.
Bohemicus любит цитировать "правило Лампедузы": "se vogliamo che tutto rimanga come è, bisogna che tutto cambi.", то есть "чтобы всё осталось по-прежнему, всё должно измениться". Иногда кажется, это свойство не только европейской политики, но и любой отрасли, в которой обращаются очень большие деньги.)

Документ выражает мою личную точку зрения, а не позицию какой-либо рабочей группы W3C.

== Введение ==

Мировая культура накопила множество историй противостояния кого-то большого неповоротливого и маленького умного. Динозавры и млекопитающие, Голиаф и Давид, Том и Джерри. Историй их сотрудничества намного меньше. Иногда кажется, что разработчики больших реляционных баз данных и разработчики семантических средств просто следовали этому устоявшемуся шаблону. Первые называли семантику "модным развлечением", полагая, что задачи обработки больших массивов данных будут всегда. Вторые подчёркивали разницу между дешёвыми данными и дорогими знаниями, разумно считая, что манипулировать знаниями тоже надо уметь. На самом же деле бизнес в проигрыше от этого разделения. Предприятия хотели бы превращать большие объёмы дешёвых данных в дорогие знания, ожидая, что хорошее обогащение данных приведёт к обогащению владельца данных. Таким образом, существует большой незанятый рынок для продуктов и услуг, которые ни первые ни вторые в одиночку предоставить не могут. Необходимо сотрудничество в разработке некоторого гибридного подхода. OpenLink Software развивает соответствующую функциональность в семействе СУБД OpenLink Virtuoso. С осени 2010 года работы также ведутся в рамках проекта EU FP7 "Linking Open Data 2", являющегося продолжением известного проекта объединения публичных данных "Linking Open Data Project". Основная цель работы --- "предоставление совместно работающих средств хранения, анализа, выделения знаний и принятия решений на их основе, публикации произвольных данных для использования любым желающим подписчиком".

Поскольку знания публикуются в формате RDF, необходимо обеспечить удобное и компактное представление RDF в аналитической базе данных. Безусловно, на этом стыке областей были проекты и до Virtuoso. Достаточно вспомнить горизонтально масштабируемый Даталог проекта The Berkeley Orders Of Magnitude (BOOM) [ 9 ] [ 1 ].

В этой заметке описывается новая (ну, почти новая --- 2011-го года) подсистема хранения сжатых колонок данных, позволяющая хранить RDF-представление данных TPC-H [ 7 ] с плотностью примерно 6 байт на квад. (В эту единственную фразу укладывается вся тогдашняя научная новизна этой заметки; эксперт в области больших СУБД может реконструировать весь остальной текст, как целого динозавра по одной косточке.)

Такая плотность позволяет выполнять SPARQL-эквивалент запросов TPC-H над RDF со скоростью, сравнимой с оригинальной SQL-версией.

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

== Почти бесформенные данные ==

"no practical application of recursive query theory ... have been found to date." --- Michael Stonebraker, 1998 [ 8 ].

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

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

То, что казалось совершенно нереалистичным в 1998-м, стало обычным сценарием через 10 лет.

Cпособы представления таких данных в реляционных СУБД были известны достаточно давно: EAV и EAV/CR, так что RDF появился не на пустом месте. Известны были и сопутствующие проблемы масштабируемости. Неважно, насколько более богатую семантику представляет RDF, неважно, насколько SPARQL выразительнее SQL, и неважно, сколько денег экономит повторное использование справочников, если соответствующие SPARQL-запросы невозможно исполнить за разумное время. Такой разрыв в производительности между RDF-хранилищами и традиционными СУБД не обусловлен фундаментальными алгоритмическими причинами. В изрядной доле это вопрос времени и инвестиций. Разработчикам семантических инструментов хватало исследовательских задач с небольшими данными в ОЗУ одиночной машины. Им было не до изучения того, как их методы работы будут переноситься на работу с массовой памятью и распараллеливаться в кластере --- особенно при отсутствии денег на кластер.

Большие СУБД теперь нуждаются в семантических средствах, а специалисты по семантике должны научиться работать с действительно большими данными. Например, Ordnance Survey оценил объём RDF-графа, который они могут экспортировать, в 1 петатриплет, при этом суммарное число атрибутов разнообразных объектов будет измеряться тысячами. Логичным следствием появления множества таких задач стал первый в истории конференции VLDB "семантический" семинар, прошедший в 2010 году.

Когда бесформенное облако дуг RDF становится достаточно большим, в нём просто в силу принципа Дирихле обнаруживаются большие достаточно однородные группы объектов. Число классов и предикатов растёт примерно как логарифм от объёма данных, они начинают повторяться. В то же время, когда база данных перерастает масштаб одиночного предприятия, в данных появляются нерегулярности, которые не укладываются в имеющуюся схему БД. При этом нерегулярности настолько редки и разнообразны, что расширение ради них схемы оказывается непрактичным. Можно сказать, что из большого плотного облака можно вырезать большие "прямоугольные параллелипипеды", оставив только рваные края. И наоборот, достаточно большие таблицы норовят обрасти бесформенной бахромой.

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

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

== Влияние цены оборудования на скорость света ==

Начиная примерно с 2008-го года, максимальный возможный размер кластерного хранилища RDF превышает максимальный объём опубликованных кем-либо данных, и опережающий рост продолжается. Кроме нас самих, всё необходимое для такого хранилища предлагают сразу несколько конкурирующих поставщиков, например 4store [ 6 ], Bigdata [ 5 ] и OWLIM [ 4 ]. С учётом совершенно символической цены байта на диске, забота о плотности хранения кажется пережитком прошлого. Массовая память стоит копейки --- порядка 100 евро за терабайтовый диск и место под него. Так какая разница, сколько именно и каких узлов будет в кластере, особенно если большее число более мощных узлов будет означать и большее число одновременно обслуживаемых запросов?

Тем не менее плотность хранения становится важной, если учесть, что разрыв в скорости дискового доступа и производительности процессоров очень велик и не сокращается. Следовательно, отношение объёма ОЗУ узла к объёму его дисков должно по-прежнему составлять от 1/10 и больше, вплоть до 1/1. Большой объём ОЗУ не только дорог, но ещё и ограничен сверху максимальной вместимостью материнской платы. Если собирать узлы из популярных и поэтому относительно недорогих комплектующих, то 256Gb ОЗУ на узел (и 1-2Tb дисков) можно считать пределом. Свыше 256Gb масштабирование возможно только болезненным переходом от одной машины к кластеру и последующим добавлением узлов к кластеру. Если большой набор RDF хранится с плотностью вчетверо худшей, чем те же данные в традиционных таблицах, то кластер для RDF будет стоить вчетверо дороже. Ещё хуже, что потребность в кластере возникнет на вчетверо меньшем объёме данных.

Но может быть рост минимального размера кластера с избытком будет скомпенсирован ростом числа обрабатываемых запросов в секунду? Ведь те же RDF-хранилища на тестах BSBM [ 13 ] показывают почти линейный рост числа выполненных запросов в час при росте числа ядер у тестовой машины? К сожалению, для кластера дела обстоят намного хуже, чем для одиночного "ящика". Неважно, насколько велика пропускная способность сети между узлами, латентность этой сети остаётся очень большой. Более того, если измерять эту латентность в тактах, то обнаруживается, что она не может быть принципиально уменьшена никакими инвестициями в оборудование. Её неустранимой причиной является конечная скорость света. Конечно, более новый и дорогой техпроцесс позволяет сделать оборудование более компактным, как следствие уменьшив длину связующих проводников. Но этот же техпроцесс позволяет и поднять тактовую частоту, в итоге число тактов за задержку существенно не поменяется.

В результате единственным практичным "стилем общения" между нодами является пересылка как можно меньшего числа достаточно больших пакетов данных. Подготовка узлом каждого очередного пакета может потребовать ожидания исходных данных со всех остальных узлов. Чем больше число узлов, тем больше, например, вероятность того, что весь запрос будет ждать ответ одного случайно перегруженного узла. Полезная загрузка процессоров падает, непроизводительные затраты на переключение между запросами растут, на линейный от числа узлов рост числа запросов в секунду нечего и надеяться. В итоге нет никаких оправданий для четырёхкратного (по сравнению с табличным хранением) объёма ОЗУ; а ведь именно цена ОЗУ составляет львиную долю цены кластера.

== В поисках оптимальной модели хранения ==

К 2007-му году RDF стал достаточно полезным средством публикации данных и для выполнения особо сложного поиска над нерегулярными данными. В частности, он стал всё шире использоваться в биологии и медицине. И в то же время его использование жёстко ограничивалось теми областями, где цена оборудования не играла особой роли. Начались интенсивные поиски наиболее компактного представления.

Базовую модель нам особо выбирать не приходилось. Все триплеты всех RDF-ресурсов хранятся в одной таблице DB.DBA.RDF_QUAD в виде квадов --- четвёрок из графа (IRI ресурса), субъекта, предиката и объекта. Соответствующие колонки называются G, S, P, и O. Чтобы не хранить многократно повторяющиеся тексты IRI, все различные IRI перенумерованы в отдельной таблице, а в DB.DBA.RDF_QUAD помещаются только эти номера. Точно так же в отдельной таблице перенумерованы длинные значения O, например, тексты и XML-деревья.

Таблица DB.DBA.RDF_QUAD проиндексирована минимум с четырьмя разными порядками колонок. Это нужно, чтобы обеспечить удовлетворительный поиск для образца SPARQL с одной константой в любом из полей.

=== Смешивание реляционных таблиц и RDF ===

Данные создаются в табличном виде намного чаще, чем в виде RDF. Большая часть публикуемых RDF-ресурсов основана опять же на табличных данных. Естественным направлением работ стало выполнение SPARQL-запросов непосредственно над реляционными источниками данных. Разработчик описывает функции, вычисляющие триплеты RDF по исходным кортежам реляционной схемы. После этого SPARQL запрос над результатами применения этих функций можно транслировать в SQL над исходной реляционной схемой. Если у этих функций известны ещё и обратные, то полученный SQL может работать не хуже написанного вручную. При этом цена написания SPARQL куда меньше цены эквивалентного SQL. Полстраницы SPARQL-BI могут заменить SQL-запрос длиной несколько десятков страниц. Кроме того, если все триплеты всех RDF-ресурсов фактически хранятся в одной реляционной таблице, то эта таблица ничем принципиально не отличается от остальных. Совместное использование RDF и реляционных таблиц становится очень простым. В OpenLink Virtuoso такое отображение кортежей в триплеты получило название RDF Views [ 3 ]. Прямым конкурентом Virtuoso в этом отношении стал SPARQL-процессор D2RQ, не имевший собственного RDF-хранилища и использовавший соединение с MySQL.

Совершенствование RDF Views шло двумя путями. Во-первых, описание самих отображений в триплеты обрастало опциями, позволявшими предоставить SPARQL-оптимизатору как можно больше подсказок о свойствах генерируемых данных. Во-вторых, используемый диалект SQL обогащался синтаксическими конструкциями, в том числе добавились транзитивные подзапросы и поддержка базовых конструкций OWL: sameAs, subTypeOf, sobPropertyOf и пр. Удалось заметно улучшить и SQL-оптимизатор.

Работа над RDF Views подтвердила, что хорошей оказывается не та СУБД, где что-то сделано замечательно, а та, где ничего не сделано "на троечку". Тщательное вылизывание модулей, казавшихся особенно важными, позволяло выигрывать единицы процентов скорости, грубые заплатки на вроде бы второстепенных неудачных местах давали десятки процентов. Мы не изобретали ничего нового, мы только исправляли свои же собственные ошибки и недоделки, и старались не делать новых --- и в тесте BSBM version 2 обогнали D2RQ в 160 раз.

Все эти локальные изменения в сумме сделали RDF Views удобным средством экспорта локальных данных предприятия --- исходных и обогащённых сведениями из внешних источников. Что важнее, они снизили потребность в копировании таблиц в RDF. Тем не менее, они никак не сказались на плотности хранения больших количеств RDF.

=== Сжатие дисковых страниц ===

Первой попыткой хоть как-то сократить разрыв в плотности между RDF и классическими таблицами стала архивация целых дисковых страниц файла БД. Результат оказался очень хорошим --- оказалось возможным сжимать 95% страниц в два раза или больше. К несчастью для RDF, данные c изначально лучшей локальностью и сжимаются лучше, в итоге классические таблицы сжимаются лучше RDF. К тому же эта мера ускоряет чтение с жёсткого диска, но не снижает требований к размеру ОЗУ. Если при выполнении запроса из-за нехватки памяти происходит чтение с диска, то это настолько плохо, что уже не очень важно, насколько именно плохо.

=== Замена обычных индексов битовыми массивами ===

В аналитических СУБД для перечислимых типов часто используют "bitmap index". Пусть есть миллион анкет о покупателях, перенумерованных от 0 до 999999, и в большинстве указан примерный возраст ("18-25 лет", "26-35 лет", "36-45" и т.п.). Тогда для выборок по возрасту будет достаточно двухколоночного индекса из десятка строк, в котором ключом строки является возраст (скажем, "26-35"), а зависимой колонкой --- массив из миллиона бит, в котором в бит номер N записана единичка, если в анкете номер N указан именно этот возраст.

Такой индекс удобен тем, что многие статистические операции можно выполнить раньше, чем понадобится доступ к собственно анкетам. Скажем, номера анкет всех мужчин старше 55 лет можно будет получить побитовым OR массивов для "56-65" и более старших возрастов, и последующим побитовым AND с массивом для мужских анкет (или побитовым AND NOT с массивом для женских).

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

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

Большинство RDF-документов имеют более-менее регулярную структуру, в которой каждый известный хранилищу IRI или возникает в качестве предиката достаточно часто, или не возникает вовсе. Фрагменты с большим количеством единичек хорошо сжимаются run-length encoding, фрагменты из одних нулей вообще нет нужды хранить, поэтому если последней колонкой индекса является P, лучше заменить её битовыми массивами. Точно по той же логике битовые массивы используются, если последней колонкой является S. Они не используются, если последняя колонка --- О, такая замена возможна только для целочисленных типов. Они не используются и для завершающего G --- обычно триплет хранится всего в одном графе, а настолько пустой ("однобитовый") массив не даёт никакого выигрыша.

Правильность решения была подтверждена в марте 2009г. Chris Bizer и Andreas Schultz прогнали бенчмарку BSBM version 2 на 25M триплетов, SPARQL-запросы через HTTP. Оказалось, что максимальные производительности одной и той же Virtuoso 5.0.10 над реляционными данными и над RDF различаются всего втрое. Это при том, что остальные проходившие тест хранилища RDF показали ещё худшую максимальную производительность, с отставанием не на проценты, а в разы.

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

=== Неполные индексы: 3+2 меньше, чем 4 ===

Следующим шагом стало внедрение неполных индексов, которые не дают полной информации о записи, а только подсказывают, где её имеет смысл искать. В таблице DB.DBA.RDF_QUAD остались два четырёхколоночных индекса --- обычный PSOG и POGS с битовыми массивами. Ещё три индекса стали неполными двухколоночными --- GS, SP и OP. Они используются в комбинации с полными. Допустим, надо найти все триплеты одного графа. Сначала в индексе GS можно найти все S из этого графа. Потом в индексе SP для них можно найти все P. Наконец, и для каждой известной комбинации P и S можно в индексе PSOG найти все O, проверяя совпадение G c заказанным.

Индексов стало на один больше, да ещё и появились дополнительные промежуточные шаги в доступе. Но при этом неполные индексы компактны, и как следствие достаточно хорошо кэшируются в памяти.

На ISWC-2008 мы заявили, что считаем бенчмарку LUBM [ 14 ] нереалистичной, слишком простой и потому устаревшей. Затем мы вывесили нахальный постер "Scale Is Here" и продемонстрировали достаточно сложные запросы над одним из крупнейших на тот момент хранилищ RDF. Это было особенно уместно перед началом работы W3C RDB2RDF Incubator Group, но всё же не было прорывом в продвижении технологии на рынок.

=== Query Execution in Column-Oriented Database Systems ===

Диссертация Абади (Daniel J. Abadi) [ 2 ] c этим заголовком стала хитом 2008-го года. Попытки сделать эффективное вертикальное хранилище были и до него, но он первый сделал всё аккуратно. В итоге Абади показал преимущества вертикального хранения для практически любых аналитических задач, и вслед за ним преимущества стали продемонстрированы даже если колонок всего три и притом очень узких, как в случае RDF. Разработчики бросились наперегонки строить вертикальные варианты своих хранилищ. Мы тоже начали эксперименты с новым размещением, трамбуя данные так и эдак, и к середине прошлого года получили результаты, которые уже не было стыдно показывать SQL-ному сообществу. Мы их и показали, на VLDB-2010:

Потребление памяти на данных TPC H, 1G По строкам По колонкам
Реляционная модель
Таблицы 127077 80469
Индексы 10389 10335
Таблицы без l_comment и ps_comment 45224
RDF
Индекс PSOG 282789 42760 +168
Индекс POGS 104684 43070 +152
Индекс SP 52314 20439 +68
Индекс OP 27767 7228 +14
Индекс GS 152 148 +1
Все 5 индексов 467706 113996
(байт на квад) (25.96) (6.32)
PSOG+POGS+GS 387473 86150
(bytes per quad) (21.50) (4.78)
Словари IRI 43615 43615
Словарь литералов 93458 93458

Размеры указаны как количества страниц по 8Kb каждая, для вертикального хранения RDF указаны размеры колонок + размеры индекса верхнего уровня.

Эти 6.32 байт на квад наконец-то делают RDF конкурентоспособным по плотности, и, как следствие, по необходимым объёмам ОЗУ и пропускной способности дисковой подсистемы, и, как следствие, по TCO систем на основе RDF. Поскольку изменилась только подсистема хранения, а все остальное было вылизано по скорости намного раньше, производительность по RDF-H наконец-то оказалась сравнима с производительностью TPC-H. Сейчас, при хранении по строкам в Virtuoso 6.1, мы рекомендуем своим клиентам ставить в сервер 32Gb ОЗУ на каждый миллиард квадов. После планируемого на эту осень выхода Virtuoso 7 с её хранением по колонкам, мы будет рекомендовать ставить порядка 8Gb на миллиард. Это означает, что дешевый самосборный сервер сможет обрабатывать уже не 8, а 32 миллиарда квадов, что достаточно для многих научных и коммерческих приложений. Это также означает, что на дорогих, но всё же серийных серверах можно попробовать такие задачи, как сводную аналитику по всем абонентам China Mobile (примерно 1 тераквад, примерно по 4000 фактов о каждом абоненте).

(В приведёных цифрах есть доля лукавства: словари IRI достаточно велики, а мы не предоставляем для них никаких полнотекстовых или regex-индексов. Это не значит, что для этого есть принципиальные ограничения --- нам просто лень. Если потребуется пользователям (а за девять лет ещё не потребовалось), мы можем добавить индексацию и/или представить их в токенизированном виде, повторив опыт MonetDB [ 10 ].)

Теперь появляется работа для специалистов по семантике, потому что классических технологий реляционных СУБД недостаточно, чтобы построить план сложного запроса над RDF. Компилятор должен лучше понимать, о чём, собственно, запрос.

=== Предсказание кардинальности и селективности ===

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

С RDF ситуация принципиально сложнее. Таблица всего одна, статистик по её пяти индексам недостаточно, чтобы выразить всё многообразие зависимостей между различными понятиями. Рассмотрим фрагмент запроса Q12 из TPC-H, переписанного в SPARQL

select (?cost * ?qty) as ?totalcost
where {
?thr_ps a tpch:partsupp ;
tpch:supplycost ?cost ;
tpch:availqty ?qty ;
tpch:has_supplier ?supp .
?supp tpch:has_nation ?nation .
?nation tpch:name "GERMANY" .
}

Разумно было бы начать с поиска всех наций с именем GERMANY, затем найти всех немецких поставщиков, затем все их предложения по запчастям, в последнюю очередь иcкать цены и количества этих запчастей. Но для этого надо понимать множество подробностей об запрашиваемых данных. К примеру, множество субъектов самых разных типов имеют свойство tpch:name, но несмотря на общую многочисленность очень немногие субъекты с этим свойством являются странами, и вообще стран в этом тесте всего 25, и имена у стран различны, так что ровно одна будет иметь это имя, а свойство tpch:has_nation имеют покупатели и поставщики, в такой-то пропорции и т.д. А прежде всего этого надо знать вообще о существовании таких обособленных и статистически однородных групп субъектов, как страны, покупатели и поставщики, что в случае обычных таблиц было очевидно из самого факта существования отдельных таблиц COUNTRY, CUSTOMER и SUPPLIER. Конечно, можно облегчить оптимизатору жизнь, вводя как можно более конкретные имена предикатов, tpch:country_name вместо tpch:name, tpch:supplier_has_nation вместо tpch:has_nation и т.п., но это хоронит все преимущества RDF как средства интеграции.

Задачу усложняют иерархии классов и свойств, особенно если разные подклассы одного класса имеют общее свойство, но с существенно разными статистиками. Рассмотрим простую транспортную задачу, "найти все пары кардиологических больниц A и B таких, что A находится не более чем с в 100 километрах от некоторого аэропорта С, B, аналогично, находится не более чем с в 100 километрах от некоторого аэропорта D, и все четыре A,B,C,D лежат в границах какого-то одного региона E типа X, вернуть кортеж из A, B, C, D и E".

select ?hosp1 ?hosp2, ?air1, ?air2, ?rgn
where {
?hosp1 a cardio_hosp .
?hosp2 a cardio_hosp .
?air1 a airport .
?air2 a airport .
?rgn a ?:region_type ; geo:loc ?rgn_borders .
filter (distance (?hosp1, ?air1) < 100000)
filter (distance (?hosp2, ?air2) < 100000)
filter (contains (?rgn_borders, ?hosp1))
filter (contains (?rgn_borders, ?hosp2))
filter (contains (?rgn_borders, ?air1))
filter (contains (?rgn_borders, ?air2)) }

Этот запрос должен компилироваться совершенно по-разному, если ?:region_type задаёт тип "континент", "страна" или "область", потому что 100 километров в масштабах континента и 100 километров в масштабах области --- совершенно разные по селективности условия, а селективность принадлежности сразу двух больниц и двух аэропортов одному региону показывает вообще "четвёртую степень" зависимости от обычного размера региона. И если проблемы возникают даже с такими простыми запросами, то что делать с запросами из 30-40 образцов и десятков условий? Надо снабдить SQL-оптимизатор некоторым интерфейсом к процессору онтологий, но сейчас нет ни хорошего списка требований к такому интерфейсу, ни тем более понимания, что из этих требований может быть реализовано в виде быстрых алгоритмов. Это очень интересная тема для исследований.

=== Обмен знаниями ===

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

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

С RDF всё обстоит хуже. Даже обычная проверка эквивалентности двух данных графов, хранящихся на двух данных машинах, оказывается тривиальной задачей только для случая графов без неименованых нод. Для графов, состоящих из "удобных" "низкорослых" деревьев, например, дампов FOAF, есть если не линейные, то хотя бы однопроходные алгоритмы [ 11 ], для графов общего вида иногда быстрее перезагрузить граф целиком, чем построить разность между старой и новой версией на одной машине и "накатить" её на другой. Ещё хуже обстоят дела с алгоритмами смешивания изменений. Для коллективной работы над большими объёмами знаний необходимо иметь эффективные процедуры diff и merge, такие, что для данных похожих больших графов G ("исходная версия"), Ga ("версия с правкой a") и Gb ("версия с правкой a") можно построить небольшие графы-"заплатки" Da := diff(G,Ga), и Db := diff(G,Gb), а потом либо доказать "несовместимость правок" получить Gab := merge(Gb,Da) такой, что merge(Ga,Db) = Gab и при этом diff(Gb,Gab) = Da и при этом diff(Ga,Gab) = Db. Опыт показывает, что если семантика данных в графах игнорируется, то diff может принимать изменения описаний сущностей за создания и удаления сущностей, и наоборот, в результате "заплатки" охватывают слишком большие фрагменты графа и при смешивании изменения "налезают" друг на друга. Учёт семантики позволил бы не только улучшить контроль версий сам по себе, но и выдавать более понятную для человека диагностику конфликтов между правками. Это ещё одна интересная тема для исследований.

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

=== RDB2RDF --- Обновление RDF из реляционных источников ===

Этот случай кажется самым простым, ведь любой генератор отчётов может выдать результат несложного SQL в формате Turtle.

Если уже есть RDF View для этих данных, то это можно сделать ещё проще, выполнив SPARQL

construct { ?s ?p ?o } where { ?s ?p ?o }

и передать результат в нужное RDF-хранилище, а если реляционные данные и RDF-хранилище находятся в одной СУБД, то схожий SPARUL INSERT сделает всё без затрат на ещё быстрее.

Очевиден и общий недостаток всех этих способов --- экспортируются не все новые данные, а вообще все данные, это слишком долго и ресурсоёмко. В Virtuoso 6.1 мы добавили ещё одну возможность --- обновление RDF триггерами над реляционными таблицами. Специальный транслятор по декларации RDF View строит код этих триггеров и код процедур для первоначального экспорта данных из таблиц в RDF. Этот метод хорошо себя зарекомендовал, а в сочетании с виртуальной схемой Virtuoso он позволяет обновлять RDF данными не только из локальных таблиц, но и из таблиц присоединённых серверов. Тем не менее это пока что не универсальное решение, потому что таким образом нельзя реплицировать OLTP источники с сохранением гарантированной доступности. Проблема в том, что при экспорте данных в RDF нормализованность данных часто приносится в жертву их читабельности и переносимости. Скажем, если в исходных таблицах OLTP все поставщики имеют уникальные и неизменные целочисленные идентификаторы, то IRI в экспортированном RDF обычно содержат их наименования. Если популярный поставщик переименовывается, то могут измениться не только его собственный IRI и не только квады непосредственно о нём, что ещё терпимо, но и многочисленные квады об относящихся к нему заказах, поставках и прочем, выполнение такого массивного обновления может сорвать своевременное отслеживание других обновлений. Учебники по реляционным СУБД считают это неизбежным наказанием за денормализованность, но может специалисты по семантике придумают какой-нибудь выход?

=== RDF2RDF --- Репликация RDF в RDF ===

Случай двух изначально одинаковых хранилищ RDF, "публикатора" и "подписчика", и воспроизведения "подписчиком" всех изменений "публикатора" --- вполне традиционная задача, Virtuoso 6.1 содержит всё необходимое. Проблемы начинаются только при многостороннем обмене изменений, при подписке на изменения сразу нескольких публикаторов или при взаимной подписке двух хранилищ на изменения друг в друге, потому что требуются аналоги уже упоминавшихся процедур diff и merge. Аналог diff с одной стороны не должен просматривать весь граф в поисках изменений, с другой стороны требования к его быстродействию куда жёстче.

=== RDF2RDB --- Обновление реляционных данных из RDF ===

В отличие от экспорта из реляционных источников в RDF и из RDF в RDF в этом случае получатель данных не "всеяден": если результат нарушает ограничения схемы базы данных, то ввод будет сорван. В связи с этим задача разбивается на несколько шагов, каждый из которых может завершиться диагностикой ошибки, и для разумной обработки этих ошибок потребуется опять-таки понимать семантику предметной области. Предположу для конкретности, что сопоставление реляционных данных и RDF описано в уже упоминавшемся стиле RDF View, и алгоритм получает на вход списки добавленных и удалённых квадов, а так Тогда обработка списка изменений в RDF. начнёт свою работу с определения для каждого данного квада, какие правила данного RDF View могли бы создать такой квад, и определение, какие первичные ключи должны были бы иметь строки, чтобы из них мог быть получен этот квад; эта часть не вызывает принципиальных затруднений. Далее надо сгруппировать эти квады по найденым первичным ключам и проверить, будут ли данные в этих группах внутренне противоречивы, если да, то надо решить, что делать с такими группами. Следующий этап --- внесение изменений в реляционные таблицы, если какие-то из изменений будут отвергнуты, то опять де нужно принимать решения и готовить диагностику. Алгоритмы для всех трёх этапов мы опубликовали ещё несколько лет назад, но их невозможно использовать на практике, пока специалисты по семантике не смогут предложить хороший способ сделать решения по обработке ошибок "разумными", а диагностику --- понятной для человека. Кроме того, необходима более развитая, чем сейчас, инфраструктура проектирования и отладки RDF Views, и опять потребуются гибридные методы; иначе как доказать, например, что результат выполнения некоторого SQL-запроса будет соответствовать ограничениям, предусмотренным данной онтологией?

=== RDB2RDF2RDF2RDB = RDB2RDB ===

RDB2RDF, RDF2RDF, RDF2RDB --- три эти задачи интересны не только сами по себе, но и как три звена одной технологической цепочки. Экспорт данных из реляционной базы с одной схемой в базу с другой схемой требуется регулярно и каждый раз оказывается проблемой. Много ручной работы, много возможностей внести ошибку, и главное --- дефицит специалистов, которые знают подробности как первой так и второй схемы или в состоянии быстро их выучить. Использование промежуточного звена в виде одного или двух RDF-хранилищ кажется хорошим решением. Конечно, требования к аппаратным ресурсам будут выше, чем для рукописного решения, зато упадут трудозатраты. Кроме того, в эту цепочку может быть добавлена подсистема логического вывода, которая поможет "заполнить дыры" в передаваемых данных, если экспортёр и импортёр используют не только различные реляционные схемы, но и различные стандарты представления знаний.

(Конспект слишком длинный, а козёл Фрэнк слишком старый, чтобы прожевать его целиком. Придётся порвать его пополам, и половинки появятся в ленте в идиотском порядке)
Tags: rdbms, конспекты
Subscribe

  • (no subject)

    It is with great sadness that I have to inform you about the passing away of Paul Nieuwdorp. May Paul's soul rest in eternal peace. He will never…

  • (no subject)

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

  • COVID-19 research dataset in our LOD Cloud cache

    Kingsley loaded FCORD-19-on-FHIR to lod.openlinksw.com, fell free to SPARQL it there. Sample queries: Diseases and MESH Cross References ( query…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 5 comments