Category: it

Category was added automatically. Read all entries about "it".

BIO_reset()



Несмотря на приставку "BIO", это не про биологию, а на 3/4 про программирование, и на 1/4 про жизнь. BIO_reset() --- маленькая служебная процедура, используемая почти в любой программе, имеющей дело с шифрованием. Она командует подсистеме шифрования, что её надо прекратить обрабатывать указанный поток данных, вернуться к его началу, и подготовиться к его обработке, как будто ничего раньше и не было. "Кнопка перемотки на начало", в общем. И её использование не вызывает ни малейших проблем даже для начинающего программиста --- один оператор BIO_reset(X), и можно начинать делать с X какие-то более интересные вещи.

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

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

Проходит ещё пол-жизни. Тот начинающий я, и тот опытный я, и тот эксперт, только-только пришедший в проект --- они уже в далёком прошлом. Вы представляете, что такое 10 лет в одном программистском проекте, бить лбом одну стену, хоть и в разных её местах? А 15? А ещё побольше? Хо-хо, я тоже когда-то думал, что представляю заранее. Мы уже давно не работаем над проектом, мы живём в нём. Коллеги успевают жениться, развестить, вырастить детей, пережить кто 9/11, а кто три госпереворота в Бишкеке. Кто-то вложился в cтуденческую шарагу под названием, как её, Facebook, но потом решил, что облажался, и убежал оттуда обратно в кэш. В честь кого-то назвали самый лучший сорт марихуаны. Ещё они успевают попасть насмерть под машину, словить рак, ослепнуть... в общем, продемонстрировать не только то, что "человек смертен внезапно", это полбеды, но человек внезапно теряет контроль над "своим" проектом. А вот это уже совсем плохо, ведь из всей моей работы только один этот проект и останется хоть как-то в памяти человечества. Цедерквист --- это который "The Cederqvist", а вот Иван Михайлов --- это который SPARQL в Virtuoso. Будет ведь обидно, если после меня проект начнут курочить менее аккуратно, он начнёт терять нынешнюю красоту и прочность, и обнаружится, что такого риска "попадания в менее заботливые руки" я не предусмотрел.

И с этой подспудной мыслью о рисках будущих десятилетий я вкорячиваю некрасивые нудные проверки после шести BIO_reset()-ов, ещё ни разу не сбойнувших у миллионов пользователей с 2004-го года.

Питерские показывают класс

Сидел сегодня на семинаре по компиляторам и языкам программирования. Один из докладов был Юрия Шейнина и Алексея Сыщикова (питерский универ аэрокосмического приборостроения), про тулчейн VGL. Они разработали специальный язык программирования для многоядерных сред, чем-то похожий на SGL, не он такой первый придуман и не он последний, но мне очень-очень-очень понравилась одна особенность их работы, нечастая в наших академических реалиях. Они дожали дело не до прототипа, и даже не до компилятора с рантаймом; и даже не до компилятора с рантаймом, продолжающих работать у посторонних людей, если разработчика нет в комнате --- они довели дело до именно комплектной среды разработки с отладчиками, средствами профилирования и т.д., до продукта, который можно внедрять к удовольствию тех, кто будет с ним работать.

В армии США есть такая устоявшая фраза в характеристиках на людей --- "smart and get things done". Не просто умный, и не просто доделывает работу до конца, а именно два в одном. В нашем канцелярите точного аналога нет, а зря. И вот эта работа по VGL --- это как раз хороший пример того, как smart-and-get-things-done люди добиваются законченного результата.

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

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

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

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

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

Collapse )

Обработка больших временных рядов в современных СУБД

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

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

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

Collapse )

(no subject)

Хорошая алгебра придумалась, для неполных/ленивых вычислений. Наглядная. Пять значений истинности: "да"; "нет"; "вообще ничего"; "или да, или нет", "а чорт его знает". С абсолютно понятными операциями. И к этим значения при необходимости сводятся выражения уже не "истинностной" алгебры, в которой счёт значений идёт уже на сотни.

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

Ленточка для бейджика ценой 6500 евро в год

IMG_2793_X_SML.jpg
Мой нежно любимый работодатель, OpenLink Software, назначил меня представителем в группу подготовки стандарта SPARQL 1.2 в World Wide Web Consortium (W3C). Там какое-то тихое сумасшествие на сей раз --- за первый месяц существования группы в неё уже набилось 90 желающих чего-нибудь усовершенствовать в несчастном SPARQL-е. Само собой, "одноранговый" комитет из 90 человек вдесятеро превосходит тот предел Сирила Паркинсона, после которого он становится бесполезен, поэтому внутри этого "Privy Council" сам собой сформируется "Cabinet", в котором и будет что-то решаться в окончательном виде. Состоять Cabinet будет в основном из тех, кто уже написал процесоры к предыдущим версиям SPARQL. В любом случае будет весело --- но только тем, кто интересуется базами знаний.

В связи с этим первый опрос в этом жжурнале:

Писать ли про всякие базы знаний, SPARQL и внутреннюю кухню W3C?

Писать про всё интересное подряд
27(84.4%)
Только конспекты лекций и техническую всячину, без подробностей про W3C
0(0.0%)
Только если что-то забавное, вроде ещё одной карты для марсиан
5(15.6%)


Upd.: Ted Thibodeau назначен ещё одним представителем OpenLink Software в ту же группу, в связи с чем моя ленточка подешевела до 3250. Все равно дорогое удовольствие, как ни крути.

(no subject)

Раз мы с женой программисты, 0x10-я годовщина свадьбы объявляется круглой.

(no subject)

Анамнез.

[СЛАЙД]
Аристотель, судя по всему, знал всё, что было известно европейской цивилизации того времени.
Это было очень удобно для окружающих -- ему можно было задать вопрос на любую тему и получить или немедленный ответ, или ссылку на книгу, или и то и другое.
Он был гуглом своей эпохи, и даже лучше, чем гуглом, так как он не просто давал релевантные ссылки, а сообщал некоторые связные знания.
К сожалению, Аристотель был последним человеком с настолько исчерпывающими знаниями обо всём -- сумма знаний продолжала расти.

После смерти Аристотеля в 322 до н.э. проблема доступа к знаниям встала с новой остротой, но решение уже было известно.
[СЛАЙД]
Один из его учеников, Деметрий Фалерский, где-то в 300 г до н.э. выбил у царя Египта Птолемея I грант на несусветную глупость -- копирование всех доступных книг и размещение их в одном общедоступном хранилище.
То, что сначала казалось глупостью, при Птолемее II Филадельфе уже стало чудом света.

Следующие две с лишним тысячи лет ничего существенно нового не появлялось.
Знания распространялись в форме книг и хранились в библиотеках.

[СЛАЙД]
В 1945 году Ванневар Буш в статье "As We May Think" предположил, что знания можно будет распространять в виде отдельных небольших документов, снабжённых большим количеством перекрёстных ссылок.
Если разместить все документы мира в одном хранилище и полностью автоматизировать получение текста документа по ссылке на него в другом документе, то читатель не будет ограничен текстом одной книги -- содержимое хранилища образует один связный гипертекст, доступный для чтения в произвольном порядке.
Memex.
Описывая возможную реализацию гипертекста, Ванневар предположил, что создание гипертекста станет возможным благодаря непрерывному совершенствованию оптики и фоточувствительных материалов для микрофильмирования, благодаря чему любой желающий сможет разместить все документы мира в одной комнате, а обновления для этого хранилища получать по подписке наподобие газеты.
Он немного ошибся -- мы используем технологии микрофильмирования не для копирования конкретных документов, а для производства оперативной памяти, которую можно записывать многократно.
Кроме того, благодаря изобретению транзистора и прогрессу средств дальней связи мы храним гипертекст в распределённой системе, а не копируем его целиком для каждого пользователя.

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

[СЛАЙД Уместно продемонстрировать разницу между значениями, данными и знаниями.]

Минский предположил, что в человеческой памяти знания хранятся, скорее всего, в чём-то наподобие фреймов.
[СЛАЙД]
Из популярных ныне языков програмирования для иллюстрации больше всего подходит JavaScript -- фреймы Минского представимы объектами JavScript, заполнение пустого фрейма конкретными данными очень похоже на конструирование объекта по образцу, а связи между фреймами представляются ссылками.
Эта модель очень удобна для программирования -- нам легко представлять такие структуры данных потому что именно ими мы и оперируем с рождения, разве что менее формальным образом.

Несмотря на простоту для человеческого мозга, фреймовое представление оказалось сложновато для непосредственной реализации алгоритмов искусственного интелекта на имеющихся языках программирования.
Первым уткнулся в эти проблемы Уинстон, когда писал решатель задач для "мира кубиков".
[СЛАЙД]
"Мир кубиков" представлял собой большую коробку с запасом разноцветных кубиков, призм, и цилиндров из конструктора для малышей.
Единственным активным обитателем этого мира был робот-кран с телекамерой и захватом.
Задачей программы было составить представление о содержимом коробки, распознав отдельные кубики, понять отношения между ними, вроде "зелёный цилиндр непосредственно опирается на синий куб", составить план действий для постройки заказанной конструкции из кубиков и управлять краном, разумно реагируя на непредвиденные отклонения от плана.
Уинстон понял, что орграф из вершин-фреймов, в которых хранятся свойства-литералы вполне можно заменить графом, в котором вершинами являются и объекты и литералы.
При такой замене рёбер прибавилось, зато каждая вершина стала маленькой.
Единственное отличие между объектами и литералами заключалось в том, что дуги могли входить и в вершины-объекты и в вершины-литералы, но выходить могли только из объектов.
Кроме того, в модели Уинстона дуга графа тоже могла быть использована как вершина.

Попробовали -- понравилось.
Робот таскал кубики, бухгалтерия MIT оформила следующий грант, Уинстон выпустил сборник "Психология машинного зрения".
Представление знаний в этом виде популярно до сих пор и его вариант под названием RDF стал стандартом W3C.
[СЛАЙД Отличия, реификация, удобство смешивания]

В настоящее время в мире накоплены терабайты знаний в формате RDF.
Большие объёмы знаний доступны бесплатно, например, в рамках Linking Open Data Project.
[СЛАЙД]

Для запросов к базам знаний разработан и утверждён в качестве стандарта язык SPARQL, для него существуют более десятка реализаций на все случаи жизни, и постоянно появляются новые точки доступа к знаниям и новые реализации SPARQL.
[СЛАЙД]

Так что если я -- биолог, и мне нужны знания о всех известных науке протеинах, то я бесплатно скачиваю сотню гигабайт с UniProt и сопутствующих источников, ставлю Virtuoso Open Source, и наслаждаюсь халявой.


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


[СЛАЙД]
Первые грабли.
Чистая RDF-модель неудобна для больших хранилищ.

Фундаментальные недостатки RDF в частности и представлений знаний графами в целом -- низкая производительность в пересчёте на доллар оборудования, плохая масштабируемость, плохая локальность доступа и как следствие плохая производительность на кластерах.
Да, мы имеем терабайты RDF, но мы не можем ни загрузить их в одну большую машину, ни организовать эффективные распределённые вычисления.
Кроме того, RDF мы меряем терабайтами, в то время как суммарный объём реляционных баз данных исчисляется петабайтами.
Да, для всех популярных СУБД существуют средства экспорта данных в формате RDF, но в результате такого экспорта мы крупное хранилище данных превращаем в "хоронилище знаний".
Это хоронилище не сможет выполнить ничего, кроме выполения тривиальных запросов, которые могли быть выполнены и на исходной СУБД средствами SQL, причём эффективнее.

Интересно отметить, что все крупные хранилища RDF основаны на реляционных СУБД.
[СЛАЙД]
Дуги графа RDF хранятся в строках таблицы с отдельными колонками для субъекта, предиката и объекта.
Почему же запросы над этой таблицей оказываются медленнее, чем запросы над таблицами с исходыми даными, при том, что суммарный объём данных совпадает, а оборудование и вовсе то же самое? Разница в том, что исходная база даных была тщательно спроектирована для конкретного набора данных и конкретных приложений, таблицы и индексы сконфигурированы так, чтобы встречающиеся на практике запросы выполнялись максимально быстро.
В то же время хранилище RDF не оптимизированно ни под одну конретную задачу -- ему все равно, что именно хранить.

Итак, мы имеем стандартный язык запросов SPARQL и стандартное представление знаний в виде RDF, но не можем масштабировать хранилища RDF до требуемого объёма.
Следовательно, надо не переводить данные в RDF, а переводить SPARQL в SQL.
Если мы научимся транслировать любой данный SPARQL запрос в несколько SQL-запросов к подходящим реляционным базам данных, то сможем совместить лёгкость использования SPARQL с производительностью классических СУБД.

Мы можем ещё упростить задачу, если будем транслировать один SPARQL запрос в ровно один SQL-запрос, но этот запрос будет выполнять СУБД с виртуальной схемой.
Такая СУБД умеет обеспечить доступ к таблицам других СУБД так, как будто эти таблицы хранятся локально.
Для этого она перенаправляет фрагменты исходного запроса на соответствующие СУБД, получает частичные ответы, при необходимости сохраняет их во временные таблицы и самостоятельно выполняет заключительные вычисления.

Наличие трансляции из SPARQL в SQL не избавит нас от необходимости транслировать данные из реляционного представления в RDF, только мы будем делать это не заранее и для всего объёма данных, а по запросу и только для тех данных, для которых это действительно необходимо.

Обычно мы сопоставляем каждой строке публикуемой таблицы одну вершину RDF.
[СЛАЙД]
Идентификаторы вершин вычисляются на основе значений ключей и, возможно, зависимых данных; например, для пункта 5 заказа 312 идентификатор может быть http://example.com/tpcd/lineitem/312/5 .
Мы переводим значения SQL в литералы; обычно численное или строковое значение остаётся неизменным, меняется только тип и язык, но возможны и вычисления.
Отношения между строками таблиц превращаются в дуги RDF графа.

Трансляция релационной базы данных в RDF описывается в виде
- списка правил перевода имён вершин,
- списка правил преобразований литералов и
- списка правил создания дуг.

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

Чаще всего, правило для имени можно задать просто форматной строкой:

create iri class tpcd:lineitem "http://example.com/tpcd/lineitem/%d/%d"
(in l_orderkey integer not null, in l_linenumber integer not null) .

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

[СЛАЙД]
create iri class oplsioc:grantee_iri using
function DB.DBA.RDF_DF_GRANTEE_ID_URI (in id integer) returns varchar ,
function DB.DBA.RDF_DF_GRANTEE_ID_URI_INVERSE (in id_iri varchar) returns integer .

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

create literal class oplsioc:grantee_lit using
function DB.DBA.RDF_DF_GRANTEE_ID_LIT (in id integer) returns varchar ,
function DB.DBA.RDF_DF_GRANTEE_ID_LIT_INVERSE (in id_iri varchar) returns integer
option (bijection) .

Наcтало время разобраться с дугами. Дуга определяется четырьмя праметрами -- в каком именно графе она находится, откуда она выходит, куда приходит и какое свойство представляет.
Правило создания дуги состоит из четырёх параметров, каждый из которых может быть либо константой, либо правилом перевода, и для каждого аргумента каждого правила перевода указывается таблица и колонка, откуда берутся значения.
Если дуги должны создаваться не для всех строк таблицы, то можно дополнительно указать фильтр -- булевское выражение.

[СЛАЙД]
Простой пример:

FROM DB.DBA.SYS_USERS as user
WHERE (^{user.}^.U_IS_ROLE = 0)
GRAPH <http://example.com/security>
SUBJECT oplsioc:user_iri (user.U_ID)
PREDICATE sioc:email
OBJECT user.U_E_MAIL

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

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

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

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

В-третьих, для данного образца дуг из SPARQL-запроса мы можем найти все правила дуг, которые в принципе могут создать дуги, соответствующие данному образцу.
Поскольку для каждого отдельного правила мы можем сделать SQL-запрос, возвращающий все дуги, объединение этих запросов вернёт все дуги, соответствующие образцу из SPARQL-запроса.
Возможно, объединённый SQL вернёт и лишние дуги в довесок к нужным, но лишнее можно отфильтровать.

SPARQL-запрос является реляционным выражением с образцами дуг в качестве атомарных выражений.
Разумеется, раз мы можем транслировать любой образец в SQL, мы можем транслировать в SQL и всё реляционное выражение.
Таким образом, сервер с виртуальной схемой, например, OpenLink Virtuoso, может получить произвольный SPARQL-запрос, транслировать его в SQL, распределить выполнение этого запроса между несколькими реляционными базами, и вернуть ответ.
Более того, при таком подходе SPARQL-запросы могут быль использованы везде, где синтаксис SQL допускает использование SQL-запроса или подзапроса.
Таким образом, клиентами базы знаний могут быть любые имеющиеся SQL-клиенты, например, SPARQL прекрасно выполняется через ODBC или SOAP.

Если всё так просто, то почему же нет массового внедрения? Оказывается, на пути такой "бесхитростной" трансляции лежат...

[СЛАЙД]
Вторые грабли.
"Наивный" SQL невозможно оптимизировать.

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

[СЛАЙД]
Расмотрим простой SPARQL запрос: найти все имена и адреса всех известных поставщиков всех деталей.

select * where {
?s foaf:name ?name .
?s sioc:email ?email .
?s tpcd:has-part ?part }

При попытке выполнить наивный SQL, сервер "уходит в астрал".
При отладке обнаруживается, что свойство foaf:name имеют не только поставщики, а вообще все люди и организации, известные тем или иным приложениям сервера.
Адреса электронной почты тоже могут быть получены из десятков источников.
Даже, казалось бы, редкое свойство tpcd:has-part имеют не только поставщики деталей, но и строки заказов на эти детали.
В результате вместо ожидавшегося произведения содержимого трёх таблиц мы получаем произведение объединений нескольких десятков таблиц.

Тут самое время вспомнить "Психологию машинного зрения".
Анализ фотографии кучи кубиков требует перебора экспоненциального количества вариантов, тем не менее человек её успешно решает.
Это значит, что человек использует более сложный алгоритм, который позволяет учитывать большее число параметров и естественные ограничения, связанные с этими параметрами.
Тогда каждый отдельный этап решения стоит дороже, зато дополнительные ограничения непрерывно отсекают тупиковые варианты.
Задача по-прежнему будет иметь степенную сложность, но со степенью, скажем, 1.05 вместо 3.
Сцена с кубиками, например, успешно распознаётся, если у кубиков кроме рёбер искать ещё и тени.

В нашем случае естественными ограничениями оказываются области значений, создаваемых правилами перевода имён вершин и литералов.
Очевидно, что ни одна дата не равна ни одному числу с плавающей точкой, стало быть бесмысленно перемножать две таблицы с равенством между колонкой дат и колонкой.
Менее тривиальным ограничением оказывается различие в форматах строк.
[СЛАЙД]
Если удаётся доказать, что ни одна строка не может быть получена использованием формата http://example.com/tpcd/lineitem/%d/%d и формата http://example.com/tpcd/lineitem/%U, то произведение таблиц с таким равенством в фильтре будет пустым.
Используются и другие ограничения, столь же простые и понятные.
Чем больше ограничений, тем лучше, поэтому полезно "рассказать" системе как можно больше про используемые данные.
Например, в декларацию правила перевода имён можно добавить реально создаваемые форматы строк, чтобы пользовательские функции из "чёрных ящиков" стали "серыми".

[СЛАЙД]
create iri class oplsioc:grantee_iri using
function DB.DBA.RDF_DF_GRANTEE_ID_URI (in id integer) returns varchar ,
function DB.DBA.RDF_DF_GRANTEE_ID_URI_INVERSE (in id_iri varchar) returns integer
option ( bijection ,
returns "http://example.com/sys/group?id=%d"
union "http://example.com/sys/user?id=%d" ) .

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

Для получения эффективного запроса мы сначала раскрываем скобки, заменяя произведение сумм суммой произведений, а затем используем естественные ограничения, чтобы выкинуть нулевые произведения.
Эта оптимизация повторяется циклически, пока от неё есть польза.
Результатом является длинный и непонятный SQL-запрос, который, тем не менее, может быть эффективно исполнен. Мешают только...


[СЛАЙД]
Третьи грабли.
"Умный" SQL тоже невозможно оптимизировать.

Произведение трёх сумм по десять слагаемых в каждой сумме требует 33 операции.
Раскрытием скобок и сокращением можно получить от нуля до четырёх тысяч операций, в зависимости от успешности оптимизации.
Результатом компиляции SPARQL-запроса из 10 строк может быть и сотня-другая килобайт SQL-текста. -- уж как повезёт.
Получив эти сто килобайт, SQL-оптимизатор умирает, ведь его проектировали из расчёта на запросы, написанные человеком, а они почти никогда не бывают длиннее двух страниц в силу органиченности человеческих способностей.
У меня были случаи, когда запрос компилировался десятки минут, после чего успешно выполнялся за десятые доли секунды.
[СЛАЙД]
Хуже всего, что один из самых популярных запросов, и уж точно самый короткий -- 'DESCRIBE ?:subject_argument' -- порождает чудовищно длинный SQL-запрос.
Можно, конечно, ждать прогресса в SQL-оптимизации, но достижение даже текущих недостаточных характеристик оптимизаторов потребовало двадцати лет исследований и миллиарды вбуханных в индустрию долларов.

Мы упрощаем работу оптимизатора одновременно тремя способами.

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

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

В третьих, мы вообще не стали компилировать DESCRIBE в чистый SQL.
Да, двумя первыми хитростями мы уменьшили и среднее количество произведений, и средне количество объединений в запросе, но DESCRIBE всё ещё непреодолимо сложен.
В самом деле, один запрос должен уметь выдать данные о любом типе субъектов, какие только могут храниться в даной базе знаний, причём один и тот же субъект может быть, например, адресатом электронной почты, покупателем, преподавателем и организатором конференции, и про него надо рассказать всё.
Поэтому вместо компиляции одного универсального суперзапроса мы вызываем хранимую процедуру, которая ломает всю идеологию конвейера -- она вызывает SPARQL-компилятор во время SQL-исполнения.

[СЛАЙД]
Эта процедура получает субъект как аргумент.
Проверяя этот субъект на соответствие естественным ограничениям, процедура строит список всех правил создания дуг, которые могут этот субъект описывать.
Этот список не уникален для каждого конкретного субъекта, наоборот, он будет естественным образом совпадать внутри каждой группы схожих субъектов, например ровно один список для всех непериодических комет или два-три варианта для всех профессоров, имеющих электронную почту.
Если после последнего старта сервера ещё никто не интересовался непериодическими кометами, то запрос про первый субъект такого рода приведёт к созданию и компиляции специальной хранимой процедуры со вставками SPARQL, которая будет уметь описывать только кометы.
Если интересовался, то готовая процедура будет извлечена из кэша.
В обеих случаях прогон этой процедуры эффективно вычислит полное описание данного конкретного субъекта.

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

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


Четвёртые грабли.
Латентность кластера в десятки раз превышает чистое время исполнения.

Когда SPARQL-запрос был неэффективным и прокачивал через межмашинные соединения мегабайты лишних данных, лишние миллисекунды перед прокачкой каждого большого потока роли не играли.
Теперь доступ к таблицам из последовательного стал выборочным, объём прокачки упал на порядки, зато количество запросов увеличилось тоже на порядки.
Эффективно работающие одиночные машины при соединении в сеть стали умирать.
Помимо этого, обнаружилось, что хорошо бы на каждой машине со SPARQL-процессором разместить все те дуги, что хранятся в "родном" представлении, а не создаются на лету из реляционых данных.
Поскольку такое размещение привело бы к резкому удорожанию системы, хорошо бы разбить всю таблицу дуг на фрагменты и разместить, скажем, по 5% всех дуг на каждой из двадцати машин.
Но из-за низкой локальности доступа к RDF при таком разбиении латентность "убъёт" любую сеть. Плохо будет работать не только сеть из машин с недорогим Ethernet, но и дорогой кластер.

Решением стал новый механизм доступа к таблицам.
Теперь мы можем собирать обращения к таблицам в большие пакеты, и отправлять запросы и ответы не по одному, а пачками размером в десятки и сотни килобайт.
Таким образом мы имеем соответственно меньшее число пакетов и теряем соответственно меньше времени на латентность.
К сожалению, я должен ограничиться только основной идеей, поскольку описание реализации потребует отдельных лекций.
Реализация этой маленькой хитрости уже заняла год, и всё ещё годится только для внутреннего употребления, но через несколько месяцев поддержка кластеров будет достаточно надёжной для индустриального использования.


Нет повести печальнее на свете,
Чем повесть о затратах и бюждете.

Остался один маленький вопрос.
А зачем кто-то будет всё это внедрять у себя?

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

А нужен ли чистый SPARQL в бизнес-приложениях (BI -- Business Intelligence)?
Не нужен, так как для обработки бизнес-данных нужна серьёзная статистическая обработка, групировки, сортировки и прочие операции, обыденные для SQL, но отсутствующие в SPARQL.

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

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


Эпикриз.

Мы демонстрируем очень хорошую производительность на одиночных машинах вроде Quad Xeon / 16Gb RAM с размерами графов до миллиарда дуг.

Мы эффективно выполняем SPARQL-BI версии запросов из TPC-D, производительность многих запросов уже сравнима с производительностью SQL-версий тех же запросов.

Мы эффективно выполняем запросы над смесью реляционых данных и дуг.
Скажем, мы можем анализировать бизнес-данные из TPC-D с использованием CIA World Factbook.

Но главное -- мы обходим ограничения на объём баз знаний.
В качестве пробной нагрузки мы уже в мае загрузим в кластер двадцать миллиардов дуг теста LUBM 160000 со средней скоростью миллион дуг в секунду.
[СЛАЙД]
Завершив настройку, мы загрузим в него все формализованные знания мира, и откроем свободный доступ.
И в будущем какая-нибудь система автоматического доказательства теорем сможет хорошенько обследовать этот граф и определить, может ли человек мыслить.