Agora: Living with XML and Relational

Ioana Manolescu, Daniela Florescu, Donald Kossmann, Florian Xhumari, Dan Olteanu

Software Demonstration at VLDB 2000
 

We demonstrate a data integration system capable of answering XML queries over both relational and XML data, by using relational query processing techniques.
 

The query language for XML queries is Quilt; we query our relational data sources under an XML representation (the user can supply one, or we use a simple default representation).
 

Query processing outline

A Quilt query is taken through the following steps: The demo poster provides a visual representation of these steps.
 

Demonstration scenario

We illustrate the whole query processing chain on the following data collections:
 

Quilt query

The following query implements a join between two XML documents: the XML representation of the table, and the real XML document. For brevity, we show directly the simplified form.

for $d in document("diseases.xml")//diseases,
     $a in $d/article,
     $p in $a/paragraph,
     $r in $d/related_medications/,
     $n in $a@name,
     $rn in $r/medication,

     $m in document("medication.xml")//tuple,
     $b in $m/brand_name
where contains($p, "contagious") and content($rn)=content($b)
return <result>
                fullText($d),
                fullText($m)
       </result>

The first block of for makes the variables iterate over elements from the "diseases.xml" document. Thus, $d iterates over all the diseases, $a over all articles concerning this disease, $r over the global list of medications related to it, while $rn iterates over the actual set of medications; $n is bound to the name attribute of the $d disease element. The second for block iterates over all the tuple elements and extracts the name of the medications (remember that the relational table we consider contains medication information).  From the complete for block result tuples of bindings for all the variables present inside the block.

The where condition performs  a selection on the binding tuples: only those for which $p corresponds to a paragraph containing the word "contagious" are kept, the others are pruned out. Also, the join condition is explicit in the where clause: we want only the bindings from both sources that refer to the same medications (same text content of $rn, which describes the medication in the diseases document, and $b, which corresponds to the medication name in the relational table).

In all, this query asks for all contagious illnesses, and for those illnesses whose recommended medication exists in the medication table, the disease XML element corresponding to $d and the medication tuple, corresponding to the $m variable, are output in a <result> element.

Translating the Quilt query to SQL on the generic schema

General framework

The translation of the for-where clause is quite easy, because it is conceptually close to SQL: variables iterate over collections, some selections on variable tuples are applied, and the result consists of bindings of tuples. Translating the return clause is more ellaborate, since we have to construct hierarchical XML structure from binding tuples. To do this, we use the "sorted outer union" approach proposed by a research group from IBM Almaden. The idea is the following. To translate a query whose return clause constructsXML structure, a single query is issued first, that returns the binding tuples produced by the for-where block; then, a separate query is issued to retrieve each piece of information that is needed in the result. The tagging module structures the information extracted by these different queries into the desired hierarchical result.
In our case, the return clause needs two distinct pieces of data: the full textual representation of the disease element, and the textual representation of the medication element.  We issue therefore three SQL queries: one corresponding to the for-where block, and one for each data item needed in the result.

Here is the SQL query corresponding to the for-where clause of the original Quilt query:
 
select e0.elID as $d, e1.elID as $a, e2.elID as $p, e3.elID as $r, a0.attrID as $n, e4.elID as $rn, e5.elID as $m, e6.elID as $b,
null as dText, null as mText
from  Document d0, URI u0, Value v0, TransClosure tc0, Element e0, QName q0, Value v0,
Child c0, Element e1, QName q1, Value v1, Child c1, Element e2, QName q2, Value v2,
Child c2, Element e3, QName q3, Value v3,  Attribute a0, Value v4, Value v5,
Child c3, Element e4, QName q4, Value v6, Child c4, Value v7,
Document d1, URI u1, Value v8, TransClosure tc1, Element e5, QName q5, Value v9,
Child c5, Element e6, QName q6, Value v10, Contains fn0
where d0.docURIID=u0.uriID and u0.uriValID=v0.valID and v0.value="diseases.xml" 
and d0.docRootID=tc0.parentID and tc0.childID=e0.elID and e0.elQNameID=q0.qNameID and 
q0.qnLocalID="disease" and e0.elID=c0.parentID and c0.childID=e1.elID and 
e1.elQNameID=q1.qNameID and q1.qnLocalID=v1.valID and v1.value="article" and 
e1.elID=c1.parentID and c1.childID=e2.elID and e2.elQNameID=q2.qNameID and q2.qnLocalID=v2.valID and
v2.value="paragraph" and e0.elID=c2.parentID and c2.childID=e3.elID and e3.elQNameID=q3.qNameID and 
q3.qnLocalID=v3.valID and v3.value="related_medications" and a0.attrElID=e3.elID and a0.attrNameID=v4.valID and
v4.value="name" and a0.attrValID=v5.valID and e3.elID=c3.parentID and c3.childID=e4.elID and 
e4.elQNameID=q4.qNameID and q4.qnLocalID=v6.valID and v6.value="medication" and
d1.docURIID=u1.uriID and u1.uriValID=v8.valID and v8.value="medication.xml" and 
d1.docRootID=tc1.parentID and tc1.childID=e5.elID and e5.elQNameID=q5.qNameID and 
q5.qnLocalID=v9.valID and v9.value="tuple" and c5.parentID=e5.elID and c5.childID=e6.elID and
e6.elQNameID=q6.qNameID and q6.qnLocalID=v10.valID and v10.value="brand_name" and
fn0.in0=e2.elID and fn0.in1="contagious" and fn0.out=true and c4.parentID=e3.elID and c4.childValID=v7.valID and v7.value=v5.value

In this query, the red tables and conditions correspond to elements, attributes, and parent-child relationships in the "diseases.xml" document; the blue part of the query comes from the query fragment describing elements of the "medication.xml" document. We left in black the function Contains, which does not belong to any data source; on the last line, the actual join predicate is shown in green.

How is this query constructed ? We use a generic schema (described in the demo paper) that reflects the structure of an XML document and provides natural support for translating XML path expressions. For example, there is a relation Document(docID, docRootID, docURIID), a relation Element(elID, elQNameID) etc. To represent filiation in the original XML documents, joins on foreign keys are used throughout the query. Note that text content (direct #PCDATA children of one node) is represented by  Element-Child-Value joins, as it is the case with e3, c4, and v7.

Constructing the remaining two queries Let us denote the query above as "select e0.elID as  $d, e1.elID as $a, e2.elID as $p, e3.elID as $r, a0.attrID as $n, e4.elID as $rn, e5.elID as $m, e6.elID as $b from F0 where W0". We construct the two other queries simply by adding the extra joins that are needed to connect the binding tuples with the data items needed in the result:
 
 
select  e0.elID as  $d, e1.elID as $a, e2.elID as $p, e3.elID as $r, a0.attrIDas $n, e4.elID as $rn, e5.elID as $m, e6.elID as $b, fn1.out as dText, null as mText 
from F0, FullText fn1
where fn1.in1=e0.elID

 
 
select  e0.elID as  $d, e1.elID as $a, e2.elID as $p, e3.elID as $r, a0.attrIDas $n, e4.elID as $rn, e5.elID as $m, e6.elID as $b, null as dText, fn2.out as mText
from F0, FullText fn2
where fn2.in1=e5.elID

Having established these translations, the Quilt query is transformed in the union of these three SQL queries on the generic schema: the query corresponding to the for-where part, and one query per (non-constant) data item needed in the result.
 

Rewriting the query on the generic schema to real data sources

At this stage, we use standard relational query rewriting algorithms (for bag semantics). We therefore need to show how are the data sources defined as SQL views over the generic schema.

View definition for the real relational table

We show below the view definition for the Medication table presented above. For brevity, we show the view definition corresponding to the table having just two columns, "generic_name" and "prescribed_for":
 
select e1.elID as $m, v4.value as generic_name, v5.value as prescribed_for
from Document d0, URI u0, Value v0, Child c0, Element e0, QName q0, Value v1, Child c1, Element e1, QName q1, Value v2,
Child c2, Element e2, QName q2, Value v3, Child c3, Value v4, Child c4, Value v5
where d0.docURIID=u0.uriID and u0.uriValID=v0.valID and v0.value="medication.xml" and d0.docRootID=e0.elID and
e0.elQNameID=q0.qNameID and q0.qnLocalID=v1.valID and v1.value="table" and c0.parentID=e0.elID and 
c0.childID=e1.elID and e1.elQNameID=q1.qNameID and q1.qnLocalID=v2.valID and v2.value="tuple" and 
c1.parentID=e1.elID and c1.childID=e2.elID and e2.elQNameID=q2.qNameID and q2.qnLocalID=v3.valID and 
v3.value="generic_name" and c2.parentID=e1.elID and c2.childID=e3.elID and e3.elQNameID=q3.qNameID and 
q3.qnLocalID=v3.valID and v3.value="prescribed_for" and c3.parentID=e2.elID and c3.childValID=v4.valID and
c4.parentID=e3.elID and c4.childValID=v5.valID

View definitions for the XML data sources

An XML document is accessed via the DOM API; once parsed, it becomes an in-memory object on which DOM calls can be made to retrieve, say, the attributes of a given element, or all its descendents having a specific tag etc.  We model each of these calls as a table, in which certain attributes have to be supplied (by joins or selections) in order to obtain values for the other attributes.  For example, here is the view definition for the call

x.getElementByName(z)

which returns all the descendents of element x having the tag z.
 
select tc0.parentID as x, e1.elID as y, v0.value as z
from TransClosure tc0, Element e1, QName q0, Value v0
where tc0.childID=e1.elID and e1.elQNameID=q0.qNameID and q0.qnLocalID=v0.valID

A similar view definition exists for all the DOM API calls, and the view definitions are used to rewrite the query resulted from the translation of the Quilt query.

Rewritten Quilt query

To rewrite the union of SQL terms, each term is rewritten in isolation and the union of the rewritings is then taken.  For illustration, here is the rewriting of the last union term resulting from the translated query, as described above:
 
select c0.parent as $d, t0.element as $a, t1.element as $p, t2.element as $r, t3.element as $rn, null as dText, FnText(med) as mText
from Medication med, Document d0, ElementByName ebn0, Children c0, Tag t0, Children c1,  Tag t1, Children c2,  Tag t2, Attribute a0,
Children c3,  Tag t3,  Contains fn0,  Children c4
where d0.docName="diseases.xml" and d0.docRoot=ebn0.ancestor and ebn0.tag="disease" and ebn0.descendent=c0.parent and
c0.child=t0.element and t0.tag="article" and c0.parent=c1.parent and c1.child=t1.element and t1.tag="paragraph" and
c0.parent=c2.parent and c2.child=t2.element and t2.tag="related_medications" and  c1.parent=a0.attrElem and 
a0.attrName="name" and c3.parent=c2.child and c3.child=t3.element and t3.tag="medication" and
fn0.in0=t1.element and fn0.in1="contagious" and fn0.out=true and c4.parent=t2.element and c4.childVal=med.brand_name

Notice that the elements from the "medication.xml" document have disappeared, and have been replaced with an occurence of the Medication table. Also, the FnText() function replaces the generic FullText() function: if FullText() operates at the level of the virtual schema on any XML document (and constructs its full textual representation), MedText() has to be implemented directly at the level of the DBMS storing the Medication table, since its implementation has to be aware of the actual storage of the data.
 

Query Optimization and execution

At this stage we apply an optimization algorithm based on dynamic programming, searching in the space of bushy trees. A particularity of our optimization algorithm is that it has to take into consideration access restrictions, like the one encountered for the ElementByName table: a scan of this table is not possible, rather, the ancestor and tag attributes have to be specified in order to get bindings for the descendents.
The relational query execution follows the regular iterator model.
 

Tagging the result

The execution of the three relational queries (resulting from the rewriting phase) yields three streams of tuples. The first stream contains all tuple bindings resulting from the for-where clause. The second stream contains those binding tuples that could be extended with  FullText($m); in our case, this extension was possible for every binding of $d, so all binding tuples from the first union term are present in the second. In the general case, however, the second term introduces extra joins that may erase some binding combinations from the first term. Similarly, the third union term contains binding tuples extended with the textual representation of $m.
These tuples coming from different streams contain different informations; to be able to distinguish among them, we introduce a numerical constant column, called "label", which has the value 0 for all tuples coming from the first term, 1 for the tuples coming from the next one etc.

For a given ($d, $p, $a, $rn, $r) combination, the dText field is contained in tuples from the second union term, and the mText field is contained in tuples from the third union term. To group together these items, and to be able to output them together in a single <result> element, we perform a sort on the ($d, $p, $a, $rn, $r, label) fields of all tuples in the union. After the sort, using the techniques described here, the information contained in the tuples is assembled together to produce the desided result.
 

For a more up-to-date description of the demo scenario, please visit the demo page.