Lambda the Ultimate

inactiveTopic GraphPath
started 2/5/2004; 8:50:52 AM - last post 4/29/2004; 5:23:42 PM
Ehud Lamm - GraphPath  blueArrow
2/5/2004; 8:50:52 AM (reads: 10278, responses: 10)
GraphPath is a little-language for analysing graph-structured data, especially RDF. The syntax of GraphPath is reminiscent of Xpath. It has a python implementation that can be teamed up with your favourite python RDF API (e.g. Redland, rdflib, or your own API).

Many interesting things can be represented as graphs (e.g., social networks, web sites, program structure, program call graphs etc. etc.) Indeed, graphs are one the most fundamental abstractions used in computer science (and not just in CS). So it is only natural that I've spent my share of moments trying to design a DSL for graph analysis, the last occasion being when I wanted to give sociologists a tool for exploring social networks. Designing a convinient DSL for this sort of purpose isn't easy.

I haven't checked GraphPath in any depth yet, if someone has - please share your conclusions.

And oh, how is the HotDraw python port coming along Patrick?

Posted to DSL by Ehud Lamm on 2/5/04; 8:53:55 AM

Sjoerd Visscher - Re: GraphPath  blueArrow
2/5/2004; 10:04:22 AM (reads: 588, responses: 3)
I'm a real fan of XPath, and GraphPath looked a bit weird at first. Until I realized the paths are actual Python code. That's actually pretty neat.

However, once you have this:

print "Julie's male ancestors are:" for a in graph>>Node(ex.julie) //Property(ex.parent)[Class(ex.Male)]: print a

then you'd wonder if Python is going to need more Iconic features:

every print graph>>Node(ex.julie) //Property(ex.parent)[Class(ex.Male)]

Bryn Keller - Re: GraphPath  blueArrow
2/5/2004; 10:38:06 AM (reads: 587, responses: 2)
then you'd wonder if Python is going to need more Iconic features:

every print graph>>Node(ex.julie)//Property(ex.parent)[Class(ex.Male)]


def p(thing):

[p(x) for x in graph>>Node(ex.julie)//Property(ex.parent)[Class(ex.Male)]]

And presumably, change the outer brackets to parentheses in Python 2.4 to avoid creating a dummy list of Nones that we just throw away...


Of course (I'll be branded a heretic for mentioning) you can also (ab)use the usual list functions:

filter(p, graph>>Node(ex.julie)//Property(ex.parent)[Class(ex.Male)])

Sjoerd Visscher - Re: GraphPath  blueArrow
2/5/2004; 11:09:26 AM (reads: 575, responses: 1)
Would this work:
maleAnc = graph>>Node(ex.julie)//Property(ex.parent)[Class(ex.Male)]
print maleAnc*

Bryn Keller - Re: GraphPath  blueArrow
2/5/2004; 11:23:44 AM (reads: 581, responses: 0)
Not currently, but it kind of makes sense. I'd expect this to print each item with a space in between rather than the newline we've been using, however.

Ehud Lamm - Re: GraphPath  blueArrow
2/5/2004; 1:47:52 PM (reads: 526, responses: 2)
What is the complexity of the various queries?

Is it possible to nest queries, that is to have a query that results in a subgraph, on which subsequent queries can be performed?

Sjoerd Visscher - Re: GraphPath  blueArrow
2/5/2004; 2:37:01 PM (reads: 527, responses: 1)
That's the only thing it does. That is, not subgraph, but a set of nodes. Starting out with a set of nodes, you can perform basically 2 kinds of subsequent queries: filtering or traversal. Both again return a set of nodes. As far as I can tell, GraphPath does not actually allow you to query for arcs, you can only traverse arcs during a query.

Ehud Lamm - Re: GraphPath  blueArrow
2/5/2004; 3:02:49 PM (reads: 532, responses: 0)
It's a pity your explanation isn't on the web page. Thanks!

Arnold deVos - Re: GraphPath  blueArrow
2/5/2004; 6:36:27 PM (reads: 476, responses: 0)

Glad to see GraphPath provoking a discussion. Just to clarify what GraphPath can do: yes the examples collapse the results to node sets or to tuple sets (using the projection operator %). But more generally you can think of GraphPath expressions as mappings from DLGs -> DG's. e.g.:

# here is a rule to match any path from a child to aunt aunts = Property(ex.parent)/Property(ex.sibling)[Class(ex.Female)]

# binding this expression to a DLG yields a DG dg = family_dlg>>aunts

# we can use aunt_graph like this: dg.terminals( None ) # all aunts dg.initials( None ) # all children with aunts dg.matches( None, ex.lisa ) # lisa's nieces and nephews dg.values( None, ex.david ) # david's aunts

# turn the dg into a list of 2-tuples: [(i, t) for i in dg.initials( None ) for t in dg.values( None, i )]

I need to get rid of the None argument don't I? Standby.

- Arnold

Oleg - Re: GraphPath  blueArrow
2/8/2004; 3:21:45 PM (reads: 327, responses: 0)
print "Julie's male ancestors are:" for a in graph>>Node(ex.julie)//Property(ex.parent)[Class(ex.Male)]: print a

I'd like to point out that using SXPath in Scheme, you can write that example something like

(for-each display ((sxpath '(julie // parent (@ (equal? (class "Male"))))) graph) )

or (let ((compiled-query (sxpath '(julie // parent (@ (equal? (class "Male"))))))) (for-each display (compiled-query graph)))

I'm guessing the schema here. SXPath queries look almost the same as XPath queries, modulo parentheses. Also, XPath separates location steps with slashes; SXPath uses spaces.

One advantage of SXPath is that you can use any appropriate Scheme procedure as a node test or a filter. That point is discussed in
(in particular, Section 3 of that paper).

Marius Amado Alves - Re: GraphPath  blueArrow
4/29/2004; 5:23:42 PM (reads: 117, responses: 0)
I've been playing with the Untyped Network Hypothesis, that states that a typed network (like RDF) can be represented in an untyped one. So I looked at PathGraph for test cases and ideas.

I'm writing a system, Mneson, based on the UNH. Currently the convention to represent typed links is as follows. A typed link A--B-->C is represented by the subgraph A-->Y, B-->Y, Y-->C. The fact that D has the value (property) E is represented simply as D-->E.

I submit that the three functions

  sources (vertex_or_vertex_set) -> vertex_set
  targets (vertex_or_vertex_set) -> vertex_set
  intersect (set_of_vertices_or_vertex_sets) -> vertex_set
with the obvious meanings, are sufficient and necessary for all querying in this scheme. I call this the Mneson Calculus.

I tested the first case in the GraphPath Introduction, for "females´ (whose parent is Nalda) first name". It gives a long expression with the primitives of the Mneson Calculus, but if we define

^ = intersect
with_attr (name, value)
  = sources (targets (name) ^ sources (value))
with_attr (value)
  = sources (value)
attr_val (subjects, attr_name)
  = targets (targets (subjects) ^ targets (attr_name))

then it is simply

attr_val (with_attr (parent, Nalda) ^ with_attr (Female), firstName)

Not bad for an untyped network, uh?

Now I´m (also) interested in the complexity of this. Mneson is based on optimized data structures (Ada 2005 standard containers). The complexity of "sources" and "targets" is trivial. "intersect" is of course the crucial operation regarding complexity. I'm thinking of ways to optimize it. This includes the observation that is seems that the interesting uses of "intersect" are always binary i.e. the intersections are always of only two sets. If this 'conjecture' is true then I think Mneson might have a bright future.

Mneson is at http:/, for those who don't want to Google. There is a lot of cool recent developments that are not there yet. But will be soon, and sooner if required.

Someone mentioned a system called "Mnesia". Interesting name similarity.

Technical note on the expression above. The occurence of with_attr/2 yields more than the really wanted vertices. Namely the result includes vertex "parent". However this does not affect the result of the expression because "parent" most certainly does not have property "Female", and therefore will be excluded from the resulting set. But this is also an issue to look into.