How do I determine whether query in tuple relational calculus is a safe query?

  • 5
    $\begingroup$ Hi @tomp: What is a tuple relational calculus? What is a safe query? While google or wiki provide some explanations, maybe you should put them into your question by using the edit function above. This will makes your question more readable, and increases the possibility of being answered. $\endgroup$ – Hsien-Chih Chang 張顯之 Dec 13 '10 at 13:59

I attended a course on database theory some time ago, but I’m a bit rusty on the topic, so take what follows with a grain of salt.

If by “safe” you mean “domain independent”, then I think you’re out of luck: domain independence is undecidable, as unsatisfiability of relational calculus queries reduces to it.

I believe you can find the details on the slides for the above-mentioned course, and in the book Foundations of Databases by Abiteboul, Hull, and Vianu.

  • $\begingroup$ It would be good to mention that the unsatisfiability problem is not always undecidable. For instance, deciding the unsatisfiability of a CNF formula is in coNP. Yet, say in first-order logic, unsatisfiability is undecidable. $\endgroup$ – M.S. Dousti Dec 14 '10 at 4:23
  • 1
    $\begingroup$ Yes, I was referring to the satisfiability of relational calculus queries; I edited the answer to clarify that. $\endgroup$ – Antonio E. Porreca Dec 14 '10 at 5:39

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.