什么声明式语言擅长分析树状数据？

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
         |
         +--- ...

数据库将是只读的，大多数查询将是这样的：

theta 在 -2.4 和 2.4 之间时点击次数最多的曲目动量
在动量大于 10 GeV/c
具有最高动量的两条轨道的加权平均 theta

等等。这些查询的共同点是它们都针对每个事件解析为一个标量，尽管它们会深入研究结构数组来执行此操作。它们执行 "reduce" 类操作（通常在 Scala 中为 fold，在 Spark 中为 aggregate，在 SQL 中为 DAF）跨越这些数组的过滤、转换子集。我可以像这样用 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 支持结构的嵌套数组，但我能找到的所有使用子结构的示例都非常复杂。必须将 table 事件分解成 table 轨道（或双重分解以获得命中），并且需要一些复杂的计算来分解并返回到每个事件的一个标量。

我想我可以将 SQL 与新函数一起使用，例如 MAXIMAL(collection, function) return 来自数组的结构，类似于 track[12] 但使用用户提供的函数作为用于最大化、最小化、查找 top/bottom N 等的 objective 函数。我认为 SQL 不支持将函数作为参数传递。如果我写一个 SQL 这样做，那将是非标准的。

是否有广泛使用的 SQL 支持传递函数作为参数的方言？

或者我应该考虑另一种声明性语言吗？

Answer 1

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

或使用来自 MS SQL 服务器的 APPLY

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 和其他方言有其他实现类似 "functions" 的方法，因为 MS SQL 服务器用 APPLY.

完成

Answer 2

即使您拥有纯树状数据结构，您也可能想要查看图形数据库。特别是，NEO4J 支持一种称为 Cypher 的声明式查询语言：

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

对于您所说的规模，Titan 可能也很有趣，它支持来自 Apache TinkerPop 项目的 Gremlin，该项目是多平台的（但不是声明性的）：

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

Answer 3

我在之前的评论中 post 编辑了它，但将其移至此处。

我和其他人一起讨论图形数据库的使用。我不熟悉 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的方式处理的，不需要post-processing.

Answer 4

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)

什么声明式语言擅长分析树状数据？

What declarative language is good at analysis of tree-like data?

sql

programming-languages

declarative