Efficient database query for ancestors on an acyclic directed graph

If selects > manipulations, and especially subtree selects (all ancestors, all descendants) I'd go for a Closure-table approach. Yes, an explosion of paths in your path-table, but it does deliver results fast (as opposed to the adjacency model), and keeps updates limited to relevant portions (as opposed to 50% update with nested sets).

Bill Karwin has some nice presentation online about pros and cons of different models, see http://www.slideshare.net/billkarwin/models-for-hierarchical-data (slide 48 is an overview).

For DAGs in SQL databases there appeared to be only two solutions:

1. Recursive WITH clause.

2. Transitive closure

I'm not aware of any practical graph labeling scheme (like nested sets,intervals or materialized path)

RDBMS:s aren't really designed to handle this kind of data. The obvious choice is to use a graph database instead, then there's no need to translate the graph into a different representation, you use an graph API all the way. There's a good presentation by Marko Rodriguez explaining the impact of the underlying data model when dealing with graph traversals, see The Graph Traversal Programming Pattern if you want to look deeper into that.

I wrote up a simple example of handling DAGs with the Neo4j graph database a while ago which may be useful to you.