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

On the Reasonable Effectiveness of Relational Diagrams: Explaining Relational Query Patterns and the Pattern Expressiveness of Relational Languages
SIGMOD 2024 best paper honorable mention (1/3) (announcement)
Proposes a semantic definition of relational query patterns, which allows us to analyze the relative pattern expressiveness of relational query languages. Also proposes "relational diagrams", a natural diagrammatic representation of tuple relational calculus.
@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.

National Science Foundation Simons Institute for the Theory of Computing

Related papers

A Comprehensive Tutorial on over 100 years of Diagrammatic Representations of Logical Statements and Relational Queries
Wolfgang Gatterbauer
ICDE 2024
Surveys the key visual metaphors developed for visual representations of relational expressions, including the early history predating the relational model. Also includes a detailed comparison of Relational Diagrams against formalisms such as Venn-Peirce diagrams, beta existential graphs and conceptual graphs.
A Tutorial on Visual Representations of Relational Queries
Wolfgang Gatterbauer
An earlier tutorial that surveys the key visual metaphors developed for visual representations of relational expressions inside the database community, leaving out the early history and connections to diagrammatic reasoning.
Principles of Query Visualization
Wolfgang Gatterbauer, Cody Dunne, H.V. Jagadish, Mirek Riedewald
Discusses the principles of relational query visualization and its potential for simplifying user interactions with relational data
Stratisfimal Layout: A modular optimization model for laying out layered node-link network visualizations
Sara Di Bartolomeo, Mirek Riedewald, Wolfgang Gatterbauer, and Cody Dunne
Proposes a comprehensive approach to make complicated networks (such as those with layers and grouped nodes) easier to read. The idea is to formulate various readability criteria (notably crossing minimization and bendiness reduction) as a modular and customizable constraint optimization problem.
QueryVis: Logic-based Diagrams help Users Understand Complicated SQL Queries Faster
Aristotelis Leventidis, Jiahui Zhang, Cody Dunne, Wolfgang Gatterbauer, HV Jagadish, Mirek Riedewald
SIGMOD, pp. 2303–2318, 2020 (SIGMOD reproducibility award, announcement)
Shows that logical diagrams automatically created from SQL queries help users understand the queries faster and with fewer errors than SQL itself. Our ultimate goal is to allow users of SQL to reason about queries in terms of "diagrammatic SQL patterns" based on first-order logic.
QueryViz: Helping users understand SQL queries and their patterns
Jonathan Danaparamita, Wolfgang Gatterbauer
Proposes QueryViz, a light-weight add-on to existing databases. Copy your SQL query into the interactive interface at http://queryviz.com and look at the visualization of the query's relational pattern.
Databases will visualize queries too
Wolfgang Gatterbauer
Describes a new human-query interaction in which users re-use existing queries as templates to compose their own queries. This interaction is made possible with new automatic query visualization tools (such as QueryViz, or now QueryVis) which help users understand SQL patterns quickly.

Related web pages

Surveys the key visual metaphors developed for visual representations of relational expressions, including the early history predating the relational model
Surveys the key visual metaphors developed for visual representations of relational expressions.
A modular optimization model for layered node-link network visualizations, as needed for query visualizations
Precursor to Relational Diagrams