{"id":93071,"date":"2021-12-27T17:48:13","date_gmt":"2021-12-27T17:48:13","guid":{"rendered":"https:\/\/www.red-gate.com\/simple-talk\/?p=93071"},"modified":"2021-12-27T17:48:13","modified_gmt":"2021-12-27T17:48:13","slug":"quantifier-predicates","status":"publish","type":"post","link":"https:\/\/www.red-gate.com\/simple-talk\/databases\/sql-server\/t-sql-programming-sql-server\/quantifier-predicates\/","title":{"rendered":"Quantifier predicates"},"content":{"rendered":"

SQL is based on set theory and logic. The only bad news is that many programmers have never had a class on either of those topics. They muddle through using the Boolean operators in their programming language and think that\u2019s all there is to formal logic.<\/p>\n

Let\u2019s flashback to the early days of logic and play catch up. We need to start with syllogisms. Syllogisms are logical forms made up of combinations of two statements about classes of things that lead to a conclusion. They were invented by the Greeks and written up by Aristotle in Prior Analytics<\/em><\/a>. You might have run into them, If you had a philosophy class that included lectures on formal fallacies. The three forms of statements allowed are:<\/p>\n

1) ALL x ARE y<\/p>\n

2) SOME x ARE y<\/p>\n

3) NO x ARE y<\/p>\n

These simple tools let us take two statements and come to a valid conclusion:<\/p>\n

All men are mortal<\/p>\n

All Greeks are Men<\/p>\n

therefore: All Greeks are mortal<\/p>\n

The Ancient Greeks seem to like to use a minimal set of tools which we could expect from a culture that gave us only circles and straight edges in plane geometry. We know that our logic was valid, so we are confident he will die if we know that Aristotle is a Greek. A polysyllogism, or a sorites, is a set of three or more such constructs that can be chained together to come to a conclusion.<\/p>\n

You can figure out syllogisms or sorites using Euler circles, Venn diagrams, or Lewis Carroll\u2019s diagrams. And before you ask, yes, it is that <\/em>Lewis Carroll. People tend to forget that he was one of the pioneers in the evolution of logic. You don\u2019t hear more about him when you\u2019re studying early logic because he was on the losing side of a philosophical argument called \u201cexistential import\u201d in the literature. Briefly, this has to do with what \u201cALL x ARE y\u201d means. Does it imply that \u201cSOME x ARE y\u201d and that \u201cNO x ARE non-y\u201d; that is, there are x\u2019s in the universe. Or does it mean only that \u201cNO x ARE non-y\u201d? I will get back to this point shortly.<\/p>\n

George Boole and his book \u201cLaws of Thought\u201d (available in reprint additions to this very day) gave us the Boolean algebra that dominates programming languages with the basic AND<\/code>, OR<\/code>, and NOT<\/code> operators we\u2019ve come to know and love over the decades. Our syllogisms mutated into quantifiers which could be applied to the Boolean algebra expressions. The two forms are For all x, P(x),<\/code> and For some x, P(x).<\/code> If you want to look up formulas in a textbook, the symbol for the universal quantifier is \u2200, an inverted letter ‘A’, and the symbol for the existential quantifier is \u2203, a rotated letter \u2018E\u2019.<\/p>\n

Existential import lost the battle, and the modern convention is that “All men are mortal” has the same meaning as “There are no men who are immortal” but does not imply that any men exist at all.<\/p>\n

The reasoning is that if I were to walk into a bar and announce that I can beat any pink elephant in the bar, that would be a true statement. The fact that there are no pink elephants in the bar merely shows that the problem is reduced to the minimum case. If this still seems unnatural, then consider the formal mathematical properties of these quantifiers:<\/p>\n

1) (\u2200x)P(x) = \u00ac(\u2203x) \u00acP(x)<\/p>\n

2) (\u2203x)P(x) = \u00ac(\u2200x) \u00acP(x)<\/p>\n

In Boolean terms, you can think of the (\u2200x) quantifier as being a generalized AND<\/code> which connects an infinite string of propositions. Likewise, you can think of the (\u2203x) quantifier as a generalized OR<\/code>, which connects an infinite string of propositions. These generalizations are actually taken from DeMorgan\u2019s Laws.<\/p>\n

The EXISTS() predicate<\/h2>\n

SQL has had the EXISTS()<\/code> predicate since the beginning. It\u2019s interesting within SQL because it has to return either TRUE<\/code> or FALSE<\/code> but can never return UNKNOWN<\/code>. This is an exception to most logical operations inside SQL\u2019s three-valued logic. It\u2019s also not quite the same as the syllogisms we have been talking about.<\/p>\n

Consider the statement “Some salesmen are liars,” and one way we would write it with the EXISTS()<\/code> predicate in SQL:<\/p>\n

...\r\nWHERE EXISTS (SELECT *\r\n FROM Personnel AS P, Liars AS L\r\n WHERE P.job_title = 'Salesman'\r\n AND P.emp_name = L.emp_name);<\/pre>\n
If we are more cynical about salesmen, we might want to formulate the predicate “All salesmen are liars” with the EXISTS<\/code> predicate in SQL, using the transform rule just discussed:<\/p>\n
...\r\nWHERE NOT EXISTS\r\n (SELECT *\r\n FROM Personnel AS P\r\n WHERE P.job_title = 'Salesman'\r\n AND P.emp_name\r\n  NOT IN\r\n  (SELECT L.emp_name\r\n  FROM Liars AS L));<\/pre>\n
This informally says “There are no salesmen who are not liars” in English. In this case, the IN()<\/code> predicate can be changed into a JOIN<\/code>, which might improve performance and be a bit easier to read.<\/p>\n
As an aside, the subquery doesn\u2019t need to evaluate the SELECT<\/code> clause for the EXISTS()<\/code> predicate to work. In one very early version of Oracle, however, the compiler would work out the expressions in the SELECT<\/code> clause and then ignore the results. Today, the preferred form is SELECT *<\/code> because the star represents a nonspecific row in several places in SQL. It is easy to find in the text, and the compiler will not waste any time with expressions in the SELECT <\/code>list (in fairness, this optimization should not be a problem anymore).<\/p>\n
Now, onto the fancy stuff!<\/p>\n
The [SOME | ANY] <subquery> predicate<\/h2>\n
The predicate <value expression> <comparison op> [ANY | SOME] <table expression><\/code> is equivalent to taking each row of the table expression, si,<\/code> (assume that they are numbered from 1 to n) of <table expression><\/code> and testing <value expression> <comparison op> si<\/code> with ORs<\/code> between the expanded expressions:<\/p>\n
((<value expression> <comparison op> s1<\/sub>)\r\nOR (<value expression> <comparison op> s2)<\/sub>\r\n ...\r\nOR (<value expression> <comparison op> sn<\/sub>))<\/pre>\n
When you get a single TRUE<\/code> result, the whole predicate is TRUE<\/code>. As long as <table expression><\/code> has cardinality greater than zero and one non-NULL<\/code> value, you will get a result of TRUE<\/code> or FALSE<\/code>. The keyword SOME<\/code> is the same as ANY<\/code>, and the choice is just a matter of style and readability.<\/p>\n
If you think about it, the IN()<\/code> predicate is equivalent to a simple = ANY<\/code> predicate. In fact, that is how it is defined in the ANSI\/ISO Standard. But the <comparison op><\/code> can be any of =, <, >, <>, <=, >=,<\/code> and (in theory, but not always in practice) any other comparison operator (such as IS [NOT] DISTINCT FROM<\/code>).<\/p>\n
The ALL <subquery> predicate<\/h2>\n
The <value expression> <comp op> ALL <table expression><\/code> takes each row of <table expression>,<\/code> call them s1, s2,.. sn<\/code>, builds a search condition for each such row expression, tests <value expression> <comp op> si<\/code> with ANDs<\/code> between the search conditions, thus:<\/p>\n
((<value expression> <comp op> s1<\/sub>)\r\nAND (<value expression> <comp op> s2<\/sub>)\r\n ...\r\nAND (<value expression> <comp op> sn<\/sub>))<\/pre>\n
When you get a single FALSE<\/code> result, the whole predicate is FALSE<\/code>. As long as <table expression> <\/code>has cardinality greater than zero and all non-NULL<\/code> values, you will get a result of TRUE<\/code> or FALSE<\/code>.<\/p>\n
That sounds reasonable so far. Now let Empty_Table<\/em> be an empty table (no rows, cardinality zero) and Null_Table<\/em> be a table with only NULLs in its rows and a cardinality greater than zero. The rules for SQL say that <value expression> <comp op> ALL Null_Table<\/code> always returns UNKNOWN<\/code>, and likewise <value expression> <comp op> ANY Null_Table<\/code> always returns UNKNOWN<\/code>. This makes sense because every row comparison test in the expansion would return UNKNOWN<\/code>, so the series of OR<\/code> and AND<\/code> operators would behave in the usual way.<\/p>\n
However, <value expression> <comp op> ALL Empty_Set<\/code> always returns TRUE<\/code> and <value expression> <comp op> ANY Empty_Set<\/code> always returns FALSE<\/code>. Most people have no trouble seeing why the ANY<\/code> predicate works that way; you cannot find a match, so the result is FALSE<\/code>. But most people have trouble seeing why the ALL<\/code> predicate is TRUE<\/code>. We are trying to preserve those generalized DeMorgan\u2019s Laws.<\/p>\n
The Foobar.x <comp op> ALL (SELECT y FROM Table2 WHERE <search condition>)<\/code> predicate converts to:<\/p>\n
 ... NOT EXISTS\r\n (SELECT *\r\n FROM Foobar, Table2\r\n WHERE Foobar.x <comp op> Table2.y\r\n AND NOT <search condition>)...<\/pre>\n
The Foobar.x <comp op> ANY (SELECT y FROM Table2 WHERE <search condition>)<\/code> predicate converts to<\/p>\n
 ... EXISTS\r\n (SELECT *\r\n FROM Foobar, Table2\r\n WHERE Foobar.x <comp op> Table2.y\r\n AND <search condition>) ...<\/pre>\n
Of the two quantified predicates, the <comp op> ALL<\/code> predicate is probably the more useful of the two since it cannot be written in terms of an IN()<\/code> predicate. The trick with it is to make sure that its subquery defines the set of values in which you are interested. For example, to find the authors whose books all <\/em>sell for $49.95 or less, you could write:<\/p>\n
SELECT *\r\n FROM Authors AS A1\r\n WHERE 49.95\r\n <= ALL (SELECT book_price\r\n FROM Books AS B1\r\n WHERE A1.author_name = B1.author_name);<\/pre>\n
The best way to think of this is to reverse the usual English sentence “Show me all x that are y” in your mind so that it says “y is the value of all x” instead.<\/p>\n
The ALL predicate and Extrema functions<\/h2>\n
At first, it is counter-intuitive that these two predicates are not<\/em> the same in SQL:<\/p>\n
 x >= (SELECT MAX(y) FROM Foobar)\r\n x >= ALL (SELECT y FROM Foobar)<\/pre>\n
You have to remember the rules for the extrema functions \u2013 they drop out all the NULLs<\/code> before <\/em>returning the greatest, least, or computed value the aggregate function wants. But the ALL<\/code> operator does not drop NULLs<\/code> so that you can get them in the results. (Editor\u2019s note:<\/strong> If any NULLs<\/code> are returned from the subquery, no rows are returned from the main query with ALL<\/code>. While the ALL<\/code> operator is not dropping NULL<\/code>, NULL<\/code> doesn\u2019t show up in the results because the expression >= NULL<\/code> will return UNKNOWN<\/code>.)<\/p>\n
The first expression uses an aggregate function, so it returns a numeric value. In effect, it works like this:<\/p>\n
0) Create the data<\/p>\n
 CREATE TABLE Foobar\r\n(foo_id VARCHAR(10) NOT NULL PRIMARY KEY,\r\n y INTEGER);\r\nINSERT INTO Foobar VALUES ('Albert', 42), ('Bob', NULL), ('Chuck', 43);<\/pre>\n
1) We can now apply the aggregate function. Remove the rows with NULLs<\/code>.<\/p>\n
(‘Albert’, 42)<\/p>\n
(\u2018Chuck\u2019, 43)<\/p>\n
2) Find the maximum value in the column of y in the remaining rows.<\/p>\n
{(42), (43)} => (43) and finally x>= (43)<\/pre>\n
But look at the second expression. That ALL()<\/code> predicate makes this a logical expression. <\/em>Bob\u2019s NULL<\/code> is not removed as it would be with an aggregation. Instead, we build a chain of AND<\/code>-ed predicates:<\/p>\n
((‘Albert’, 42)<\/p>\n
AND (‘Bob’, NULL)<\/p>\n
AND (\u2018Chuck\u2019, 43))<\/p>\n
Which becomes in effect:<\/p>\n
((42 >= x)\r\nAND (NULL >= x) --- UNKNOWN\r\nAND (43 >= x))<\/pre>\n
SQL\u2019s three-valued logic comes into play here. We know that<\/p>\n
TRUE AND UNKNOWN = UNKNOWN<\/p>\n
FALSE AND UNKNOWN = FALSE<\/p>\n
UNKNOWN AND UNKNOWN = UNKNOWN<\/p>\n
As you can see, once you\u2019ve got an UNKNOWN<\/code> value in a chain of AND<\/code>-ed predicates, you really can\u2019t get it to resolve to a TRUE<\/code> value. You would have to cast them to a known value, using COALESCE()<\/code> or some similar function.<\/p>\n
Conclusion<\/h2>\n
It\u2019s always a good idea to take a little time out and learn some of the more obscure features in this very large language we call SQL. But when you do, have mercy on the poor guys that have to maintain your code after you\u2019re gone. This is what comments are for.<\/p>\n","protected":false},"excerpt":{"rendered":"
Predicates in SQL are often complex and difficult to understand. In this article, Joe Celko explains the logic behind a few of the predicates: EXISTS, SOME, ANY and ALL.…<\/p>\n","protected":false},"author":96214,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[53,143531],"tags":[5134],"coauthors":[6781],"class_list":["post-93071","post","type-post","status-publish","format-standard","hentry","category-featured","category-t-sql-programming-sql-server","tag-sql-prompt"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/93071","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/users\/96214"}],"replies":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/comments?post=93071"}],"version-history":[{"count":3,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/93071\/revisions"}],"predecessor-version":[{"id":93073,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/93071\/revisions\/93073"}],"wp:attachment":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/media?parent=93071"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/categories?post=93071"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/tags?post=93071"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/coauthors?post=93071"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}