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

Question

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

Большая часть данных будет структурирована следующим образом (представьте себе следующую схему для миллиардов 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 ГэВ/с
• средневзвешенная теты из двух дорожек с самым высоким импульсом

и так далее. Что общего у этих запросов, так это то, что все они решаются на один скаляр для каждого события, хотя они вникают в массивы структур, чтобы сделать это. Они выполняют «сокращение» как операции (обычно 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 и будет работать на графических процессорах. Независимо от того, что я приношу в Scala, это переопределенное подмножество - другими словами, изобретенный язык. (То же самое можно сказать и для Haskell, Javascript или другого языка, который сильно использует функции в качестве аргументов.)

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

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

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

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

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

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

Answer 1

Я отправил это в комментарий ранее, но перемещение его здесь.

Я с другими пользователями, использующими базу данных графа. Я не знаком с запросами 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-способом и не требует последующей обработки.

Answer 2

Scala Пример 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.

Answer 3

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

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

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

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