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.

As example, consider the following three queries: “Find sailors who reserved all red boats”, “Find students who took all classes from the art department”, and “Find actors who played in all movies by Hitchcock”. These three queries use a similar relational patterns (shown in the “all” column) across three different schemas:

Relational Diagrams are a complete and sound diagrammatic representation of safe relational calculus. They are (𝑖) proven unambiguous, (𝑖𝑖) proven relationally complete, and (𝑖𝑖𝑖) are able to represent all relational query patterns for unions of non-disjunctive queries. Our anonymously preregistered user study shows that Relational Diagrams allows users to recognize patterns meaningfully faster and with higher accuracy across different schemas than SQL. We envision a future in which a user dictates queries while interacting with a relational database, and the system visualizes the queries back, enabling the user to verify their correct interpretation.

Reference

@article{SIGMOD2024:GD,
  author = {Wolfgang Gatterbauer and Cody Dunne},
  title = {On the Reasonable Effectiveness of Relational Diagrams:
          Explaining Relational Query Patterns and the Pattern Expressiveness of Relational Languages},
  journal = {Proc. {ACM} Manag. Data},
  volume = {2},
  number = {1},
  pages = {61:1--61:27},
  year = {2024},
  url = {https://doi.org/10.1145/3639316},
  doi = {10.1145/3639316}
}

Funding

This work has been supported in part by the National Science Foundation (NSF) under award numbers IIS-1762268, IIS-1956096, and IIS-2145382, and was conducted in part while Wolfgang Gatterbauer was on sabbatical and attending the semester-long program on Logic and Algorithms in Database Theory and AI at Berkeley's Simons Institute for the Theory of Computing. Any opinions, findings, and conclusions or recommendations expressed in this project are those of the author(s) and do not necessarily reflect the views of the Funding Agencies.

Related papers

Related web pages