You are given a table, BST, containing two columns: N and P, where N represents the value of a node in Binary Tree, and P is the parent of N.

Question - Write a query to find the node type of Binary Tree ordered by the value of the node. Output one of the following for each node:

Root: If node is root node.

Leaf: If node is leaf node.

Inner: If node is neither root nor leaf node.

Solution 1 - I am using dot(.) notation on alias B.N=P

SELECT N,
CASE
   WHEN P IS NULL THEN 'Root'
   WHEN (SELECT COUNT(*) FROM BST WHERE B.N=P)>0 THEN 'Inner'
   ELSE 'Leaf'
END AS PLACE
FROM BST B
ORDER BY N;

Solution 2 - Not using and dot operator?

SELECT N,
CASE
   WHEN P IS NULL THEN 'Root'
   WHEN (SELECT COUNT(*) FROM BST WHERE N=P)>0 THEN 'Inner'
   ELSE 'Leaf'
END AS PLACE
FROM BST 
ORDER BY N;

My question is -

1. Why do the Solution 1 is generating correct answer, is it due to . (dot) ? If it is due to dot operator why we didn't use dot operation on P (B.N = P)?
2. Even I modify solution 2 and write (BST.N = P), it is still giving me wrong answer. Why it is so?

I am confused in usage of .(dot)

CodePudding user response：

You use BST twice in your query. The . tells the DBMS which instance you are using. When omitted, the DBMS has to chose it implicitly.
The table that is implicitly chosen happens not be the same throughout your query.

With more explicit aliases, your query is:

SELECT N,
CASE
   WHEN P IS NULL THEN 'Root'
   WHEN (SELECT COUNT(*) FROM BST InsideAlias WHERE OutsideAlias.N=InsideAlias.P)>0 THEN 'Inner'
   ELSE 'Leaf'
END AS PLACE
FROM BST OutsideAlias

When you remove the aliases, the implicitly chosen instance of BST is:

• Inside the subquery SELECT COUNT(*) FROM BST InsideAlias : InsideAlias
• In the rest of your query: OutsideAlias (InsideAlias is out of scope for the rest of the query anyway).

Which means:

(SELECT COUNT(*) FROM BST InsideAlias WHERE N=P)

is equivalent to

(SELECT COUNT(*) FROM BST InsideAlias WHERE InsideAlias.N=InsideAlias.P)

Therefore, you are getting the wrong results because it requires a node to be its own parent for the COUNT(*) to be greater than 0.

Instead, OutsideAlias.N=InsideAlias.P translates to: is my node the parent of some other node? Another way to do the test is with EXISTS (SELECT * FROM BST WHERE OutsideAlias.N = P), although that was not your question.

CodePudding user response：

This is about correlated subquery. A correlated subquery is a subquery that contains a reference to a table that also appears in the outer query. And how do we distinguish the subquery table and the table from the outer query? There are two cases.

1. The inner table and the outer table are different tables (having different names): In this case,we simply use their table names as they are distinct.
   
2. The inner table and the outer table are the same table (same table name): In this case, in order to distinguish them, we need to give one of them an alias.(Usually we give the outer table an alias )
   Therefore, to answer your first question,please check the comments besides the query:

SELECT N,
CASE
   WHEN P IS NULL THEN 'Root'
   WHEN (SELECT COUNT(*) FROM BST -- this is the table name of the subquery table which does not need an alias
        WHERE B.N=P /*B.N=P means table condition of this subquery requires that value of P from this subquery table BST equals to its outer(parent) table which is aliased as B */)>0 THEN 'Inner'
   ELSE 'Leaf'
END AS PLACE
FROM BST B -- this is the table name of the main query which needs an alias so it can be distinguishable in the correlated subquery  
ORDER BY N;

Before answering your second question, how do we make two tables of the same name distinguishable? We need to give one of them a different name ,which calls for using an alias. But if you use BST.N = P(Here you didn't state in your second question as where you would put the condition. From the context i presume you mean the subquery table condition) in the subquery, then this BST is clearly not identifiable. To fix the issue,give one of them an alias.(preferably the outer table)