Какой декларативный язык хорош для анализа древовидных данных?

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

Большая часть данных будет структурирована следующим образом (представьте себе следующую схему для миллиардов event структур):

event: struct
  |
  +--- timestamp: bigint
  +--- missing energy: float
  +--- tracks: array of struct
  |      |
  |      +--- momentum: float
  |      +--- theta angle: float
  |      +--- hits: array of struct
  |             |
  |             +--- detector id: int
  |             +--- charge: float
  |             +--- time: float
  |             +--- ...
  +--- showers: array of struct
         |
         +--- ...

База данных будет доступна только для чтения, и большинство запросов будут примерно такими:

  • импульс трека с наибольшим количеством хитов с тета от -2,4 до 2,4
  • средний заряд всех попаданий со временем в 0-10 пс на всех треках с импульсом более 10 ГэВ/c
  • средневзвешенная тета двух треков с наибольшим импульсом

и так далее. Общим для этих запросов является то, что все они разрешаются в один скаляр для каждого события, хотя для этого они углубляются в массивы структур. Они выполняют операции «уменьшения» (обычно fold в Scala, aggregate в Spark, DAF в SQL) для отфильтрованных преобразованных подмножеств этих массивов. Я мог бы написать их на Scala так:

// missing check for when zero tracks passed filter!
{event => event.tracks                      // get list of tracks
               .filter(abs(_.theta) < 2.4)  // in theta range
               .maxBy(_.hits.size)          // take the one with the most hits
               .momentum                    // return its momentum
}

{event => mean(
            event.tracks                    // get list of tracks
                 .filter(_.momentum > 10)   // in momentum range
                 .flatMap(_.hits)           // explode to hits
                 .filter(_.time < 10)       // in time range
                 .map(_.charge)             // return their charges
              )}                            // ... to the mean function

// again missing check for less than two tracks!
{event => val List(one, two) =              // unpack and assign "one" and "two"
              event.tracks                  // get list of tracks
                   .sortBy(_.momentum)      // sort by momentum
                   .take(2)                 // take the first two
          // now compute the weighted mean of structs "one" and "two"
          (one.theta*one.momentum + two.theta*two.momentum) /
              (one.momentum + two.momentum)
}

Почему бы просто не использовать Scala? Моя программа написана на C и будет работать на GPU. Какой бы Scala я ни привнес, это будет перереализованным подмножеством — другими словами, изобретенным языком. (То же самое можно сказать и о Haskell, Javascript или другом языке, который активно использует функции в качестве аргументов.)

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

Почему бы просто не использовать SQL? Можно ли легко писать подобные запросы, чтобы их мог прочитать кто угодно, кроме автора? Запросы, подобные приведенным выше, являются нормой, а не сложными крайностями.

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

Я полагаю, что мог бы использовать SQL с новыми функциями, такими как MAXIMAL(collection, function), которые возвращают структуру из массива, подобно track[12], но используя предоставленную пользователем функцию в качестве целевой функции для максимизации, минимизации, нахождения максимального/минимального N и т. д. Я не Не думаю, что SQL поддерживает передачу функций в качестве аргументов. Если я напишу SQL, который это делает, это будет нестандартно.

Существует ли широко используемый диалект SQL, поддерживающий передачу функций в качестве аргументов?

Или мне следует рассмотреть другой декларативный язык?


person Jim Pivarski    schedule 08.08.2016    source источник
comment
Ваши вложенные структуры — это просто дополнительные таблицы. У вас есть основная event таблица с уникальным идентификатором. Затем таблица track имеет внешний ключ для уникального идентификатора в event. Допускает отношения, в которых одна event строка связана с от нуля до многих track строк. То же самое относится к event:showers и track:hit и т. д. и т. д. Затем SQL обычно становится случаем объединения двух таблиц, затем агрегирования, присоединения этого результата к другой таблице и повторного агрегирования и т. д. и т. д.   -  person MatBailie    schedule 08.08.2016
comment
С точки зрения functions as arguments, это не будет нормальным для любого диалекта SQL. Некоторые из них имеют собственную среду CLR и позволяют делать некоторые волшебные вещи, но даже если вы заставите ее работать, это не будет чем-то, что распознает стандартный разработчик SQL (актуально для вас с точки зрения поддержки) . Но в MS SQL Server есть APPLY, который позволяет вам инкапсулировать функции другим способом, который может вам подойти.   -  person MatBailie    schedule 08.08.2016
comment
Было бы легко писать/легко читать, если бы каждый запрос представлял собой соединение + агрегацию? Если вы можете показать, как будут выглядеть SQL-запросы (например, мои три примера), и это не ужасно, это тот ответ, который я ищу. (Извините за субъективность ужасного, но я думаю, вы знаете, почему это мой критерий.)   -  person Jim Pivarski    schedule 08.08.2016
comment
Если вы добавите комментарии (псевдокод, независимый от языка, дружелюбный к идиоту (мне)) к своим примерам Scala, тогда я (попытаюсь) перевести их на SQL.   -  person MatBailie    schedule 08.08.2016
comment
Извиняюсь; Я выбрал Scala, чтобы быть конкретным и лаконичным. Подобные функции на месте также лаконичны в Haskell и Julia, и они распространены в R и Javascript, хотя вам нужно каждый раз писать функцию целиком. (В Python вы должны написать слово лямбда целиком.) Я думаю, что такого рода запросы подходят для цепочек функторов, поэтому я спрашивал о функциях в качестве аргументов.   -  person Jim Pivarski    schedule 08.08.2016
comment
Действительно, SQL имеет другую направленность и не совсем лаконичен. Но за десятилетия адаптировался, чтобы быть намного лучше аналитических запросов. Я перевела первый запрос, но у меня есть работа, я попробую следующий после встречи.   -  person MatBailie    schedule 08.08.2016
comment
Смотрите мой комментарий под ним; это пример того, что я считаю сложным. Возможно, нам следует подождать, чтобы увидеть, может ли кто-нибудь предложить другой декларативный язык. Должны быть другие, у которых такой запрос в центре внимания... (Спасибо за помощь, однако!)   -  person Jim Pivarski    schedule 08.08.2016
comment
Почему вы снова исключили Haskell или другие функциональные языки? Если вы работаете на GPU и с кратким кодом, и не изобретаете что-то новое, ваши приоритеты? Казалось бы, функциональный язык идеально подходит...   -  person MatBailie    schedule 08.08.2016
comment
Давайте продолжим обсуждение в чате.   -  person Jim Pivarski    schedule 08.08.2016
comment
Вы проверили neo4j.com/docs/developer-manual/current/cypher как синтаксис, поддерживающий деревья вроде SQL?   -  person fncomp    schedule 31.08.2016
comment
@fncomp Большое спасибо, что указали на это! Я прочитал спецификацию, и хотя я думаю, что она будет очень полезна для графических запросов, где вы ищете новые структуры, в моем случае структура исправлена, и я не вижу простого способа чтобы сопоставить мои запросы с этим. Но все равно спасибо, это то, что я ищу; Мне просто нужно найти (или сделать) правильный.   -  person Jim Pivarski    schedule 01.09.2016
comment
Круто, может хоть что-то вдохновит. Увидимся на Стрэнджелупе :-)   -  person fncomp    schedule 02.09.2016


Ответы (4)


Я писал это в комментарии ранее, но перенес сюда.

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

Для первого запроса запрос SPARQL может выглядеть так:

PREFIX : <http://yournamespace.com/accelerator/> .

SELECT ?momentum (MAX(?hitcount) as ?maxhits)
WHERE {
    SELECT ?momentum (COUNT(?hits) AS ?hitcount)
    WHERE ?track :momentum ?momentum .
          ?track :theta ?theta .
          FILTER (?theta > -2.4 AND ?theta < 2.4) .
          ?track :hits ?hits
    GROUP BY ?track
}
GROUP BY ?momentum;

Идентификаторы имеют префикс :, потому что они должны быть закодированы как URI. Но это внутренняя деталь для перехода на RDF (формат данных для баз данных SPARQL).

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

person PaulaG    schedule 09.09.2016
comment
Я хочу углубиться в это немного глубже, но пока это выглядит как лучший вариант. RDF и SPARQL удовлетворяют моим критериям стандарта: они определены W3C. Этот синтаксис запроса не выглядит слишком обременительным и довольно близок к замыслу. XML больше соответствует древовидным данным, чем общий график, даже несмотря на то, что мы никогда не представляли наши данные в XML из соображений производительности. - person Jim Pivarski; 09.09.2016
comment
Следует отметить, что RDF не имеет ничего общего с XML. Первоначальный выпуск RDF был выпущен вскоре после того, как XML был стандартизирован, и W3C считал, что использование их собственного универсального формата сериализации было хорошей демонстрацией того, что они верят в него. Это привело к тому, что первоначальным форматом сериализации для RDF стал RDF/XML. К сожалению, с этим было множество проблем. Несколько человек в сообществе XML думали, что это подрывает XML, многие люди думали, что RDF привязан к XML, и это был ужасный формат. Сегодня рекомендуется использовать Terse Triples Language: TurTLe - person PaulaG; 10.09.2016
comment
У меня есть еще одно обязательство во время несессий Strangeloop, но, пожалуйста, не стесняйтесь разыскать меня, чтобы поговорить об этом. - person PaulaG; 10.09.2016

JSONiq был разработан именно для запросов деревьев, даже и особенно когда данные сильно вложены и разнородны. Он на 95% основан на стандарте W3C.

Rumble — это реализация JSONiq с открытым исходным кодом, которая работает с коллекциями из миллиардов записей. Он использует Spark под капотом, но полностью прозрачным для пользователя (и скрытым от него).

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

Запрос 1:

(
  for $track in root-file("events.root", "Events").tracks
  where abs($track.theta) lt 2.4
  order by size($track.hits) descending
  return track
)[1].momentum

Запрос 2:

root-file("events.root", "Events").tracks[$$.momentum gt 10].hits[][$$.time lt 10].charge

Запрос 3:

let $tracks := (
    for $track in root-file("events.root", "Events").tracks
    order by $track.momentum
    return $track
  )[position() le 2]
return
  sum(
    for $t in $tracks
    return $t.theta * $t.momentum
  ) div sum($tracks.momentum)
person Ghislain Fourny    schedule 17.03.2020

Даже если у вас есть чистые древовидные структуры данных, вы можете захотеть взглянуть на базу данных графа. В частности, NEO4J поддерживает декларативный язык запросов, известный как Cypher:

https://neo4j.com/developer/cypher-query-language/

Titan также может быть интересен для масштаба, о котором вы говорите, он поддерживает Gremlin из проекта Apache TinkerPop, который является мультиплатформенным (но не декларативным):

http://tinkerpop.apache.org/docs/3.0.1-incubating/#preface

person PDH    schedule 08.09.2016
comment
Единственная причина, по которой меня беспокоит избыточность (представление графа содержит деревья и многое другое), заключается в том, что вам в конечном итоге приходится обращаться к нерелевантным понятиям в каждом запросе. Преимущество DSL в том, что он несколько оптимизирован. Я смотрел на Cypher и Gremlin и думал о том, как будут выглядеть эти запросы: похоже, вам придется специально указывать, что события содержат треки, когда вы хотите получить конкретный трек из события. Но события всегда содержат треки... - person Jim Pivarski; 09.09.2016

Скала Пример 1...

// missing check for when zero tracks passed filter!
{event => event.tracks                      // get list of tracks
               .filter(abs(_.theta) < 2.4)  // in theta range
               .maxBy(_.hits.size)          // take the one with the most hits
               .momentum                    // return its momentum
}

Возможный SQL....

WITH
   hit_stats
AS
(
   SELECT
       hit.track_id,
       COUNT(*)    as hit_count
   FROM
       hit
   GROUP BY
       hit.track_id
),
   track_sorted
AS
(
    SELECT
       track.*,
       ROW_NUMBER() OVER (PARTITION BY track.event_id
                              ORDER BY hit_stats.hit_count DESC
                         )
                            track_ordinal
    FROM
       track
    INNER JOIN
       hit_stats
           ON  hit_stats.track_id = track.id
    WHERE
           track.theta > -2.4
       AND track.theta <  2.4
)
SELECT
    *
FROM
    event
INNER JOIN
    track_sorted
        ON  track_sorted.event_id = event.id
WHERE
    track_sorted.track_ordinal = 1

Или используя APPLY из MS SQL Server

SELECT
   event.*,
   track.momentum
FROM
   event
OUTER APPLY
(
    SELECT TOP 1
        track.*,
        stat.hit_count
    FROM
        track
    OUTER APPLY
    (
        SELECT
            COUNT(*) hit_count
        FROM
            hit
        WHERE
            track_id = track.id
    )
        stat
    WHERE
            track.event_id = event.id
        AND track.theta    > -2.4
        AND track.theta    <  2.4
    ORDER BY
       stat.hit_count DESC
)
   track

Это очень вложенное, что мне сложнее читать и поддерживать, чем версию CTE. Но, скорее всего, в итоге получится очень похожий план выполнения.

Oracle и другие диалекты имеют другие способы реализации подобных «функций», которые MS SQL Server выполняет с помощью APPLY.

person MatBailie    schedule 08.08.2016
comment
Хорошо, прежде чем продолжить, обратите внимание, что я пытался найти способ обойти сложный учет, пытаясь вернуться к одному скаляру для каждого события. Я имею в виду, вы создаете новые таблицы (hit_stats) и выполняете много работы с ids, чтобы снова собрать все воедино. - person Jim Pivarski; 08.08.2016
comment
@JimPivarski - SQL, как вы упомянули, является декларативным. Выражение может быть решено путем создания таблиц, но в данном случае вы создаете выражение (эта нотация называется Common Table Expressions). Затем они расширяются, как макросы, в запросе, в котором они используются, и СУРБД затем генерирует план выполнения, чтобы решить заявленную проблему с наименьшими возможными затратами. По сути, я просто говорю, что это используется только как помощь для выражения проблемного пространства, а не как выражение решения. Новые таблицы не создаются. - person MatBailie; 08.08.2016
comment
Способ, которым это решение, скорее всего, будет планироваться, заключается в том, что каждая дорожка имеет скалярную операцию, в которой количество обращений рассчитывается путем подсчета записей в индексе. Дорожки сортируются, и все, кроме дорожки с самым высоким рейтингом, отбрасываются. Наконец, этот трек присоединяется к его родительскому событию. (При условии, что количество обращений не изменится, количество обращений может кэшироваться в самой таблице дорожек.) - person MatBailie; 08.08.2016
comment
О, я не хотел сказать, что под капотом SQL-движка слишком много работы (зависит от реализации, я уверен). Я говорю чисто с точки зрения того, как это выглядит для пользователя. - person Jim Pivarski; 08.08.2016
comment
В MS SQL Server это может быть выражено более функционально. Но, скорее всего, будет тот же план выполнения. Дай мне две минуты. - person MatBailie; 08.08.2016
comment
Количество треков, ливней и хитов варьируется. Вот почему в моих примерах на Scala также отсутствует достаточная обработка ошибок, которая должна быть более лаконичной, чем Scala на языке, который я ищу. - person Jim Pivarski; 08.08.2016
comment
Переменная в том, что они меняются каждый раз при выполнении запроса? В этом случае мои запросы все еще работают, просто не могут сократить вещи с кэшированными значениями. - person MatBailie; 08.08.2016
comment
Извините --- количество треков варьируется от одного события к другому, а количество просмотров варьируется от одного трека к другому. Набор данных в целом неизменен. - person Jim Pivarski; 08.08.2016