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.