CareerCup

This is a pretty general solution:

Table Nodes
(Node_ID INT, Node_Value X)
Table Adjacents
(Node_ID INT, Adj_Node_ID INT, PathCost INT)

Then to retrieve all children of a node:
Select Adj_Node_ID from Adjacents Where Node_ID=SomeNodeId

To retrieve the 'parents' of a node:
Select Node_ID from Adjacents Where Adj_Node_ID=SomeNodeId

Store the graph as edge list. Columns: src, dst, cost. Create an index on columns src and dst.
Query:
To get all parents and child nodes of node A.
Select src as parent from edgelist where dst='A' union
select dst as child from edgelist where src='A'

single index on src& dst or one index for src and another for dst?

traverse the graph (N1->N2), (N1->N3), (N1->N4), (N2->N3), and (N3->N4) and extract nodes and add them to node_master table:

<node_master>
node_id, node_value
N1 1234
N2 34
N3 56
N4 90

Then for each node, extract the children, add them to node_family table:
<node_family>
node_parent, node_child
N1 N2
N1 N3
N1 N4
N2 N3
N3 N4

Then to find the parent/child: SQL query may be:

SELECT node_master.node_id, node_family.node_child
FROM node_master INNER JOIN node_family
ON node_master.node_id = node_family.node_id
WHERE <specify a filter>;

I'd keep the PATH infomation for each node.

Table Node
- Id
- Value (or Cost)
- Path

Assume that the graph is like below.
(i.e. a complete binary tree which is a special form of a graph)

.                  1

       2                    3

 4         5           6        7

8 9    10 11    12 13    14 15

Example Rows for the graph above:

Id Path
-------------------------
1.......... NULL
2.......... 1
3.......... 1
4.......... 1,2
5.......... 1,2
6.......... 1,3
7.......... 1,3
8.......... 1,2,4
9.......... 1,2,4
10..........1,2,5
11..........1,2,5
12..........1,3,6
13..........1,3,6
14..........1,3,7
15..........1,3,7

Selecting all parents of Node X:

.        SELECT [Path] FROM [PathTable] WHERE [Id] = X;

Selecting all children of Node X:

.        declare @path varchar(max);
        set @path = (SELECT [Path] FROM [PathTable] WHERE [Id] = X);
        set @path = @path + ',%';
        SELECT [Id] FROM [PathTable] WHERE [Path] LIKE @path;

However, this is only an optimization for the given conditions. There are many disadvantages of this solution. For example insert and delete operations are too costly since you need to update all impacted paths in the table..

A self referential table would work.

1
/ \
2 3
/ \ \
4 5 6

Example Node Table
| ItemId | ParentId |
| 1 | NULL |
| 2 | 1 |
| 3 | 1 |
| 4 | 2 |
| 5 | 2 |
| 6 | 3 |

To select parent of node 2:
SELECT ParentId FROM Node WHERE ItemId = 2;
To select children of node 2:
SELECT ItemId FROM Node Where ParentId = 2;