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$ Commented Dec 13, 2010 at 13:59

1 Answer 1


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$ Commented Dec 14, 2010 at 4:23
  • 1
    $\begingroup$ Yes, I was referring to the satisfiability of relational calculus queries; I edited the answer to clarify that. $\endgroup$ Commented Dec 14, 2010 at 5:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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