On the reasonable effectiveness of Relational Diagrams: explaining relational query patterns and the pattern expressiveness of relational languages

Two Relational Diagrams consisting of nested boxes connected by lines, similar to entity relationship diagrams.
We propose "relational diagrams", a natural diagrammatic representation of tuple relational calculus. We also propose a semantic definition of relational query patterns, which allows us to analyze the relative pattern expressiveness of relational query languages. Here we see Relational Diagrams of two queries with similar patterns: "find names of sailors who reserved all boats" and "find names of suppliers who supply all parts".
Abstract
Comparing relational languages by their logical expressiveness is well understood. Less well understood is how to compare relational languages by their ability to represent relational query patterns. Indeed, what are query patterns other than "a certain way of writing a query"? And how can query patterns be defined across procedural and declarative languages, irrespective of their syntax? To the best of our knowledge, we provide the first semantic definition of relational query patterns by using a variant of structure-preserving mappings between the relational tables of queries. This formalism allows us to analyze the relative pattern expressiveness of relational language fragments and create a hierarchy of languages with equal logical expressiveness yet different pattern expressiveness. Notably, for the non-disjunctive language fragment, we show that relational calculus can express a larger class of patterns than the basic operators of relational algebra. Our language-independent definition of query patterns opens novel paths for assisting database users. For example, these patterns could be leveraged to create visual query representations that faithfully represent query patterns, speed up interpretation, and provide visual feedback during query editing. As a concrete example, we propose Relational Diagrams, a complete and sound diagrammatic representation of safe relational calculus that is provably (i) unambiguous, (ii) relationally complete, and (iii) able to represent all query patterns for unions of non-disjunctive queries. Among all diagrammatic representations for relational queries that we are aware of, ours is the only one with these three properties. Furthermore, our anonymously preregistered user study shows that Relational Diagrams allow users to recognize patterns meaningfully faster and more accurately than SQL.
Materials
PDF | Preprint | DOI | Supplement | Preregistration | Homepage | BibTeX | SIGMOD 2024 Best Paper Honorable Mention (1/3)!
Authors
Citation

Khoury Vis Lab — Northeastern University
* West Village H, Room 302, 440 Huntington Ave, Boston, MA 02115, USA
* 100 Fore Street, Portland, ME 04101, USA
* Carnegie Hall, 201, 5000 MacArthur Blvd, Oakland, CA 94613, USA