Эффективный запрос к базе данных для предков на ациклическом ориентированном графе

Допустим, у меня есть ациклический ориентированный граф, такой как семейное «дерево» (на самом деле это не дерево, так как у ребенка 2 родителя). Я хочу разместить представление этого графа в реляционной базе данных, чтобы быстро вычислить всех предков узла и всех потомков узла. Как бы вы изобразили этот график? Как бы вы запросили всех потомков? Как бы вы вставляли и удаляли узлы и отношения? Какие предположения вы делаете в отношении данных?

Лучшее решение будет иметь наилучшую большую букву O для числа операторов select / insert / delete , которые вы выполняете для запроса предков и потомков, причем связи, нарушенные лучшими большой O для общего времени выполнения, со связями, нарушенными требованиями к пространству.

Мой коллега задал мне этот вопрос. У меня есть решение, но в худшем случае оно имеет экспоненциальный размер, поэтому я хотел посмотреть, как другие люди решат его.

править

Уточненная реляционная база данных. Этот вопрос тривиален (и скучен), если вы используете базы данных графов со встроенными транзитивными замыканиями.