OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help



   Re: Research notebook: On edge-labelled graphs in XML

[ Lists Home | Date Index | Thread Index ]
  • From: tpassin@home.com
  • To: xml-dev@xml.org
  • Date: Wed, 06 Sep 2000 21:55:12 -0400

Dan Brickley asked about work on edge-labeled graphs as they might be used
in XML-related applications.

> So I'm posting a far-from-ready document since I expect RDF Issues to eat
> a bunch of time this month I might've spent on it:
> http://www.w3.org/2000/09/XGraph/
> Research notebook: On edge-labelled graphs in XML
> ...on the basis that it's best to post half-finished but
> material than sit on it for months hoping to perfect it (RDFViz,
> RDF-WordNet etc being previous examples where I've gone against instinct
>   "This document serves as an informal survey of XML applications that
>    an edge-labelled graph data model similar to that used in W3C's
>    Description Framework (RDF)."

I got interested in the edge-labeled approach after I read "Data on the
Web", by Abiteboul, Buneman, and Suciu.  From the book, it appears that a
lot of academic research on querying semi-structured data is based on an
edge-labeled approach. Since a query language for xml documents is sorely
needed, I thought it would be worth looking at the edge-labeled approach a
little more.   I came up with a way to represent XML documents by
edge-labeled graphs - nodes are there mainly to allow for containment of
children or text values - PCDATA (text) can be imagined to be contained in
invisible <text>...</text> elements, so there are edges labeled "text" too.
The edges would contain the attributes, since edges represent elements.

This approach mapped closely to DTDs too - in the DTD the nodes would be
labeled with their multiplicity, and whether they were alternations or not.
Edges would not end in nodes since the DTD contains no actual values.  Thus,
a DTD graph appears remarkably similar to an actual instance graph.

This was interesting and easy to set up.  I was able to write rudimentary
tree-building and xml-writing code very quickly (no, I didn't include the
whole infoset, I was just trying it out).  That's as much as I've done to
date, but it was stimulating.   It makes me think that the subject is worth
while.  But then we've got all those node-based models like DOM, hate to
reinvent all that stuff...


Tom Passin


News | XML in Industry | Calendar | XML Registry
Marketplace | Resources | MyXML.org | Sponsors | Privacy Statement

Copyright 2001 XML.org. This site is hosted by OASIS