Question

Consider the following three tables where keys are underlined: Graphs(graphid, graphname), Nodes(nodeid, nodename, nodeweight, graphid), Edges(parentid, childid, edgeweight, graphid), formulate a SQL statement for each query in the following.

3. Suppose there is a node X in graph with graphid = 1234 such that all other nodes are the parents of node X. Return the nodeid of node X.

Answer 1

The basic logic behind the following SQL query is to first check for all nodes of graphid = 1234 whether they satisfy the condition that no. of times they appear in childid field = no. of nodes in the graph (graphid = 1234) - 1(node itself)

The node which has all other nodes as his parents should appear (n-1) times in edges table where n is the no. of nodes in the given graph.

SQL statement:

SELECT nodeid

FROM Nodes

WHERE graphid = 1234

AND

(

SELECT count(childid)+1

FROM Edges

WHERE childid=nodeid

AND

graphid = 1234

GROUP BY childid

)

=

(

SELECT count(nodeid)

FROM Nodes

WHERE graphid = 1234

GROUP BY graphid

) ;

For implementation, I made simple tables inside MySQL 5.5

mysql> select * from Graphs; graphid | graphname | + 1234 | Graphi T + 1 row in set (0.00 sec) mysql> select from Nodes; nodeid nodename | nodeweight | graphid | 1 A 2 B 3C 1 11 11 1234 1234| 1234| 3 rows in set (0.03 sec) mysql> select * from Edges; parentid | childid | edgeweight | graphid | 11 31 21 21 11 11 1234| 1234 2 rows in set (0.00 sec)

Then I ran the given query:

mysql> select nodeid -> from nodes -> where graphid -> and = 1234 -> select count(childid) + 1 -> from edges -> where childid=nodeid -> and -> graphid = 1234 -> group by childid -> = -> ( -> select count(nodeid) -> from nodes -> where graphid = 1234 -> group by graphid + nodeid | + 21 -+ 1 row in set (0.04 sec)