Hacker News Reader

Comment by tylerhou | Hacker News Reader

Small nitpick: I would say that an abstract graph datatype does exist: it's a relation. I think that idea was not really properly explored by the referenced article. And the relational algebra gives us a powerful way of manipulating the abstract relational datatype, which informs efficient concrete representations.

View on HN

Insightful, and reminds me of Kierkegaard:

Man is spirit. But what is spirit? Spirit is the self. But what is the self? The self is a relation which relates itself to its own self, or it is that in the relation [which accounts for it] that the relation relates itself to its own self; the self is not the relation but [consists in the fact] that the relation relates itself to its own self.

Would this specification suffice for a sentient datalog program? Or is datalog itself sentient?

You've captured my intrigue, and now I want to explore datalog, so thank you for writing the article.

Regarding relational algebra in particular: It is interesting that important and frequently needed relations on graphs cannot be expressed in relational algebra. The transitive closure of a relation is a well-known example, and as you nicely show in your article this relation can be easily and very naturally expressed in two lines of Datalog. For example, we can easily express reachability in a graph:

    reachable(V, V) :- vertex(V).     
    reachable(From, To) :-            
            arc_from_to(From, Next),  
            reachable(Next, To).

One can show that Datalog with two very conservative and simple extensions (allowing negation of extensional database relations, and assuming a total order on the domain elements) captures the complexity class P, so can be used to decide exactly those properties of databases (and hence graphs) that are evaluable in polynomial time, a major result from descriptive complexity theory.

An example of such a property is CONNECTIVITY ("Is the graph connected?"), which can be easily expressed with Datalog on ordered databases, where we assume 3 built-in predicates (such as first/1, succ/2 and last/1) to express an ordering of domain elements:

    connected(X) :- first(X).
    connected(Y) :- connected(X), succ(X, Y), reachable(X, Y).

    connected    :- last(X), connected(X).

If such an ordering is not available via built-in predicates, then we can easily define it ourselves for any given concrete database by adding suitable facts. Also negated EDB relations can be easily defined for any database as concrete additional relations.

Yes, you're right that one cannot express Datalog semantics (and also transitive closure semantics) with just one "query", as queries cannot be recursive.

If you view each rule as a query, however, looping over rules does capture Datalog semantics. Furthermore, by optimizing over rules using the relational algebra, one can derive algorithms "equivalent" to traditional graph algorithms.

(I don't think you would disagree with me; just want to clarify for other people who might be reading.)

Reply on news.ycombinator.com