A Principled Solution to the Disjunction Problem of Diagrammatic Query Representations

Finding unambiguous diagrammatic representations for first-order logical formulas and relational queries with arbitrarily nested disjunctions has been a surprisingly long-standing unsolved problem. We refer to this problem as the disjunction problem (of diagrammatic query representations).

This work solves the disjunction problem. Our solution unifies, generalizes, and overcomes the shortcomings of prior approaches for disjunctions. It extends the recently proposed Relational Diagrams and is identical for disjunction-free queries. However, it can preserve the relational patterns and the safety for all well-formed Tuple Relational Calculus (TRC) queries, even with arbitrary disjunctions. Additionally, its size is proportional to the original TRC query and can thus be exponentially more succinct than Relational Diagrams.

1 FOL is basically the same as Relational Calculus and thus equivalent in expressiveness to relationally complete languages. 2 Safety is a syntactic criterion that guarantees that the query is domain-independent and thus always returns finitely many answers [71]. See Section 3.2 for details. "Same pattern" is a semantic notion and means (slightly simplified) that the representation uses the set of relation variables. See Section 2.2 for details.