More Like this

1. Relational Diagrams and the Pattern Expressiveness of Relational Languages

   https://doi.org/10.1145/3733620.3733637  

   Gatterbauer, Wolfgang; Dunne, Cody (April 2025, ACM SIGMOD Record)

   Comparing relational languages by their logical expressiveness is well understood. Less 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? Our SIGMOD 2024 paper proposes a semantic definition of relational query patterns that uses a variant of structure-preserving mappings between the relational tables of queries. This formalism allows us to analyze the relative pattern expressiveness of relational languages. Notably, for the nondisjunctive language fragment, we show that relational calculus (RC) can express a larger class of patterns than the basic operators of relational algebra (RA). We also propose Relational Diagrams, a complete and sound diagrammatic representation of safe relational calculus. These diagrams can represent all query patterns for unions of non-disjunctive queries, in contrast to visual query representations that derive visual marks from the basic operators of algebra. Our anonymously preregistered user study shows that Relational Diagrams allow users to recognize relational patterns meaningfully faster and more accurately than they can with SQL. 

   more » « less
2. A Tutorial on Visual Representations of Relational Queries

   https://doi.org/10.14778/3611540.3611578  

   Gatterbauer, Wolfgang (August 2023, Proceedings of the VLDB Endowment)

   Query formulation is increasingly performed by systems that need to guess a user's intent (e.g. via spoken word interfaces). But how can a user know that the computational agent is returning answers to the right query? More generally, given that relational queries can become pretty complicated,how can we help users understand existing relational queries, whether human-generated or automatically generated? Now seems the right moment to revisit a topic that predates the birth of the relational model: developing visual metaphors that help users understand relational queries. This lecture-style tutorial surveys the keyvisual metaphors developed for visual representations of relational expressions.We will survey the history and state-of-the art of relationally-complete diagrammatic representations of relational queries, discuss the key visual metaphors developed in over a century of investigating diagrammatic languages, and organize the landscape by mapping their used visual alphabets to the syntax and semantics of Relational Algebra (RA) and Relational Calculus (RC). 

   more » « less
3. Bridge trisections of knotted surfaces in 4-manifolds

   https://doi.org/10.1073/pnas.1717171115  

   Meier, Jeffrey; Zupan, Alexander (October 2018, Proceedings of the National Academy of Sciences)

   We prove that every smoothly embedded surface in a 4-manifold can be isotoped to be in bridge position with respect to a given trisection of the ambient 4-manifold; that is, after isotopy, the surface meets components of the trisection in trivial disks or arcs. Such a decomposition, which we call a generalized bridge trisection, extends the authors’ definition of bridge trisections for surfaces in S 4 . Using this construction, we give diagrammatic representations called shadow diagrams for knotted surfaces in 4-manifolds. We also provide a low-complexity classification for these structures and describe several examples, including the important case of complex curves inside ℂ ℙ 2 . Using these examples, we prove that there exist exotic 4-manifolds with ( g , 0 ) —trisections for certain values of g. We conclude by sketching a conjectural uniqueness result that would provide a complete diagrammatic calculus for studying knotted surfaces through their shadow diagrams. 

   more » « less
4. Interactive Text-to-SQL Generation via Editable Step-by-Step Explanations

   https://doi.org/10.18653/v1/2023.emnlp-main.1004  

   Tian, Yuan; Zhang, Zheng; Ning, Zheng; Li, Toby; Kummerfeld, Jonathan; Zhang, Tianyi (December 2023, Association for Computational Linguistics)

   Relational databases play an important role in business, science, and more. However, many users cannot fully unleash the analytical power of relational databases, because they are not familiar with database languages such as SQL. Many techniques have been proposed to automatically generate SQL from natural language, but they suffer from two issues: (1) they still make many mistakes, particularly for complex queries, and (2) they do not provide a flexible way for non-expert users to validate and refine incorrect queries. To address these issues, we introduce a new interaction mechanism that allows users to directly edit a step-by-step explanation of a query to fix errors. Our experiments on multiple datasets, as well as a user study with 24 participants, demonstrate that our approach can achieve better performance than multiple SOTA approaches. 

   more » « less
5. StreamQRE: modular specification and efficient evaluation of quantitative queries over streaming data

   https://doi.org/10.1145/3062341.3062369  

   Mamouras, Konstantinos; Raghothaman, Mukund; Alur, Rajeev; Ives, Zachary G.; Khanna, Sanjeev (January 2017, Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation)

   Real-time decision making in emerging IoT applications typically relies on computing quantitative summaries of large data streams in an efficient and incremental manner. To simplify the task of programming the desired logic, we propose StreamQRE, which provides natural and high-level constructs for processing streaming data. Our language has a novel integration of linguistic constructs from two distinct programming paradigms: streaming extensions of relational query languages and quantitative extensions of regular expressions. The former allows the programmer to employ relational constructs to partition the input data by keys and to integrate data streams from different sources, while the latter can be used to exploit the logical hierarchy in the input stream for modular specifications. We first present the core language with a small set of combinators, formal semantics, and a decidable type system. We then show how to express a number of common patterns with illustrative examples. Our compilation algorithm translates the high-level query into a streaming algorithm with precise complexity bounds on per-item processing time and total memory footprint. We also show how to integrate approximation algorithms into our framework. We report on an implementation in Java, and evaluate it with respect to existing high-performance engines for processing streaming data. Our experimental evaluation shows that (1) StreamQRE allows more natural and succinct specification of queries compared to existing frameworks, (2) the throughput of our implementation is higher than comparable systems (for example, two-to-four times greater than RxJava), and (3) the approximation algorithms supported by our implementation can lead to substantial memory savings. 

   more » « less