Extracting nested relational queries from implicit definitions

Add to your list(s) Download to your calendar using vCal

• Pierre Pradic (University of Oxford)
• Wednesday 04 November 2020, 13:45-15:30
• https://bham-ac-uk.zoom.us/j/4040590387?pwd=dlJpN0tyUVJQQWxyUzc3SisvcHJtUT09.

If you have a question about this talk, please contact Anupam Das.

(based on joint work with Michael Benedikt, available at http://perso.ens-lyon.fr/pierre.pradic/nestedbeth.pdf)

In this talk, I will present results obtained jointly with Michael Benedikt establishing a connection between the Nested Relational Calculus (NRC) and sets implicitly definable using Δ₀ formulas.

Call a formula φ(I,O) an implicit definition of the relation O(x,...) in terms of I(y,...) if O is functionally determined by I: for every I, O, O’, if both φ(I,O) and φ(I,O’) hold, then we have O ≡ O’. When φ is first-order and I and O are relations over base sorts, then Beth’s definability theorem states that there is a first-order formula ψ(I,x,...) corresponding to O whenever φ(I,O) holds. Further, this explicit definition ψ can be effectively be computed from a sequent calculus proof witnessing that φ is functional. This allows for practical use of implicit definitions in the context of database programming, as there is a well-established link between fragments of explicitly FO definable relations and relational calculi.

NRC is a conservative extension of relational calculi from database theory with limited powerset types in addition to tupling and anonymous base types. NRC expressions thus not only encompass flat relations over primitive datatypes like SQL but also nested collections, while remaining useful in practice.

We extend the above correspondence between first-order logic and flat relational queries to NRC and implicit definitions using set-theoretical Δ₀ formulas over (typed) nested collection. Our proof of the equivalence goes through a notion of Δ₀-interpretation and a generalization of Beth definability for multi-sorted structures. This proof is non-constructive and thus does not yield any useful algorithm for converting implicit definitions into NRC terms. Using an approach more closely related to proof-theoretic interpolation, we give a constructive proof of the result restricted to intuitionistic provability, i.e, when the input functionality proof π of φ(I,O) is carried out in intuitionistic logic. Further, if π is cut-free, this can be done efficiently. Whether or not there exists a polynomial-time procedure working with classical proofs of functionality is still an open problem.

I will focus on the effective result for the talk, and if time allows, discuss the difficulties with extending it to classical logic. I will not assume any background in either database or model theory.

This talk is part of the Theoretical computer science seminar series.

This talk is included in these lists:

• Computer Science Departmental Series
• Computer Science Distinguished Seminars
• Theoretical computer science seminar
• computer sience
• https://bham-ac-uk.zoom.us/j/4040590387?pwd=dlJpN0tyUVJQQWxyUzc3SisvcHJtUT09

Note that ex-directory lists are not shown.