Pith. sign in

REVIEW 4 major objections 4 minor 58 references

Relational Algebras for Subset Selection and Optimisation

T0 review · 4 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A single relational algebra now spans ordinary data queries, subset selection, and optimisation.

desk verdict A genuinely integrative algebraic framework for subset selection and optimization, but the central translation-to-RA claim is not yet proven — the symbolic apparatus in Appendix G.4 goes beyond standard RA. read the letter →

arxiv 2509.06439 v1 pith:QHOZFT5D submitted 2025-09-08 cs.DB cs.DMcs.MS

David Robert Pratten , Luke Mathieson , Fahimeh Ramezani This is my paper · ORCID
classification cs.DBcs.DMcs.MS MSC 68P15
keywords relationalalgebracompletedomainrelationssolutionsetsexponentiationsubsetselectionoptimisationqueriesquerysafetyprescriptiveanalytics
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Subset selection and optimisation queries—choosing a collection of tuples that satisfies global constraints or maximises an objective—are usually bolted onto SQL through ad-hoc extensions, each with its own way of inventing a search space. The paper's central proposal is that the missing foundational operation is relational exponentiation: raising a Decision relation to the power of a Base relation to form the set of all functions f: Base → Decision, with |Decision|^|Base| candidate relations. It organises those candidates as solution sets, a higher-order relational algebra filtered by Boolean aggregation over candidate relations, and gives a homomorphic translation Φ back to ordinary relational algebra. If that translation is sound, a single polymorphic SQL can express data management, NP-complete search, and optimisation problems without new keywords or special clauses.

What carries the argument

Relational exponentiation, realised as solution sets U=⟨Base_U,Decision_U,χ_U⟩, is the central operation: it forms all functions f:Base→Decision, i.e. |Decision|^|Base| candidate relations. The argument is carried by the four-step homomorphic translation Φ that maps a solution set back to standard RA—flattening Decision into a repeated cross product (flat_U), building a symbolic candidate relation (symI_U) whose decision attributes are references ⟨a_i⟩, handling joins on decision attributes via symbolic lookup relations, and translating Boolean aggregations into constraints over symbolic values. This makes ordinary relational algebra the evaluation target and gives the query optimiser a prin

What would settle it

Choose a small solution set (say |Base|=2, |Decision|=3) whose characteristic function joins the candidate on a decision attribute with a relation that maps decision values to dependent values. Translate it with Φ, solve the resulting flattened relation, and compare the satisfying assignments with the definitional semantics of the solution set; any mismatch settles the soundness question.

Watch

Extended reading notes

Core claim

The paper argues that characteristic functions should be first-class citizens of relational algebra. An active domain relation is one whose characteristic function is a finite DNF equality formula; a complete domain relation is a pair of attributes and an arbitrary characteristic function, starting full and excluding tuples by constraints. This captures constraint solving and NP-complete problems while keeping query safety, because the active-domain fragment is a domain-independent DNF region reachable in polynomial time. A solution set U = ⟨Base_U, Decision_U, χ_U⟩ is then the exponential collection of candidate relations I_U such that π[α_Base](I_U)=Base_U and the functional dependency Bas

Load-bearing premise

The load-bearing premise is that the translation Φ sends every expressible solution-set restriction to an ordinary relational algebra expression that keeps exactly the same set of candidate solutions; the paper defines the cases but gives no inductive proof of soundness for arbitrary restrictions.

Editorial extensions

If this is right

  • Subset selection and optimisation queries become composable relational expressions, so their results can feed further joins, selections, and subsequent optimisation stages.
  • A query optimiser can choose between set-based evaluation and constraint-solving evaluation based on problem characteristics, because the same expression maps to both styles.
  • The polymorphic SQL layer needs no new keywords: standard SELECT/FROM/WHERE/GROUP BY/ORDER BY/LIMIT clauses already express search, restriction, ordering, and limits.
  • The expressiveness claims imply NP-complete decision and NP-hard optimisation problems are representable without sacrificing finite-result safety for finite inputs.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If Φ is sound, the flat_U encoding suggests a natural cost model: when |Base| is small the search space is small, so the optimiser can pick set enumeration; when the flattened constraint set is hard, it should hand off to a constraint solver—this is an implicit design cue the paper does not develop.
  • The symbolic-reference encoding could serve as a compiler intermediate representation for a wider family of solvers than the demonstrated one, including SAT and SMT back-ends, since it already separates problem structure from decision variables.
  • A testable extension is to relax the total-function assumption and treat partial functions f: Base ⇀ Decision directly, which would make 'choose at most one' and optional-assignment problems more natural; the paper notes total functions are no loss of generality but does not work out the ergonomics.
  • The compositional semantics open a route to incremental re-optimisation: a chain of solution sets can be re-solved stage by stage when data changes, rather than recomputing the whole flattened space.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper sets out to unify subset-selection and optimisation queries with classical relational algebra. It introduces complete domain relations (CDRs), defined by characteristic functions rather than finite extensions, and solution sets, a higher-order structure whose candidates are all functions f : Base → Decision. A translation Φ is claimed to map solution-set algebra RAsol back to standard relational algebra, and the framework is illustrated on Latin squares, production planning, meal planning, energy balancing, and a Pareto optimisation problem. The paper also surveys prior SQL/RA extensions and claims that solution sets match the expressiveness of SolveDB while providing a cleaner algebraic foundation.

Significance. If the central claims held, the paper would make a useful conceptual contribution: a single algebraic setting in which ordinary queries, subset selection, and optimisation are compositional, with a formal route from algebra to solvers. The definitions of CDRs and solution sets are clearly presented, and the worked examples are instructive. The related-work survey is thorough and gives appropriate credit to prior systems such as SQLMP, SCL, CombSQL+, package queries, and SolveDB. However, the main theoretical load rests on the soundness of the translation Φ and on the claimed NP-complete/hard expressiveness; the paper explicitly defers the required proofs, and the translation as specified in Appendix G.4 contains non-standard symbolic constructs. The significance is therefore conditional: the framework is plausible and worth developing, but the foundational claims are not yet established at the level the paper asserts.

major comments (4)
  1. [§5 and Appendix G.4] The claimed homomorphism Φ is not a translation into the standard RA defined in §2/Appendix C. In the decision-attribute-join case, Φ replaces a relation R by a symbolic relation R′ whose attribute values are themselves relational algebra expressions (e.g., π[satFat](σ[recipe=⟨recipe⟩](Recipes)) in Tables 9–10), and aggregation is translated by 'collecting arguments' to be 'evaluated under the control of πsol'. In the RA of Table 4, attributes hold constants, not queries, and γ computes over concrete values. Thus Φ(U) is a symbolic intermediate representation requiring a meta-interpreter, contrary to the third contribution's claim that no interpretive semantics beyond RA is needed. No inductive theorem is proved that relates solutions of U to solutions of Φ(U) for arbitrary χU; the examples are hand-compiled and do not substitute for such a theorem.
  2. [Appendix G.3/G.4] The decision-attribute join rule changes the semantics of natural join. In standard RA, I ⋈ R produces one tuple per matching tuple of R and possibly zero tuples; G.4 instead constructs R′ as a singleton total lookup and states that 'the cardinality of the result is unchanged'. This imposes the extra assumption that every decision value determines exactly one tuple in R, an assumption not stated in §4 or Table 2. The meal-planning example works because recipe is a key of Recipes, but the general case of zero or multiple matches is not addressed. A soundness proof must show that the translated expression has the same filtering effect as the original join for all allowed IExprU; no such proof is given.
  3. [§1, §3, §9] Central theoretical claims are asserted rather than proved. Section 1 states that 'we defer detailed proofs of properties and characterisation of computability, decidability, and termination', and Section 9 lists 'Detailed Proofs' as future work. The NP-completeness expressiveness of CDRs is supported only by transcribing one 3-SAT formula in Listing 1 and by an informal translation of optimisation problems in Appendix D.2; there is no theorem stating which characteristic functions are encodable, no reduction, and no formal complexity statement. Similarly, the query-safety proof in Appendix D.4 covers only the DNF/ADR region; the NP-hard fragment uses non-DNF characteristic functions, and the scope of the safety guarantee is not stated precisely. These are load-bearing for the paper's foundational claims, not presentation details.
  4. [§8 and Eq. (1)] The claimed equivalence with SolveDB is largely definitional. Equation (1) defines dom(U) as the set of all total functions BaseU → DecisionU, and SolveDB's search space is described as the same set of functions; no formal model of SolveDB is given, nor is a mapping between expressions or a characterisation of expressible constraints provided. The conclusion that solution sets 'match the most expressive prior approach' is therefore closer to a restatement than an expressiveness result. This does not invalidate the framework, but the claim should be scoped to 'the same functional structure as SolveDB' unless a formal equivalence is supplied.
minor comments (4)
  1. [§1 and Figures 1, 3, 9, 13, 17] The text says the framework uses 'only standard relational operators—no new keywords and no special clauses', but the SQL examples use non-standard constructs such as SolutionSet(), CompleteRelation(), ALL(SELECT ...) as a standalone predicate, hasSubset(), and PARETO_OPTIMAL(). The presentation should distinguish the polymorphic SQL proposal from standard SQL and moderate the 'no new keywords' claim.
  2. [Figure 2] The figure showing the 16 functions of the Latin-square search space appears to contain many identical tuple sets (e.g., Functions 7, 8, 10, and 11 are displayed with the same tuples). This is likely a rendering or numbering error and should be corrected, since the figure is the first illustration of solution-set cardinality.
  3. [Table 2] The operator notation is inconsistent: the header uses '⊕sol' while the rows use unsubscripted symbols for ω, σ, π, τ, λ, and the definitions of ωsol's default Base and Decision as {⟨⟩} need clarification for non-unary base relations.
  4. [Appendix G.4] The homomorphism statement 'Φ(A⊕B) = Φ[⊕](Φ(A),Φ(B))' uses the symbol Φ[⊕] without defining it. The cases in G.4 define Φ on specific operators, but a formal definition on operator symbols would make the claimed homomorphism checkable.

Circularity Check

2 steps flagged · score 6.0 of 10

Solution-set/SolveDB equivalence is built into Eq. (1), and the Φ translation to 'standard RA' defers symbolic joins and aggregation back to RAsol, making the claimed grounding self-referential.

  1. self definitional [Section 4.2 Eq. (1); Section 8]
    "Solution sets achieve equivalent expressiveness through the same functional structure. For a solution set U =⟨BaseU,DecisionU,χU⟩, the domain corresponds exactly to the set of all functions from BaseU to DecisionU: {f :BaseU→Decision U}. When DecisionU includes infinite domains, the expressiveness is equivalent to that of SolveDB."

    Equation (1) defines dom(U) = {I_U ⊆ Base_U × Decision_U | π[α_BaseU](I_U)=Base_U ∧ FD α_BaseU→α_DecisionU holds in I_U}, which is exactly the set of functions Base_U → Decision_U. Section 7/H.2.9 describes SolveDB's search space as 'all functions f : R → S' over finite R and possibly infinite S. Thus the Section 8 statement that solution sets 'match' SolveDB is not a derived expressiveness theorem: the domain structure was defined to be the same function-set. The equivalence to the most expressive prior approach is therefore built into the definition (Equation 1), and the paper's own conclusion ('Our contribution is not increased expressiveness') confirms that no independent reduction is being performed.

  2. other [Appendix G.4, 'Joins on decision attributes' and 'Aggregation']
    "The value of attributes am∈αmatched will be a symbolic reference to themselves: ⟨am⟩. The value of ad∈αdependent will be a relational algebraic expression retrieving the value given the matched attributes: π[ad](σ[⋀(am =⟨am⟩)|am∈αmatched](R). ... These symbolic aggregations will be evaluated under the control of the RAsol algebra, as part of evaluating a πsol operation."

    Section 5's contribution 3 claims Φ gives formal semantics for solution sets by translation to standard RA ('does not require interpretive semantics beyond that available in relational algebra'). But in the decision-attribute join case, Φ produces an R′ whose attribute values are embedded RA expressions, and in the aggregation case it deliberately does not compute the aggregate: it 'collects arguments' whose evaluation is delegated to the RAsol operator πsol. Standard RA (Section 2/Appendix C) has attributes as constants from domains, and γ aggregates actual values; there is no operator that treats an attribute value as a query to be evaluated later. Therefore Φ(U) is not an RA query for the very cases (joins on decision attributes, symbolic aggregation) that the Cakes and Meal Planner exa

full rationale

The paper is not a data-fitting paper, and there are no fitted parameters called predictions. The only self-citation ([46]) is used for bibliographic context, not as a load-bearing theorem. However, two central equivalences reduce by construction. First, the claimed expressiveness match to SolveDB (Section 8) is guaranteed by Equation (1), which defines solution-set domains as exactly the set of functions Base→Decision—the same function-set structure attributed to SolveDB. Second, and more seriously, the third contribution's translation Φ is supposed to ground solution-set semantics in standard RA. Appendix G.4 shows that for joins on decision attributes and for aggregations over symbolic references, Φ produces expression-valued symbolic relations and 'collects arguments' whose evaluation is deferred 'under the control of the RAsol algebra' during πsol. That is not standard RA and it invokes the very higher-order algebra whose semantics the translation is meant to define. No induction theorem is proved showing solution-set satisfaction is preserved for arbitrary characteristic functions; the examples are hand-compiled. These are definitional/self-referential reductions, not mere incompleteness, so the central foundational unification claim is only partially supported. Honest assessment: substantial independent algebraic content (CDR algebra, RA_sol operators, examples) exists; the circularity is partial, hence 6 rather than 8.

Assumptions & free parameters 0 free parameters · 4 assumptions · 3 invented entities

The paper introduces no fitted numerical parameters. Its formal machinery rests on several unproved or sketched assumptions: the validity of characteristic-function relations as a database primitive, the claimed DNF safety region, the exact correspondence between global constraints and Boolean aggregation, and the semantic preservation of the Phi translation. These are the load-bearing assumptions behind the central claims.

assumptions (4)
  • domain assumption Characteristic functions over arbitrary domains can serve as first-class database relations.
    Section 3 defines CDRs as pairs of attribute set and characteristic function, and builds an algebra over them. This is the foundational extension on which the whole paper rests.
  • ad hoc to paper The DNF region of CDRs is domain-independent and preserved under relational operations in polynomial time.
    Appendix D.4 sketches the argument for join, union, and difference, with complexity estimates, but it is not a formal proof and is stated as a demonstration rather than a theorem.
  • domain assumption Global constraints from constraint programming correspond exactly to Boolean aggregation functions over relations.
    Section 4.1 equates AllDifferent, hasSubset, and similar constraints with gamma-based Boolean aggregations. All solution-set selections depend on this correspondence.
  • ad hoc to paper The translation Phi is homomorphic and semantics-preserving over all valid IExprU.
    Appendix G.4 defines translation by cases but provides no inductive proof that the recursion preserves solution sets, especially for decision-attribute joins that introduce symbolic lookup relations.
invented entities (3)
  • Complete domain relation (CDR)
    purpose: Represent potentially infinite constraint relations via characteristic functions instead of finite extensions.
    A formal construct introduced by the paper; it has no falsifiable handle outside the formal framework.
  • Solution set
    purpose: Represent combinatorial search spaces as sets of candidate relations, one per function from Base to Decision.
    A new mathematical object at the core of the paper; its properties are defined, not empirically verified.
  • Symbolic reference <ai>
    purpose: Connect replicated flat-domain attributes to candidate-relation structure during translation.
    An internal notation device in the Phi translation; no independent evidence of existence beyond the paper's definitions.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Relational Algebras for Subset Selection and Optimisation." pith.science (2026). https://pith.science/paper/QHOZFT5D

@misc{pith2026250906439,
  author       = {Pith},
  title        = {Pith review of: Relational Algebras for Subset Selection and Optimisation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QHOZFT5D}},
  note         = {Machine review of arXiv:2509.06439}
}
read the original abstract

The database community lacks a unified relational query language for subset selection and optimisation queries, limiting both user expression and query optimiser reasoning about such problems. Decades of research (latterly under the rubric of prescriptive analytics) have produced powerful evaluation algorithms with incompatible, ad-hoc SQL extensions that specify and filter through distinct mechanisms. We present the first unified algebraic foundation for these queries, introducing relational exponentiation to complete the fundamental algebraic operations alongside union (addition) and cross product (multiplication). First, we extend relational algebra to complete domain relations-relations defined by characteristic functions rather than explicit extensions-achieving the expressiveness of NP-complete/hard problems, while simultaneously providing query safety for finite inputs. Second, we introduce solution sets, a higher-order relational algebra over sets of relations that naturally expresses search spaces as functions f: Base to Decision, yielding |Decision|^|Base| candidate relations. Third, we provide structure-preserving translation semantics from solution sets to standard relational algebra, enabling mechanical translation to existing evaluation algorithms. This framework achieves the expressiveness of the most powerful prior approaches while providing the theoretical clarity and compositional properties absent in previous work. We demonstrate the capabilities these algebras open up through a polymorphic SQL where standard clauses seamlessly express data management, subset selection, and optimisation queries within a single paradigm.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

58 extracted references · 53 canonical work pages

  1. [1]

    Abiteboul, R

    S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases . Addison Wesley, 1994. https://doi.org/10.5860/choice.33-0359 doi:10.5860/choice.33-0359

    work page doi:10.5860/choice.33-0359 1994

  2. [2]

    Agarwal, Aryan Esmailpour, Xiao Hu, Stavros Sintos, and Jun Yang

    Pankaj K. Agarwal, Aryan Esmailpour, Xiao Hu, Stavros Sintos, and Jun Yang. Computing A Well-Representative Summary of Conjunctive Query Results . Proc. ACM Manag. Data , 2024. https://doi.org/10.1145/3695835 doi:10.1145/3695835

    work page doi:10.1145/3695835 2024

  3. [3]

    Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue

    Marcelo Arenas, Timo Camillo Merkl, Reinhard Pichler, and Cristian Riveros. Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue . Proc. ACM Manag. Data , 2024. https://doi.org/10.1145/3695833 doi:10.1145/3695833

    work page doi:10.1145/3695833 2024

  4. [4]

    Global Constraint Catalog

    Nicolas Beldiceanu, Mats Carlsson, and Jean-Xavier Rampon. Global Constraint Catalog . Technical report, Swedish Institute of Computer Science, Kista, Sweden, 2010

    work page 2010

  5. [5]

    A scalable execution engine for package queries

    Matteo Brucato, Azza Abouzied, and Alexandra Meliou. A scalable execution engine for package queries . SIGMOD Record , 46(1), 2017. https://doi.org/10.1145/3093754.3093761 doi:10.1145/3093754.3093761

    work page arXiv 2017

  6. [6]

    Scalable package queries in relational database systems

    Matteo Brucato, Juan Felipe Beltran, Azza Abouzied, and Alexandra Meliou. Scalable package queries in relational database systems . Proceedings of the VLDB Endowment , 9(7), 2016. https://doi.org/10.14778/2904483.2904489 doi:10.14778/2904483.2904489

    work page arXiv 2016

  7. [7]

    Mannino, A

    Matteo Brucato, M. Mannino, A. Abouzied, P. Haas, and A. Meliou. sPaQLTooLs: A Stochastic Package Query Interface for Scalable Constrained Optimization . Proceedings of the VLDB Endowment , 2020. https://doi.org/10.14778/3415478.3415499 doi:10.14778/3415478.3415499

    work page arXiv 2020

  8. [8]

    Abouzied, P

    Matteo Brucato, Nishant Yadav, A. Abouzied, P. Haas, and A. Meliou. Stochastic Package Queries in Probabilistic Databases . In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data , 2020

    work page 2020

Show all 58 references
  1. [9]

    Combining relational algebra, SQL, constraint modelling, and local search

    Marco Cadoli and Toni Mancini. Combining relational algebra, SQL, constraint modelling, and local search . Theory and Practice of Logic Programming , 7(1-2), 2007. https://doi.org/10.1017/S1471068406002857 doi:10.1017/S1471068406002857

    2007 doi

  2. [10]

    Choobineh

    J. Choobineh. SQLMP: A Data Sublanguage for Representation and Formulation of Linear Mathematical Models . INFORMS journal on computing , 1991. https://doi.org/10.1287/ijoc.3.4.358 doi:10.1287/ijoc.3.4.358

    1991 doi

  3. [11]

    A Relational Model of Data for Large Shared Data Banks

    E F Codd. A Relational Model of Data for Large Shared Data Banks . Communications of the ACM , 13(6), 1970. https://doi.org/10.1145/362384.362685 doi:10.1145/362384.362685

    1970

  4. [12]

    Ramakrishna, A

    Kevin Fernandes, Matteo Brucato, R. Ramakrishna, A. Abouzeid, and A. Meliou. PackageBuilder: querying for packages of tuples . In SIGMOD Conference , 2014. https://doi.org/10.1145/2588555.2612667 doi:10.1145/2588555.2612667

    2014

  5. [13]

    Flener, J

    P. Flener, J. Pearson, and Magnus gren. Introducing esra, a Relational Language for Modelling Combinatorial Problems . International Workshop/Symposium on Logic-based Program Synthesis and Transformation , 2003. https://doi.org/10.1007/978-3-540-45193-8 \_ 95 doi:10.1007/978-3...

    2003 doi

  6. [14]

    Towards Relational Modelling of Combinatorial Optimisation Problems

    Pierre Flener. Towards Relational Modelling of Combinatorial Optimisation Problems . In In Proceedings of IJCAI-2001 Workshop on Modelling and Solving Problems with Constraints. International Joint Conference on Artificial Intelligence , 2001

    2001

  7. [15]

    R. W. Floyd. Nondeterministic Algorithms . JACM , 1967. https://doi.org/10.1145/321420.321422 doi:10.1145/321420.321422

    1967

  8. [16]

    The proper treatment of undefinedness in constraint languages

    Alan M Frisch and Peter J Stuckey. The proper treatment of undefinedness in constraint languages . In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) , volume 5732 LNCS, 2009. https://doi.org/...

    2009 doi

  9. [17]

    k-Clustering with Comparison and Distance Oracles

    Sainyam Galhotra, Rahul Raychaudhury, and Stavros Sintos. k-Clustering with Comparison and Distance Oracles . Proc. ACM Manag. Data , 2024. https://doi.org/10.1145/3695830 doi:10.1145/3695830

    2024 doi

  10. [18]

    Umboh, Hanzhi Wang, Anthony Wirth, and Zhuo Zhang

    Junhao Gan, S. Umboh, Hanzhi Wang, Anthony Wirth, and Zhuo Zhang. Optimal Dynamic Parameterized Subset Sampling . Proc. ACM Manag. Data , 2024. https://doi.org/10.1145/3695827 doi:10.1145/3695827

    2024 doi

  11. [19]

    Computers and Intractability: A Guide to the Theory of NP-Completeness

    Michael R Garey and David S Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W H Freeman, San Francisco, CA, USA, 1979

    1979

  12. [20]

    A. V. Gelder and R. Topor. Safety and translation of relational calculus . TODS , 1991. https://doi.org/10.1145/114325.103712 doi:10.1145/114325.103712

    1991

  13. [21]

    Goldin and P

    Dina Q. Goldin and P. Kanellakis. Constraint query algebras . Constraints , 2004. https://doi.org/10.1007/BF00143878 doi:10.1007/BF00143878

    2004 doi

  14. [22]

    Guagliardo, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, L

    P. Guagliardo, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, L. Peterfreund, and Cristina Sirangelo. Queries with External Predicates . International Conference on Database Theory , 2025. https://doi.org/10.4230/LIPIcs.ICDT.2025.22 doi:10.4230/LIPIcs.ICDT.2025.22

    2025 doi

  15. [23]

    Gyssens and D

    M. Gyssens and D. V. Gucht. The Powerset Algebra as a Natural Tool to Handle Nested Database Relations . Journal of computer and system sciences (Print) , 1992. https://doi.org/10.1016/0022-0000(92)90041-G doi:10.1016/0022-0000(92)90041-G

    1992 doi

  16. [24]

    An algebra of relations for machine computation

    Patrick A V Hall, Peter Hitchcock, and Stephen Todd. An algebra of relations for machine computation . In POPL '75 , 1975

    1975

  17. [25]

    M. R. Hansen, B. S. Hansen, P. Lucas, and P. E. Boas. Integrating Relational Databases and Constraint Languages . Computer languages , 1989. https://doi.org/10.1016/0096-0551(89)90014-3 doi:10.1016/0096-0551(89)90014-3

    1989 doi

  18. [26]

    Hirst and D

    T. Hirst and D. Harel. Completeness results for recursive data bases . Journal of computer and system sciences (Print) , 1993. https://doi.org/10.1145/153850.153905 doi:10.1145/153850.153905

    1993

  19. [27]

    J. Hooker. Integrated methods for optimization . In International Series in Operations Research and Management Science , 2011. https://doi.org/10.1007/978-1-4614-1900-6 doi:10.1007/978-1-4614-1900-6

    2011 doi

  20. [28]

    Hrbacek and T

    K. Hrbacek and T. Jech. Introduction to Set Theory . New York : M. Dekker, 1978. https://doi.org/10.2307/3621546 doi:10.2307/3621546

    1978 doi

  21. [29]

    J Jaffar and J.-L. Lassez. Constraint Logic Programming . In Proceedings of the 14th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages , POPL '87, pages 111--119, New York, NY, USA, 1987. Association for Computing Machinery. https://doi.org/10.1145/41625.4163...

    1987

  22. [30]

    Constraint Query Languages

    Paris C Kanellakis, Gabriel M Kuper, and Peter Z Revesz. Constraint Query Languages . Journal of Computer and System Sciences , 51(1):26--52, 1995. URL: https://doi.org/10.1145/298514.298582, https://doi.org/10.1006/jcss.1995.1051 doi:10.1006/jcss.1995.1051

    1995

  23. [31]

    Anthony C. Klug. Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions . JACM , 1982. https://doi.org/10.1145/322326.322332 doi:10.1145/322326.322332

    1982

  24. [32]

    Query Optimization by Quantifier Elimination

    Christoph Koch and Peter Lindner. Query Optimization by Quantifier Elimination . Proc. ACM Manag. Data , 2024. https://doi.org/10.1145/3651607 doi:10.1145/3651607

    2024 doi

  25. [33]

    F. Kursawe. A Variant of Evolution Strategies for Vector Optimization . Parallel Problem Solving from Nature , 1990. https://doi.org/10.1007/BFb0029752 doi:10.1007/BFb0029752

    1990 doi

  26. [34]

    Abouzeid, Peter J

    Anh Mai, Matteo Brucato, A. Abouzeid, Peter J. Haas, and A. Meliou. Scaling Package Queries to a Billion Tuples via Hierarchical Partitioning and Customized Optimization . Proceedings of the VLDB Endowment , 2023. https://doi.org/10.48550/arXiv.2307.02860 doi:10.48550/arXiv.2307.02860

    2023 doi arXiv

  27. [35]

    The theory of relational databases

    David Maier. The theory of relational databases . Computer Science Press, Rockville, 1983

    1983

  28. [36]

    Incorporating computed relations in relational databases

    David Maier and David S Warren. Incorporating computed relations in relational databases . In Proceedings of the ACM SIGMOD International Conference on Management of Data , 1981. https://doi.org/10.1145/582318.582345 doi:10.1145/582318.582345

    1981

  29. [37]

    Flener, and J

    Toni Mancini, P. Flener, and J. Pearson. Local search over relational databases . Technical report, Uppsala University, 2010

    2010

  30. [38]

    Flener, and J

    Toni Mancini, P. Flener, and J. Pearson. Combinatorial problem solving over relational databases: view synthesis through constraint-based local search . ACM Symposium on Applied Computing , 2012. https://doi.org/10.1145/2245276.2245295 doi:10.1145/2245276.2245295

    2012

  31. [39]

    Lynce, and S

    Joao Marques-Silva, I. Lynce, and S. Malik. Conflict-Driven Clause Learning SAT Solvers . In Handbook of Satisfiability , 2021. https://doi.org/10.3233/978-1-58603-929-5-131 doi:10.3233/978-1-58603-929-5-131

    2021 doi

  32. [40]

    Programming with Constraints: An Introduction

    Kim Marriott and Peter James Stuckey. Programming with Constraints: An Introduction . MIT Press, 1998

    1998

  33. [41]

    Meliou, A

    A. Meliou, A. Abouzeid, Peter J. Haas, R. R. Haque, Anh L. Mai, and Vasileios Vittis. Data Management Perspectives on Prescriptive Analytics (Invited Talk) . International Conference on Database Theory , 2025. https://doi.org/10.4230/LIPIcs.ICDT.2025.2 doi:10.4230/LIPIcs.ICDT.2025.2

    2025 doi

  34. [42]

    An Arithmetic Optimisation Example , 11 2024

    MiniZinc . An Arithmetic Optimisation Example , 11 2024. URL: https://docs.minizinc.dev/en/stable/modelling.html#an-arithmetic-optimisation-example

    2024

  35. [43]

    Pedersen

    Martin Moesmann and T. Pedersen. Data-Driven Prescriptive Analytics Applications: A Comprehensive Survey . Information Systems , 2024. https://doi.org/10.48550/arXiv.2412.00034 doi:10.48550/arXiv.2412.00034

    2024 doi arXiv

  36. [44]

    Nethercote, Peter James Stuckey, Ralph Becket, S

    N. Nethercote, Peter James Stuckey, Ralph Becket, S. Brand, Gregory J. Duck, and Guido Tack. MiniZinc: Towards a Standard CP Modelling Language . International Conference on Principles and Practice of Constraint Programming , 2007. https://doi.org/10.1007/978-3-540-74970-7 \_ ...

    2007 doi

  37. [45]

    Paredaens and D

    J. Paredaens and D. V. Gucht. Converting nested algebra expressions into flat algebra expressions . ACM Transactions on Database Systems , 1992. https://doi.org/10.1145/128765.128768 doi:10.1145/128765.128768

    1992

  38. [46]

    Relational Expressions for Data Transformation and Computation

    David Robert Pratten and Luke Mathieson. Relational Expressions for Data Transformation and Computation . In LNCS,volume 14386 , pages 241--255, 2024. URL: https://link.springer.com/10.1007/978-3-031-47843-7_17, https://doi.org/10.1007/978-3-031-47843-7 \_ 17 doi:10.1007/978-3...

    2024 doi

  39. [47]

    P. Revesz. Safe query languages for constraint databases . TODS , 1998. https://doi.org/10.1145/288086.288088 doi:10.1145/288086.288088

    1998

  40. [48]

    Vrgo c , Nadime Francis, Amélie Gheerbrant, P

    Alexandra Rogova, D. Vrgo c , Nadime Francis, Amélie Gheerbrant, P. Guagliardo, L. Libkin, Victor Marsault, Wim Martens, Filip Murlak, L. Peterfreund, F. Geerts, and Brecht Vandevoort. A Researcher’s Digest of GQL . In 26th International Conference on Database Theory (ICDT 202...

    2023

  41. [49]

    Sabogal, P

    G. Sabogal, P. V. Roy, and Sascha Van Cauwelaert. Implementation of the relation domain for constraint programming . In International Conference on Principles and Practice of Constraint Programming , 2013

    2013

  42. [50]

    Transformation of Combinatorial Optimization Problems Written in Extended SQL into Constraint Problems

    Genki Sakanashi and Masahiko Sakai. Transformation of Combinatorial Optimization Problems Written in Extended SQL into Constraint Problems . ACM-SIGPLAN International Conference on Principles and Practice of Declarative Programming , 2018. https://doi.org/10.1145/3236950.32369...

    2018

  43. [51]

    Transformation of SQL-based combinatorial optimization problems into Constraint problems

    Genki Sakanashi and Masahiko Sakai. Transformation of SQL-based combinatorial optimization problems into Constraint problems . The Japanese Society for Artificial intelligence , 112:12--17, 3 2020. https://doi.org/10.11517/jsaifpai.112.0 \_ 03 doi:10.11517/jsaifpai.112.0 \_ 03

    2020 doi

  44. [52]

    Pedersen

    Laurynas Siksnys and T. Pedersen. Demonstrating SolveDB: An SQL-Based DBMS for Optimization Applications . IEEE International Conference on Data Engineering , 2017. https://doi.org/10.1109/ICDE.2017.180 doi:10.1109/ICDE.2017.180

    2017 doi

  45. [53]

    Pedersen, T

    Laurynas Siksnys, T. Pedersen, T. D. Nielsen, and Davide Frazzetto. SolveDB+: SQL-Based Prescriptive Analytics . International Conference on Extending Database Technology , 2021. https://doi.org/10.5441/002/edbt.2021.13 doi:10.5441/002/edbt.2021.13

    2021 doi

  46. [54]

    SolveDB: Integrating optimization problem solvers into SQL databases

    Laurynas S ik s nys and Torben Bach Pedersen. SolveDB: Integrating optimization problem solvers into SQL databases . In ACM International Conference Proceeding Series , volume 18-20-July-2016, 2016. https://doi.org/10.1145/2949689.2949693 doi:10.1145/2949689.2949693

    2016

  47. [55]

    Enabling Relational Databases for Effective CSP Solving

    Sebastien Siva. Enabling Relational Databases for Effective CSP Solving . PhD thesis, Emory University, Atlanda, GA, 2011

    2011

  48. [56]

    Data Driven Relational Constraint Programming

    Michael Valdron and Ken Q Pu. Data Driven Relational Constraint Programming . In Proceedings - 2020 IEEE 21st International Conference on Information Reuse and Integration for Data Science, IRI 2020 , 2020. https://doi.org/10.1109/IRI49571.2020.00030 doi:10.1109/IRI49571.2020.00030

    2020

  49. [57]

    Valluri and K

    Satyanarayana R. Valluri and K. Karlapalem. Subset Queries in Relational Databases . arXiv.org , 2004

    2004

  50. [58]

    Vieira, H

    Marcos R. Vieira, H. Razente, M. Barioni, Marios Hadjieleftheriou, D. Srivastava, C. Traina, and V. Tsotras. DivDB . Proceedings of the VLDB Endowment , 2011. https://doi.org/10.14778/3402755.3402779 doi:10.14778/3402755.3402779

    2011

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.