It is an established fact that SQL-92 cannot query a tree or graph structure (represented as parent-child pairs) without procedural extensions. However, with minor preprocessing, a tree can be augmented with keys which make retrieval simple and fast. There are several approaches which have different insert and update performance, and space requirements.
Traversal Order Indexing (also known as the "nested sets" approach)
Imagine traversing a tree (in pre-order, say) and tagging each node with a sequence number in the order encountered. The useful property of these sequence numbers is that they fall into a continous range for each subtree, i.e. if a given node X is assigned sequence number k, its descendants will have sequence numbers k+1...k+C, where C is the number of descendants of X. Finding the descendants is as simple as retrieving all nodes within that range. If, during the traversal, we also tag X with the last number (k+C) in its subtree, X will have all the information needed to get X's descendants.
This method requires that the sequence numbers be updated when a new node is inserted; every sequence number after the new node must be incremented. In a database which uses table locks, this requirement may not be so onerous, but in general, it is. Various workarounds avoid having to renumber on every insert by leaving empty slots in the numbering.
Materialized Paths
The familiar dotted notation (chapter 2, section 2.1, 2.2, 2.2.1, etc.) for chapters and sections of documents uses this construct, as does just about every filesystem. Each node X is given a path X1.X2...Xk with the id's of its ancestors starting from root, and ending at X. X itself can be omitted from the path, saving some space. Finding the descendants of X requires a simple range query to find all nodes with a path between X1...Xk and X1...XkZ, where Z is a maximum value like MAXINT. Ordering by the paths puts the nodes in the correct display order.
Inserting nodes is simpler because no global updates are needed; new paths simply fit in between the older ones.
Maintaining the whole transitive closure
The transitive closure of a tree is a table of all ancestor-descendant pairs, no matter how many hops between them. For a node X at depth D, the TC will contain D ancestor-X pairs. Finding all descendants of a node is a very straightforward query, but the results may be hard to put in the correct display order.
Updating the TC on inserts and deletes is also a fairly complex operation, but not impossible.
Recursive queries
While I said I was talking about SQL-92, the more recent standard includes recursive queries, where a query can refer to its own result set in the FROM clause. So expressing defining a set S as "the root node, plus any node connected to S" is possible.
And, of course, Oracle has its venerable "connect by" clause, which is more limited.
