Say I have part of a query in the form: ∃xa(...)∧∃xb(...)∧∃xc(...), where a, b, and c are attributes and the ellipses can be anything (I'm looking for a general rule). Is this equivalent to saying ∃xa,xb,xc(...∧...∧...) - i.e. compacting all the existential quantifiers into one and 'anding' their domains together?

For example, if I have the query:

enter image description here

would it be correct (albeit unwieldy) to write it as:

{ xpid | ∃xpname,xcolor,xsid,xsname,xaddress,xcost,ysid,ysname,yaddress,ycost( PARTS(xpid,xpname,xcolor) ∧ SUPPLIERS(xsid,xsname,xaddress... (and then the rest of the query)

  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – Raphael Apr 9 '14 at 9:57
  • 1
    $\begingroup$ Please don't crosspost on different SE sites simultaneously! Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, feel free to flag for migration or repost. It may be prudent to include links in either direction and explain why the particular perspective of the other site seems useful. $\endgroup$ – Raphael Apr 9 '14 at 11:43

If all the quantified variables are distinct, then you can safely move all quantifiers to the left. This is the only obstruction to this procedure. You can always ensure that all quantified variables are distinct by renaming them. For example, starting with $$(\forall x P(x)) \lor (\forall x Q(x)),$$ we first rename the second variable to $y$, $$(\forall x P(x)) \lor (\forall y Q(y)),$$ and then move the quantifiers to the left, $$ \forall x \forall y (P(x) \lor Q(y)). $$ This is equivalent to the original formula.


You are looking for prenex normal form in which all quantifiers "come first".

It exists for every first-order formula but you have to take care when transforming; multiple quantifiers may use the same variable (name) in the original formula, but they may not in the normal form.


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.