1
$\begingroup$

I am somewhat aware of the correspondence between (tuple and domain) relational calculus, relational algebra, and SQL. To the best of my understanding, one should be able to automatically convert a formula in relational calculus to an SQL query whose run on a database produces rows that make the original formula satisfiable. However, I cannot find any rules for such conversion and I would expect them to exist.

Is my understanding wrong? Where can I find these "conversion" rules? I am specifically interested in how to systematically (automatically) convert predicates involving existential quantifiers.

$\endgroup$
  • 1
    $\begingroup$ Why don't you make an attempt at writing down such conversion rules yourself, and show us how far you were able to get and where you got stuck? $\endgroup$ – D.W. Sep 28 '18 at 4:08
2
$\begingroup$

I am somewhat aware of the correspondence between (tuple and domain) relational calculus, relational algebra, and SQL. To the best of my understanding, one should be able to automatically convert a formula in relational calculus to an SQL query ...

Why do people persist in this confusion? The semantics of SQL is different to Codd's Relational Model. Therefore no 'conversion' makes sense. Specifically:

  • Relations are sets vs SQL tables are multisets.
  • In Tuple Relational Calculus and Domain Relational Calculus, attributes are named, and that is the only way to access attributes vs SQL columns of an SQL table might or might not have names, might or might not have a unique name; can also be accessed by column position (under older SQL standards), and have an obtuse and incomplete algorithm for column positioning of query results.
  • For Relational Algebra, it gets messier: some versions (including in Codd 1972) access columns only positionally; some only by name.

The only formal conversion between any of these is given in Codd 1972 'Relational Completeness', where he uses conversion from TRC to Relational Algebra (not v.v.) to show the expressive completeness of (that version of) RA. (And actually, it's from his 'Alpha', which is an 'implementation' of TRC that was never implemented.)

However, I cannot find any rules for such conversion and I would expect them to exist.

Please give some reference claiming they exist. The usual form of words is that SQL is "based upon" RA or TRC. That's not a claim of convertability, in either direction.

I am specifically interested in how to systematically (automatically) convert predicates involving existential quantifiers.

Given some relation schema

  • S(SNO, SNAME, CITY, STATUS) with predicate 'Supplier identified by SNO is named SNAME, is located in CITY and has status STATUS',

  • a derived predicate 'exists STATUS s.t. Supplier identified by SNO is named SNAME, is located in CITY and has status STATUS'

  • is given by RA: pi(SNO, SNAME, CITY)(S).

  • That is, existentially quantifying an attribute is equivalent to projecting it away. "Projecting away" is also known as REMOVE or project ALL BUT.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.