5 ms·

PathQuery, Google's Graph Query Language

172 points by mpweiher 5y ago

pgt 5y ago
Curious that there is no mention of Datalog [^1] for graph traversal in the paper. To support multi-locale names in Datomic or Datascript-flavoured Datalog attractions_v1.pq would be written as (where :entity/locale is of type :db.type/ref): (d/q [:find ?id ?name ?lang :in $ ?type :where [?e :entity/type ?type] [?e :entity/locale ?loc] [?loc :locale/name ?name] [?loc :locale/lang ?lang] db #{"museum" "theme_park"}) => (["/z/38dwfnb8" "Museum of Modern Art" "en"] ["/z/38dwfnb8" "Museo de Arte Moderno" "es"] ...) You could store the locale inside the name string, but then you can't efficiently filter on it. If you want the whole shebang, can do `(pull ?id [*])`. It's not obvious in their example if the locale filtering is post-query or part of the unification. With only 4-tuple EAVT-style indices, you need an intermediate join to support compound values like ["Hello" "en"] if you want to query against the components, so I have been toying with making my own graph DB with 5-tuple (or more) extensible indices, e.g. EAXVT, where X would be the locale, but then index order matters. [^1]: http://www.learndatalogtoday.org/ http://www.learndatalogtoday.org/
- simongray 5y ago
  Clojure's Datalog ("Clojurelog") basically looks a whole lot like SPARQL written using Clojure data structure literals and they do reference SPARQL in the paper.
jerven 5y ago
Interesting read. I think there are some ideas in there that can be used for sparql 1.2. especially regarding external function definitions. On the other hand the sparql in the paper is decent but not excellent. The result is subtly different from the path query one, but I think fine for example use case.
MikeTaylor 5y ago
Strange that this paper doesn't even _mention_ GraphQL.
- simongray 5y ago
  I don't think GraphQL is used to query graph databases directly, is it? I've always understood it to be an API protocol that was built to serve some specific needs Facebook had (e.g. bundling multiple HTTP requests), not a full-on graph query language. I should probably mention that I don't really have extensive experience using it, though.
  - oliyoung 5y ago
    you're right, on every point
  - topicseed 5y ago
    I think it is used as foundation for DQL[0], the query language of Dgraph. But in and of itself, GraphQL isn't really built to query graph databases as you said. [0] https://dgraph.io/docs/query-language/graphql-fundamentals/ https://dgraph.io/docs/query-language/graphql-fundamentals/
  - AtNightWeCode 5y ago
    GraphQL is basically used as SQL queries over stupid API:s. 99% of the graph DB advocates does not even understand what problem the graph DB solves. Soooo funny to argue with people when you can say that, oh, yes, we did this 20 years ago with recursive CTE:s.
- contravariant 5y ago
  Probably because GraphQL (despite it's name) isn't made for querying graphs.
  - slver 5y ago
    Technically it is. But in a very restricted way. Any graph, when you traverse it from a specific node, with fixed depth, and you don't explicitly work with node references, but rather node "values", looks like a tree that sprawls from that node. Anyway, PathQuery is a completely different beast regardless.
mark_l_watson 5y ago
I was invited to work at Google in 2013 on an internal project using their Knowledge Graph. I had just written two books on RDF/SPARQL/linked-data and at first I was taken aback by the query language used at the time. However, when I realized how well the KG scaled and how fast the queries were, I became a fan. BTW, I think this paper is very well written. Graph queries is not an easy topic and their examples and text make the data types, syntax, and how to perform matches and aggregations easy to follow.
- ampdepolymerase 5y ago
  What are your thoughts on just using plain datalog/prolog?
  - mark_l_watson 5y ago
    I have only used datalog in the form of Clojure and Datomic on a consulting job about ten years ago. I used to be a huge Prolog fan, but I don't think that anyone has paid me to do Prolog develop in over 20 years. My largest Prolog project was porting a prototype AI planning system that I wrote in Common Lisp to ExperProlog. It took about 6 weeks to prototype the system in Common Lisp, and re-writing it in Prolog only took about two weeks. I noticed last month that someone was offering an online Prolog course using Swi-Prolog. That might be a good place to start.
  - lmeyerov 5y ago
    Having written a chunk of my phd in prolog and even a simplified implementation of one, I'm definitely a fan. At the same time, our startup (graphistry) works w/ teams needing to look at all sorts of graph data, including knowledge graphs like the topic here, and I'd be nervous about meeting the performance & scale needs with out-of-the-box prolog systems. Likewise, a lot of prolog's power comes from ideas like automatically backtracking search, and I can't imagine using that in most team environments. Datalog solves most of that :) My read of the paper is their semantics largely reduces to datalog. The most interesting semantic exception is their bounded recursion, which suggests they're doing optimizations normal datalog wouldn't. Likewise, graph workloads often have weird phenomena to optimize for in terms of expected queries & data, where I'm guessing datalog might fit semantically but not how people would normally implement an engine. The PathQuery paper carefully side-stepped all such discussion, so I've been curious. At Graphistry, we do end-to-end GPU stuff, so I've been thinking about this particular problem, and came to a similar conclusion of a datalog-ish subset being the most straightforward way to get more performance/$ for this kind of task.
atombender 5y ago
PathQuery looks a lot like GROQ [1], which is the query language used by the Sanity data store [2]. For example, one of the queries in the paper: @entities .[/type == (Id(/ museum ) , Id(/ theme_park ))] .{ id: ?cur require name: /name.[TextLang() == en ] @merge : events::GetInfo() } can be written something like: *[type == "museum" || type == "theme_park"] { id, name: select(name[lang == "en"] => name), ...{ // GROQ doesn't have functions, so GetInfo() // would need to be inlined here } } PathQuery is of course a lot more complex, but the basic structure seems very similar. One thing GROQ does not have yet is recursive querying of the type needed to traverse graphs, but this is on our roadmap to implement. We've published a public draft specification for GROQ, and hoping it will be adopted by more tools. For example, we already have an open-source JavaScript implementation of it. (Disclosure: I work on GROQ at Sanity.) [1] https://github.com/sanity-io/GROQ https://github.com/sanity-io/GROQ [2] https://www.sanity.io/ https://www.sanity.io/
- sanxiyn 5y ago
  It seems PathQuery's entire novelty is better handling of recursive querying for query optimization, but "details are admittedly not discussed herein". So the paper has a sort of weird feel. It goes like this: PathQuery is a good language, because it has good semantics and it is optimizable. Some words on its good semantics. We don't discuss how it is optimizable, but trust us, it is.
  - atombender 5y ago
    From what I can tell, PathQuery is also clever in how queries express the shape of the returned data, which we in GROQ call projection. For example, in GROQ you can do: *[type == "user"] { id, name, "slug": id + "-" + lower(name), "photos": photos[] { url, width, height } | order(position), "newestComment": *[_type == "comment" && author == ^.id] | order(createdAt desc)[0] { id, body } } PathQuery seems to give you similar tools in transforming data as part of your pipeline, which I think is how query languages should be like.
jalk 5y ago
Anybody know why a paper like this doesn’t include a date?
- chodeboy 5y ago
  I was asking myself the very same thing.
- CharlesW 5y ago
  In case you're just wondering how recent it is (vs. "Why is the date not in the PDF?"), the page says the submission date was 17 Jun 2021.
kayza 5y ago
Reminds me of GQL [2]. Anybody know the differences and or similarities? [2] https://www.gqlstandards.org/ https://www.gqlstandards.org/
- bionhoward 5y ago
  GQL is much more clear and readable while PathQuery is confusing and non semantic
netfl0 5y ago
Can someone explain why they did not mention SPARQL CONSTRUCT statements? I struggle with the notion that SPARQL isn’t “graphy” per their assertion. I may be missing something though. https://www.w3.org/TR/sparql11-query/#construct https://www.w3.org/TR/sparql11-query/#construct
staticassertion 5y ago
I feel like graph languages can be so esoteric. It would be nice to have something closer to RDF, but with filter syntax, and the ability to group filters. I've never built a language, so maybe I'm just crazy, but what's wrong with, say, https://gist.github.com/insanitybit/cd997e8d367889708edc3ec221b89430 https://gist.github.com/insanitybit/cd997e8d367889708edc3ec2... Basically I defined the subject in a sort of 'namespace' of constraints ("parent", "children", etc), and then the edge or predicate constraint on it. I guess it's easy to just "make up" a language, and implementing is the difficult part, and then it's like "ok well then how do you solve <some unanticipated problem because idk what I'm even talking about>" but also, graphql, as much as it isn't good for a database API, is also quite straightforward and familiar looking and I feel like taking something like rdf as a basis would be reasonable.
- Jeff_Brown 5y ago
  I wrote a language that's very close to natural language for writing to and querying a RSLT, a kind of higher order graph. https://github.com/JeffreyBenjaminBrown/hode/blob/master/docs/hash/the-hash-language.md https://github.com/JeffreyBenjaminBrown/hode/blob/master/doc...
Jeff_Brown 5y ago
Syntactically how does PathQuery compare to Gremlin?
adsharma 5y ago
I think people focus much on syntax and not enough on semantics. After working on 2-3 iterations of similar languages (sexpressions, clojure enhanced with pipe operator), my take away is to define an API (not a new language) and support multiple languages on top of it. I picked python and the API is here: https://github.com/adsharma/fquery/ https://github.com/adsharma/fquery/ https://adsharma.github.io/fquery/ https://adsharma.github.io/fquery/ Like SQL, DDL and DML should be separated too. https://adsharma.github.io/flattools-programs/ https://adsharma.github.io/flattools-programs/
snicker7 5y ago
One issue I have with query languages is how poorly they interact with the "host language" . SQL requires non-composable string templating or complex, low-performance ORM's. The only query languages that do this "right" are datalog (Datomic) and Q/K (KDB+, Shakti).
- fragile_frogs 5y ago
  I think RethinkDB also did a great job with ReQL: https://rethinkdb.com/docs/sql-to-reql/javascript/ https://rethinkdb.com/docs/sql-to-reql/javascript/
liminal 5y ago
I've tried using SPARQL in the past and found it to be very difficult. There are some aspects here that seem like improvements: - I really like that a query only operates on a single graph. Quads make what should be simple triple queries on a graph much harder than necessary in RDF/SPARQL. - I like the path-oriented declarative design. It seems like a declarative version of the imperative graph traversal libraries. - The inline creation of records based on state in a traversal is also intuitive. - The simple type system is a welcome change from RDF's xsd monstrosity It still seems to be missing some things. For example, they show a recursive query, but no way to return the actual path taken, only the start and end points (I also can't figure out how to do in SPARQL); I don't see a way to explore predicate relationships; is there a method for reification?

172 points by mpweiher 5y ago

pgt 5y ago

Curious that there is no mention of Datalog [^1] for graph traversal in the paper. To support multi-locale names in Datomic or Datascript-flavoured Datalog attractions_v1.pq would be written as (where :entity/locale is of type :db.type/ref): (d/q [:find ?id ?name ?lang :in $ ?type :where [?e :entity/type ?type] [?e :entity/locale ?loc] [?loc :locale/name ?name] [?loc :locale/lang ?lang] db #{"museum" "theme_park"}) => (["/z/38dwfnb8" "Museum of Modern Art" "en"] ["/z/38dwfnb8" "Museo de Arte Moderno" "es"] ...) You could store the locale inside the name string, but then you can't efficiently filter on it. If you want the whole shebang, can do `(pull ?id [*])`. It's not obvious in their example if the locale filtering is post-query or part of the unification. With only 4-tuple EAVT-style indices, you need an intermediate join to support compound values like ["Hello" "en"] if you want to query against the components, so I have been toying with making my own graph DB with 5-tuple (or more) extensible indices, e.g. EAXVT, where X would be the locale, but then index order matters. [^1]: http://www.learndatalogtoday.org/ http://www.learndatalogtoday.org/

simongray 5y ago
Clojure's Datalog ("Clojurelog") basically looks a whole lot like SPARQL written using Clojure data structure literals and they do reference SPARQL in the paper.

jerven 5y ago

Interesting read. I think there are some ideas in there that can be used for sparql 1.2. especially regarding external function definitions. On the other hand the sparql in the paper is decent but not excellent. The result is subtly different from the path query one, but I think fine for example use case.

MikeTaylor 5y ago

Strange that this paper doesn't even _mention_ GraphQL.

simongray 5y ago
I don't think GraphQL is used to query graph databases directly, is it? I've always understood it to be an API protocol that was built to serve some specific needs Facebook had (e.g. bundling multiple HTTP requests), not a full-on graph query language. I should probably mention that I don't really have extensive experience using it, though.
- oliyoung 5y ago
  you're right, on every point
- topicseed 5y ago
  I think it is used as foundation for DQL[0], the query language of Dgraph. But in and of itself, GraphQL isn't really built to query graph databases as you said. [0] https://dgraph.io/docs/query-language/graphql-fundamentals/ https://dgraph.io/docs/query-language/graphql-fundamentals/
- AtNightWeCode 5y ago
  GraphQL is basically used as SQL queries over stupid API:s. 99% of the graph DB advocates does not even understand what problem the graph DB solves. Soooo funny to argue with people when you can say that, oh, yes, we did this 20 years ago with recursive CTE:s.
contravariant 5y ago
Probably because GraphQL (despite it's name) isn't made for querying graphs.
- slver 5y ago
  Technically it is. But in a very restricted way. Any graph, when you traverse it from a specific node, with fixed depth, and you don't explicitly work with node references, but rather node "values", looks like a tree that sprawls from that node. Anyway, PathQuery is a completely different beast regardless.

mark_l_watson 5y ago

I was invited to work at Google in 2013 on an internal project using their Knowledge Graph. I had just written two books on RDF/SPARQL/linked-data and at first I was taken aback by the query language used at the time. However, when I realized how well the KG scaled and how fast the queries were, I became a fan. BTW, I think this paper is very well written. Graph queries is not an easy topic and their examples and text make the data types, syntax, and how to perform matches and aggregations easy to follow.

ampdepolymerase 5y ago
What are your thoughts on just using plain datalog/prolog?
- mark_l_watson 5y ago
  I have only used datalog in the form of Clojure and Datomic on a consulting job about ten years ago. I used to be a huge Prolog fan, but I don't think that anyone has paid me to do Prolog develop in over 20 years. My largest Prolog project was porting a prototype AI planning system that I wrote in Common Lisp to ExperProlog. It took about 6 weeks to prototype the system in Common Lisp, and re-writing it in Prolog only took about two weeks. I noticed last month that someone was offering an online Prolog course using Swi-Prolog. That might be a good place to start.
- lmeyerov 5y ago
  Having written a chunk of my phd in prolog and even a simplified implementation of one, I'm definitely a fan. At the same time, our startup (graphistry) works w/ teams needing to look at all sorts of graph data, including knowledge graphs like the topic here, and I'd be nervous about meeting the performance & scale needs with out-of-the-box prolog systems. Likewise, a lot of prolog's power comes from ideas like automatically backtracking search, and I can't imagine using that in most team environments. Datalog solves most of that :) My read of the paper is their semantics largely reduces to datalog. The most interesting semantic exception is their bounded recursion, which suggests they're doing optimizations normal datalog wouldn't. Likewise, graph workloads often have weird phenomena to optimize for in terms of expected queries & data, where I'm guessing datalog might fit semantically but not how people would normally implement an engine. The PathQuery paper carefully side-stepped all such discussion, so I've been curious. At Graphistry, we do end-to-end GPU stuff, so I've been thinking about this particular problem, and came to a similar conclusion of a datalog-ish subset being the most straightforward way to get more performance/$ for this kind of task.

atombender 5y ago

PathQuery looks a lot like GROQ [1], which is the query language used by the Sanity data store [2]. For example, one of the queries in the paper: @entities .[/type == (Id(/ museum ) , Id(/ theme_park ))] .{ id: ?cur require name: /name.[TextLang() == en ] @merge : events::GetInfo() } can be written something like: *[type == "museum" || type == "theme_park"] { id, name: select(name[lang == "en"] => name), ...{ // GROQ doesn't have functions, so GetInfo() // would need to be inlined here } } PathQuery is of course a lot more complex, but the basic structure seems very similar. One thing GROQ does not have yet is recursive querying of the type needed to traverse graphs, but this is on our roadmap to implement. We've published a public draft specification for GROQ, and hoping it will be adopted by more tools. For example, we already have an open-source JavaScript implementation of it. (Disclosure: I work on GROQ at Sanity.) [1] https://github.com/sanity-io/GROQ https://github.com/sanity-io/GROQ [2] https://www.sanity.io/ https://www.sanity.io/

sanxiyn 5y ago
It seems PathQuery's entire novelty is better handling of recursive querying for query optimization, but "details are admittedly not discussed herein". So the paper has a sort of weird feel. It goes like this: PathQuery is a good language, because it has good semantics and it is optimizable. Some words on its good semantics. We don't discuss how it is optimizable, but trust us, it is.
- atombender 5y ago
  From what I can tell, PathQuery is also clever in how queries express the shape of the returned data, which we in GROQ call projection. For example, in GROQ you can do: *[type == "user"] { id, name, "slug": id + "-" + lower(name), "photos": photos[] { url, width, height } | order(position), "newestComment": *[_type == "comment" && author == ^.id] | order(createdAt desc)[0] { id, body } } PathQuery seems to give you similar tools in transforming data as part of your pipeline, which I think is how query languages should be like.

jalk 5y ago

Anybody know why a paper like this doesn’t include a date?

chodeboy 5y ago
I was asking myself the very same thing.
CharlesW 5y ago
In case you're just wondering how recent it is (vs. "Why is the date not in the PDF?"), the page says the submission date was 17 Jun 2021.

kayza 5y ago

Reminds me of GQL [2]. Anybody know the differences and or similarities? [2] https://www.gqlstandards.org/ https://www.gqlstandards.org/

bionhoward 5y ago
GQL is much more clear and readable while PathQuery is confusing and non semantic

netfl0 5y ago

Can someone explain why they did not mention SPARQL CONSTRUCT statements? I struggle with the notion that SPARQL isn’t “graphy” per their assertion. I may be missing something though. https://www.w3.org/TR/sparql11-query/#construct https://www.w3.org/TR/sparql11-query/#construct

staticassertion 5y ago

I feel like graph languages can be so esoteric. It would be nice to have something closer to RDF, but with filter syntax, and the ability to group filters. I've never built a language, so maybe I'm just crazy, but what's wrong with, say, https://gist.github.com/insanitybit/cd997e8d367889708edc3ec221b89430 https://gist.github.com/insanitybit/cd997e8d367889708edc3ec2... Basically I defined the subject in a sort of 'namespace' of constraints ("parent", "children", etc), and then the edge or predicate constraint on it. I guess it's easy to just "make up" a language, and implementing is the difficult part, and then it's like "ok well then how do you solve <some unanticipated problem because idk what I'm even talking about>" but also, graphql, as much as it isn't good for a database API, is also quite straightforward and familiar looking and I feel like taking something like rdf as a basis would be reasonable.

Jeff_Brown 5y ago
I wrote a language that's very close to natural language for writing to and querying a RSLT, a kind of higher order graph. https://github.com/JeffreyBenjaminBrown/hode/blob/master/docs/hash/the-hash-language.md https://github.com/JeffreyBenjaminBrown/hode/blob/master/doc...

Jeff_Brown 5y ago

Syntactically how does PathQuery compare to Gremlin?

adsharma 5y ago

I think people focus much on syntax and not enough on semantics. After working on 2-3 iterations of similar languages (sexpressions, clojure enhanced with pipe operator), my take away is to define an API (not a new language) and support multiple languages on top of it. I picked python and the API is here: https://github.com/adsharma/fquery/ https://github.com/adsharma/fquery/ https://adsharma.github.io/fquery/ https://adsharma.github.io/fquery/ Like SQL, DDL and DML should be separated too. https://adsharma.github.io/flattools-programs/ https://adsharma.github.io/flattools-programs/

snicker7 5y ago

One issue I have with query languages is how poorly they interact with the "host language" . SQL requires non-composable string templating or complex, low-performance ORM's. The only query languages that do this "right" are datalog (Datomic) and Q/K (KDB+, Shakti).

fragile_frogs 5y ago
I think RethinkDB also did a great job with ReQL: https://rethinkdb.com/docs/sql-to-reql/javascript/ https://rethinkdb.com/docs/sql-to-reql/javascript/

liminal 5y ago

I've tried using SPARQL in the past and found it to be very difficult. There are some aspects here that seem like improvements: - I really like that a query only operates on a single graph. Quads make what should be simple triple queries on a graph much harder than necessary in RDF/SPARQL. - I like the path-oriented declarative design. It seems like a declarative version of the imperative graph traversal libraries. - The inline creation of records based on state in a traversal is also intuitive. - The simple type system is a welcome change from RDF's xsd monstrosity It still seems to be missing some things. For example, they show a recursive query, but no way to return the actual path taken, only the start and end points (I also can't figure out how to do in SPARQL); I don't see a way to explore predicate relationships; is there a method for reification?