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 張顯之Commented Dec 13, 2010 at 13:59
1 Answer
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