Graphs and XML

R. Alexander Milowski

milowski@sims.berkeley.edu

School of Information Management and Systems

#1

Graphs

  • Graphs have:

    • Vertices (e.g. R, A, B, C, D)

    • Edges (e.g. the lines & arrows).

    • Edges & Vertices can have labels.

    • Edges can have directions.

#2

Edges

#3

Formalisms

#4

Example XML

I'll use this for the examples:

<person>
<name><first>Alex</first><last>Milowski</last></name>
<office>103 South Hall</office>
<email>milowski@sims.berkeley.edu</email>
</person>

#5

An XML Graph

#6

An Alternate XML Graph

#7

Graphs and Modeling

#8

Graph Serialization

#9

Cycles - Option 1

#10

Cycles - Option 2

#11

XML for Arbitrary Graphs

#12

University Example

University Relationships

#13

University Example - A Graph Instance

Two Students & Their Classes

#14

University XML - Try 1

<university>
 <name>UC Berkeley</name>
 <department>
  <name>SIMS</name>
  <class id="290-4">
     <student><name>Jane Smith</name></student>
     <student><name>John Doe</name></student>
  </class>
  <class id="290-8">
     <student><name>Jane Smith</name></student>
  </class>
 </department>
</university>

...but 'student' gets duplicated.

#15

University XML - Try 2

Maybe 'student' should be a child of university...

<university>
 <name>UC Berkeley</name>
 <student id="s1"><name>Jane Smith</name></student>
 <student id="s2"><name>John Doe</name></student>
 <department>
  <name>SIMS</name>
  <class id="290-4">
    <student ref="s1"/>
    <student ref="s2"/>
  </class>
  <class id="290-8">
    <student ref="s2"/>
  </class>
 </department>
</university>

But departments can cross-list courses and students can be from other universities...

#16

University XML - "Fully Normalized"

This might be the ultimate in flexibility:

<model>
 <university id="berkeley">
  <name>UC Berkeley</name>
  <department id="sims"/>
 </university>
 <student id="s1"><name>Jane Smith</name></student>
 <student id="s2"><name>John Doe</name></student>
 <department id="sims">
  <name>SIMS</name>
  <class ref="290-4"/>
  <class ref="290-8"/>
 </department>
 <class id="290-4">
    <student ref="s1"/>
    <student ref="s2"/>
 </class>
 <class id="290-8">
    <student ref="s2"/>
 </class>
</model>

But it also might be a pain to process.

#17

RDF & XML

#18

An RDF Example

<c:person xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
          xmlns:c="http://cde.berkeley.edu/contact/#"
          rdf:about="http://cde.berkeley.edu/people#milowski">
    <c:name>Alex Milowski</c:name>
    <c:email rdf:resource="mailto:milowski@sims.berkeley.edu"/>
    <c:title>Instructor Lacky</c:title> 
</c:person>

#19

The RDF Graph