6 ms·

SQL generally doesn't have primitives that let you traverse arbitrary relationships. You can join multiple tables together, but the nature of those relationship

by pcl 7y ago

SQL generally doesn't have primitives that let you traverse arbitrary relationships. You can join multiple tables together, but the nature of those relationships is expressed directly in the SQL statement you're writing. Some RDBs provide extensions to the SQL standard to do some basic graph traversals (Oracle's CONNECT BY, for example), but these are just the most-basic sorts of graph traversals. In a graph database, the primary notions are nodes and edges and properties associated with them, whereas in a relational database, the primary notions are tables (aka "relations"), foreign keys that allow you to connect together multiple tables, and rows in those tables. Those differences in primary notions surface in the query languages as well.

mehrdadn 7y ago
Thanks for the response. I'm having trouble seeing what kinds of queries come up of this nature that SQL wouldn't be fit for, though. What would be an example of a realistic graph query one would want to do that would be too difficult to do in SQL?
- zaphar 7y ago
  Graphs have arbitrary depth. As a result some queries need an unknown number of joins on an unknown number of keys. Representing this in just SQL would be impossible. You could do it in a stored procedure but that is a superset of SQL not vanilla SQL. You can also do it by just making the SQL calls over and over in your code as you get each row but that's not going to be very optimized.
  - deleted 7y ago
    [deleted]
- pcl 7y ago
  Let's assume we're playing the Kevin Bacon game. We've got actors, movies, and roles. Here's some sample data: INSERT INTO actors (id, name) VALUES (1, 'Kevin Bacon') INSERT INTO actors (id, name) VALUES (2, 'Frank Langella') INSERT INTO actors (id, name) VALUES (3, 'Cameron Diaz') INSERT INTO movies (id, name) VALUES (1, 'The Box') INSERT INTO movies (id, name) VALUES (2, 'Frost/Nixon') INSERT INTO roles (movie_id, actor_id) VALUES (1, 2) INSERT INTO roles (movie_id, actor_id) VALUES (1, 3) INSERT INTO roles (movie_id, actor_id) VALUES (2, 1) INSERT INTO roles (movie_id, actor_id) VALUES (2, 2) Given the above data model, it's not possible to select all the actors that are within 6 degrees of Kevin Bacon with a SQL statement. (Data from the incredible Oracle of Bacon, which uses custom graph traversal to serve up results: https://oracleofbacon.org/how.php https://oracleofbacon.org/how.php)
  - irishsultan 7y ago
    It may not be obvious, but it should be possible. It's relatively easy to get those within 1 degree of separation, put that in a view, then repeat that, but instead of hardcoding Kevin Bacon do "within 1 degree of those within 1 degree of Kevin bacon". Repeat a few more times and you have your query. Of course if you want to know the degree between two random actors, or all actors within n degrees of Kevin Bacon (where n is unknown ahead of time) then it becomes really difficult (potentially still possible using common table expressions though).
    - pcl 7y ago
      Yes -- put more clearly, it's not possible in the relational calculus to fetch the number of degrees of separation between two actors.
    - waffle_ss 7y ago
      It’s possible with recursive CTEs, but very slow. https://stackoverflow.com/questions/52674380/improving-postgres-performance-on-graph-like-queries-of-multi-level-self-joins https://stackoverflow.com/questions/52674380/improving-postg...
      - kyllo 7y ago
        There's nothing essentially, inherently slower about recursive CTEs in SQL databases compared to graph database queries, it depends how they're implemented, particularly whether they take advantage of indexing and caching. They're both going to be doing fundamentally the same type of algorithm under the hood. I've gotten recursive CTEs in SQL Server to perform quite well just by indexing the join key columns.
        johnymontana 7y ago
        Graph databases like Neo4j have a very important performance characteristic called "index-free adjacency". This means that a traversal from node to node (similar to a JOIN in a relational database) does NOT use an index. Instead, it's more like chasing pointers, jumping directly to an offset. Whereas relational databases do use an index to perform JOINS - it's essentially a set comparison, using an index to see where two sets overlap. What this means is that the performance of joins in relational databases is dependent on the overall size of the tables, while the performance of traversals in a graph database that implements index-free adjacency is not dependent on the overall size of the data (rather just the connectedness of the nodes being traversed), because an index is not used for traversals.
- kyllo 7y ago
  Anything where you need transitive closure, that is, you need all the nodes that are reachable from a given starting node. You can do it in SQL dialects that support recursive common table expressions. In a previous job, I dealt with Bill of Materials data, which basically a parts list for a hardware product. Parts contain other parts, which contain other parts, and so on, recursively. The data was in SQL Server. I could have moved the data to Neo4j and gotten a much more concise and convenient syntax for traversing the parent-child relationships. But I decided it wasn't worth the trouble of moving data, so I bit the bullet and just wrote the recursive CTE in SQL. That's the biggest problem with graph databases. If your data's already in a SQL database, it often isn't worth it to _move all your data_ just to get a better query syntax.
  - mehrdadn 7y ago
    Huh, interesting, thanks!
- giardini 7y ago
  Here's the classic and humorous letter critical of relational databases (RDBMS) penned in 1991 by Henry Baker and published in the Communications of the ACM: http://home.pipeline.com/~hbaker1/letters/CACM-RelationalDatabases.html http://home.pipeline.com/~hbaker1/letters/CACM-RelationalDat... Almost an "RDBMS Considered Harmful" screed, Baker's letter may seem humorous in today's environment and even ludicrous to those who did not live through the transition from older file-systems/DBMS to RDBMS. To those of us who did experience that transition, Baker was painfully on-point and his letter served as a scourge to improve systems performance for more than a decade beyond that period. More recently the major RDBMS vendors have complemented SQL with directives that address the storage and handling of hierarchical data, e.g., in POSTGRESQL: https://www.technobytz.com/closure_table_store_hierarchical_data.html https://www.technobytz.com/closure_table_store_hierarchical_... Baker was no prophet: his letter showed high hopes for object-oriented databases, another technology that noisily rose and quietly fell in popularity.
  - taffer 7y ago
    > More recently the major RDBMS vendors have complemented SQL with directives that address the storage and handling of hierarchical data Oracle could do that 30 years ago, and recursive CTEs are part of SQL:1999.
ulrikrasmussen 7y ago
The theoretical basis for SQL is relational algebra. I wonder if there is a similar calculus underlying graph query languages?
- chongli 7y ago
  I don't know much about graph databases but there is a whole branch of mathematics called algebraic graph theory [1] which allows for the treatment of graphs algebraically. I took intro graph theory in second year so I have only seen combinatorial approaches but from what I gather it's a pretty powerful field. [1] https://en.wikipedia.org/wiki/Algebraic_graph_theory https://en.wikipedia.org/wiki/Algebraic_graph_theory
- Jeff_Brown 7y ago
  There's a recent category-theoretic framework for them: https://arxiv.org/abs/1909.04881 https://arxiv.org/abs/1909.04881
u320 7y ago
> Some RDBs provide extensions to the SQL standard to do some basic graph traversals This has been standardized since the SQL-1999 standard.
- twic 7y ago
  Are you referring to recursive common table expressions? These do allow graph queries. They are quite different to the proprietary extensions, though, and much more awkward. I would love to see SQL grow a concise navigation/join syntax like JPQL's [1]; imagine writing: select e.name, e.department.head.assistant.name from employees Instead of: select e.name, a.name from employees e, join departments d using (department_id) join employees h on d.head_id = h.employee_id join employees a on h.assistant_id = a.employee_id Given that dots already mean something in SQL, maybe it would have to be: select e.name, e->department->head->assistant.name from employees Once you've got that, it would not be a huge leap to add a recursive version of this operator. [1] https://www.objectdb.com/java/jpa/query/jpql/path#Navigation_through_Path_Expressions https://www.objectdb.com/java/jpa/query/jpql/path#Navigation...
  - deleted 7y ago
    [deleted]
  - dragonwriter 7y ago
    > I would love to see SQL grow a concise navigation/join syntax Yeah, what you need is a specification of a name to use for the referenced table in implicit joins when you sepcify an FK, then if you reference the linked table, it performs the join (to bring in a different subthread, such an implicit join specification could be the mechanism of opting-in for index-free adjacency on that FK, too, so you'd combine syntactic support with the supporting query optimization.) Maybe something like: REFERENCES <table> [(<key columns>)] AS <link-name> So, your example would be be supported by (assuming all the FKs are to PKs so you don't need columns specified on the FKs): FOREIGN KEY department_id REFERENCES departments AS department FOREIGN KEY head_id REFERENCES employees AS head FOREIGN KEY assistant_id REFERENCES employees AS assistant ...on the relevant tables.
- 7y ago

by pcl 7y ago

mehrdadn 7y ago

Thanks for the response. I'm having trouble seeing what kinds of queries come up of this nature that SQL wouldn't be fit for, though. What would be an example of a realistic graph query one would want to do that would be too difficult to do in SQL?

zaphar 7y ago
Graphs have arbitrary depth. As a result some queries need an unknown number of joins on an unknown number of keys. Representing this in just SQL would be impossible. You could do it in a stored procedure but that is a superset of SQL not vanilla SQL. You can also do it by just making the SQL calls over and over in your code as you get each row but that's not going to be very optimized.
- deleted 7y ago
  [deleted]
pcl 7y ago
Let's assume we're playing the Kevin Bacon game. We've got actors, movies, and roles. Here's some sample data: INSERT INTO actors (id, name) VALUES (1, 'Kevin Bacon') INSERT INTO actors (id, name) VALUES (2, 'Frank Langella') INSERT INTO actors (id, name) VALUES (3, 'Cameron Diaz') INSERT INTO movies (id, name) VALUES (1, 'The Box') INSERT INTO movies (id, name) VALUES (2, 'Frost/Nixon') INSERT INTO roles (movie_id, actor_id) VALUES (1, 2) INSERT INTO roles (movie_id, actor_id) VALUES (1, 3) INSERT INTO roles (movie_id, actor_id) VALUES (2, 1) INSERT INTO roles (movie_id, actor_id) VALUES (2, 2) Given the above data model, it's not possible to select all the actors that are within 6 degrees of Kevin Bacon with a SQL statement. (Data from the incredible Oracle of Bacon, which uses custom graph traversal to serve up results: https://oracleofbacon.org/how.php https://oracleofbacon.org/how.php)
- irishsultan 7y ago
  It may not be obvious, but it should be possible. It's relatively easy to get those within 1 degree of separation, put that in a view, then repeat that, but instead of hardcoding Kevin Bacon do "within 1 degree of those within 1 degree of Kevin bacon". Repeat a few more times and you have your query. Of course if you want to know the degree between two random actors, or all actors within n degrees of Kevin Bacon (where n is unknown ahead of time) then it becomes really difficult (potentially still possible using common table expressions though).
  - pcl 7y ago
    Yes -- put more clearly, it's not possible in the relational calculus to fetch the number of degrees of separation between two actors.
  - waffle_ss 7y ago
    It’s possible with recursive CTEs, but very slow. https://stackoverflow.com/questions/52674380/improving-postgres-performance-on-graph-like-queries-of-multi-level-self-joins https://stackoverflow.com/questions/52674380/improving-postg...
    - kyllo 7y ago
      There's nothing essentially, inherently slower about recursive CTEs in SQL databases compared to graph database queries, it depends how they're implemented, particularly whether they take advantage of indexing and caching. They're both going to be doing fundamentally the same type of algorithm under the hood. I've gotten recursive CTEs in SQL Server to perform quite well just by indexing the join key columns.
      - johnymontana 7y ago
        Graph databases like Neo4j have a very important performance characteristic called "index-free adjacency". This means that a traversal from node to node (similar to a JOIN in a relational database) does NOT use an index. Instead, it's more like chasing pointers, jumping directly to an offset. Whereas relational databases do use an index to perform JOINS - it's essentially a set comparison, using an index to see where two sets overlap. What this means is that the performance of joins in relational databases is dependent on the overall size of the tables, while the performance of traversals in a graph database that implements index-free adjacency is not dependent on the overall size of the data (rather just the connectedness of the nodes being traversed), because an index is not used for traversals.
kyllo 7y ago
Anything where you need transitive closure, that is, you need all the nodes that are reachable from a given starting node. You can do it in SQL dialects that support recursive common table expressions. In a previous job, I dealt with Bill of Materials data, which basically a parts list for a hardware product. Parts contain other parts, which contain other parts, and so on, recursively. The data was in SQL Server. I could have moved the data to Neo4j and gotten a much more concise and convenient syntax for traversing the parent-child relationships. But I decided it wasn't worth the trouble of moving data, so I bit the bullet and just wrote the recursive CTE in SQL. That's the biggest problem with graph databases. If your data's already in a SQL database, it often isn't worth it to _move all your data_ just to get a better query syntax.
- mehrdadn 7y ago
  Huh, interesting, thanks!
giardini 7y ago
Here's the classic and humorous letter critical of relational databases (RDBMS) penned in 1991 by Henry Baker and published in the Communications of the ACM: http://home.pipeline.com/~hbaker1/letters/CACM-RelationalDatabases.html http://home.pipeline.com/~hbaker1/letters/CACM-RelationalDat... Almost an "RDBMS Considered Harmful" screed, Baker's letter may seem humorous in today's environment and even ludicrous to those who did not live through the transition from older file-systems/DBMS to RDBMS. To those of us who did experience that transition, Baker was painfully on-point and his letter served as a scourge to improve systems performance for more than a decade beyond that period. More recently the major RDBMS vendors have complemented SQL with directives that address the storage and handling of hierarchical data, e.g., in POSTGRESQL: https://www.technobytz.com/closure_table_store_hierarchical_data.html https://www.technobytz.com/closure_table_store_hierarchical_... Baker was no prophet: his letter showed high hopes for object-oriented databases, another technology that noisily rose and quietly fell in popularity.
- taffer 7y ago
  > More recently the major RDBMS vendors have complemented SQL with directives that address the storage and handling of hierarchical data Oracle could do that 30 years ago, and recursive CTEs are part of SQL:1999.

ulrikrasmussen 7y ago

The theoretical basis for SQL is relational algebra. I wonder if there is a similar calculus underlying graph query languages?

chongli 7y ago
I don't know much about graph databases but there is a whole branch of mathematics called algebraic graph theory [1] which allows for the treatment of graphs algebraically. I took intro graph theory in second year so I have only seen combinatorial approaches but from what I gather it's a pretty powerful field. [1] https://en.wikipedia.org/wiki/Algebraic_graph_theory https://en.wikipedia.org/wiki/Algebraic_graph_theory
Jeff_Brown 7y ago
There's a recent category-theoretic framework for them: https://arxiv.org/abs/1909.04881 https://arxiv.org/abs/1909.04881

u320 7y ago

> Some RDBs provide extensions to the SQL standard to do some basic graph traversals This has been standardized since the SQL-1999 standard.

twic 7y ago
Are you referring to recursive common table expressions? These do allow graph queries. They are quite different to the proprietary extensions, though, and much more awkward. I would love to see SQL grow a concise navigation/join syntax like JPQL's [1]; imagine writing: select e.name, e.department.head.assistant.name from employees Instead of: select e.name, a.name from employees e, join departments d using (department_id) join employees h on d.head_id = h.employee_id join employees a on h.assistant_id = a.employee_id Given that dots already mean something in SQL, maybe it would have to be: select e.name, e->department->head->assistant.name from employees Once you've got that, it would not be a huge leap to add a recursive version of this operator. [1] https://www.objectdb.com/java/jpa/query/jpql/path#Navigation_through_Path_Expressions https://www.objectdb.com/java/jpa/query/jpql/path#Navigation...
- deleted 7y ago
  [deleted]
- dragonwriter 7y ago
  > I would love to see SQL grow a concise navigation/join syntax Yeah, what you need is a specification of a name to use for the referenced table in implicit joins when you sepcify an FK, then if you reference the linked table, it performs the join (to bring in a different subthread, such an implicit join specification could be the mechanism of opting-in for index-free adjacency on that FK, too, so you'd combine syntactic support with the supporting query optimization.) Maybe something like: REFERENCES <table> [(<key columns>)] AS <link-name> So, your example would be be supported by (assuming all the FKs are to PKs so you don't need columns specified on the FKs): FOREIGN KEY department_id REFERENCES departments AS department FOREIGN KEY head_id REFERENCES employees AS head FOREIGN KEY assistant_id REFERENCES employees AS assistant ...on the relevant tables.
7y ago