Welche deklarative Sprache ist gut für die Analyse von baumartigen Daten?

Question

Ich denke über die Entwicklung eines Systems zur Durchführung hochparalleler Abfragen auf verschachtelten (aber Baum-ähnlichen) Daten. Die potenziellen Benutzer sind Datenanalytiker (insbesondere Physiker), keine Programmierer. Für die Benutzeroberfläche möchte ich eine bekannte Abfragesprache verwenden, um neue Sprachen zu vermeiden.

Die meisten der Daten wie folgt strukturiert sein würden (für Milliarden von event Strukturen das folgende Schema vorstellen):

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

Die Datenbank würde, nur gelesen werden und die meisten Abfragen wären Dinge wie:

• Dynamik der Strecke mit den meisten Hits mit Theta zwischen -2,4 und 2,4
• durchschnittliche Ladung aller Treffer mit der Zeit in 0-10 ps auf allen Spuren mit dem Impulse größer als 10 GeV/c
• gewichteter Durchschnitt Theta der beiden Spuren mit höchster Dynamik

et cetera. Gemeinsam ist diesen Abfragen, dass sie alle zu einem Skalar pro Ereignis aufgelöst werden, obwohl sie in die Arrays von Strukturen eintauchen, um dies zu tun. Sie führen "reduce" -ähnliche Operationen (allgemein fold in Scala, aggregate in Spark, DAF in SQL) über gefilterte, transformierte Teilmengen dieser Arrays durch. Ich konnte sie in Scala wie folgt schreiben:

// 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) 
} 

Warum nicht einfach Scala benutzen? Mein Programm ist in C implementiert und wird auf GPUs laufen. Was auch immer Scala mir bringen würde, wäre eine neu implementierte Untermenge - mit anderen Worten eine erfundene Sprache. (Das gleiche könnte für Haskell, Javascript oder eine andere Sprache gesagt werden, die Funktionen als Argumente verwendet.)

Diese Abfragen sollten auch deklarativ sein. Wenn ich zu viel von einer allgemeinen Programmiersprache implementiere, könnten Details wie die Reihenfolge von Funktionsaufrufen relevant werden.

Warum nicht einfach SQL verwenden? Ist es möglich, Abfragen wie die obigen einfach, so zu schreiben, dass sie für alle anderen als den Autor lesbar sind? Abfragen wie die oben genannten sind die Norm, keine komplexen Extreme.

SQL unterstützt geschachtelte Arrays von Strukturen, aber alle Beispiele, die ich von unter Verwendung dieser Unterstruktur finden kann, sind horrend kompliziert. Man muss die Ereignistabelle in eine Tabelle von Spuren auflösen (oder doppelt explodieren, um Treffer zu erhalten), und eine komplexe Buchhaltung wäre erforderlich, um nicht explodieren zu müssen und zu einem Skalar pro Ereignis zurückzukehren.

Ich glaube, ich SQL mit neuen Funktionen wie MAXIMAL(collection, function) verwenden könnte, die eine Struktur aus einem Array, ähnlich wie track[12] jedoch unter Verwendung der vom Benutzer bereitgestellten Funktion als eine Zielfunktion für die Maximierung zurückzukehren, minimiert, zu finden, mit dem oberen/unteren N, etc Ich glaube nicht, dass SQL unterstützt, Funktionen als Argumente zu übergeben. Wenn ich eine SQL schreibe, die das tut, wäre das nicht Standard.

Gibt es einen weit verbreiteten Dialekt von SQL, der Passing-Funktionen als Argumente unterstützt?

Oder gibt es eine andere deklarative Sprache, die ich berücksichtigen sollte?

Answer 1

ich gepostet in einem Kommentar früher, aber es hier zu bewegen.

Ich bin mit anderen auf die Verwendung einer Grafik-Datenbank. Ich kenne mich mit Neo4j-Abfragen nicht aus, aber ich erwarte, dass sie in der Lage sind. Ähnlich würde SPARQL für diese Art von Sache gut funktionieren.

Für die erste Abfrage, eine SPARQL-Abfrage könnte wie folgt aussehen:

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; 

Identifiers haben: Präfix auf sie, weil sie als URIs codiert werden müssen. Aber das ist ein internes Detail für den Wechsel zu RDF (das Datenformat für SPARQL-Datenbanken).

Die obige Abfrage führt Unterabfragen durch, weil Sie aggregieren (nach Anzahl) und dann erneut aggregieren möchten (mit dem Maximum der Anzahl). Aber Sie können sehen, dass alles auf eine SQL-ähnliche Weise behandelt wird und keine Nachbearbeitung erfordert.

Answer 2

Scala Beispiel 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 
} 

Potential 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 

Oder mit APPLY von 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 

Das ist sehr verschachtelt ist, die Ich finde es schwieriger zu lesen und zu pflegen als die CTE-Version. Aber wird wahrscheinlich mit einem sehr ähnlichen Ausführungsplan enden.

Oracle und andere Dialekte haben andere Möglichkeiten zur Implementierung ähnlicher "Funktionen" wie MS SQL Server mit APPLY.

Answer 3

Auch wenn Sie reine baumartige Datenstrukturen haben, sollten Sie sich eine Graphdatenbank ansehen. Insbesondere unterstützt Neo4j eine deklarative Abfragesprache als Cypher bekannt:

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

Titan könnte auch für den Maßstab interessant sind Sie sprechen, es unterstützt Gremlin aus dem Apache TinkerPop Projekt, die Multi-Plattform (aber nicht deklarativ):

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