|
|
Database
Systems: Advanced Topics and Implementation
|
|
. |
Mon |
Tue |
Wed |
Thu |
Fri |
|
Lecture |
|
9:30–10:50 |
|
||
|
Instructor
Office Hours |
|
|
9:00
- 10:00 CSE 3238 |
. |
|
| TA Office Hours |
11:00 - 12:00 CSE 3232 |
Staff 
- Instructor: Alin
Deutsch, deutsch at cs dot ucsd dot
edu, office CSE 3238
- TA: Rana Ralotibi
alotaib, at eng dot ucsd dot
edu
Prerequisites
- cse232A or instructor's
permission, granted only if the following
prerequisites are fulfilled
- Java (8B or 11 or
equivalent)
- SQL (132A or
equivalent)
Class
Project
You may team up with (at most) one partner for the class projects. Use the Piazza forum to advertise if you are looking for a partner.
Our
class project is the construction of an XQuery
processor. We consider a subset/modification of XML’s
data model, XQuery, and XQuery’s type system as
described in this
note. The processor receives an XQuery, parses it
into an abstract tree representation, optimizes it and
finally executes the optimized plan.
- Milestone 2 (Efficient Evaluation):
Implement a join operator as defined in Section 7 of
this note. Implement
an algorithm which detects the fact that the FOR and
WHERE clause computation can be implemented using
the join operator. You may assume that the input XQueries to be optimized are
in the simplified "Core" syntax given in the note.
No need to first normalize your queries to this
form.
To access XML files you can use the standard DOM
interface. There are a
number of XML DOM parser implementations.
The Java distribution includes one (see documentation here).
As an alternative, the Xerces-J project from Apache is
quite mature and stable.
The
W3C specification of DOM is here.
Test cases for project Phase I. For the data,
download Shakespeare's play, Julius Caesar, in XML
form (the associated DTD is here).
Queries can be found here.
Presentation Topics
Teams of two studens each will give a
20-minute talk in class, presenting a research paper
from the general field of XML-based data integration.
Here are a few suggestions (you are welcome to make
new ones after consulting with me).
- Minimization of XPath queries.
- Minimization
of Tree Pattern Queries. S. Amer-Yahia et al. []
- Efficient
Algorithms for Tree Pattern Minimization P.
Ramanan []
- More XPath Optimization
- XPath:
Looking Forward D. Olteanu
et al. []
- Processing of XML Streams.
- Processing
XML Streams with Deterministic Automata T.
Green et al. []
- Stream
Processing of XPath Queries with Predicates
A. Gupta et al. []
- Systems for publishing relational data
as XML
- Agora:
Living with XML and Relational I. Manolescu
et al. (a very short overview paper that goes
together with the next one) []
- Answering
XML Queries over Heterogeneous Data Sources
I. Manolescu et al. []
- XPERANTO:
Publishing Object-Relational Data as XML M.
Carey et al. []
- Querying
XML Views of Relational Data J. Shanmugasundaram et al. []
- Storing XML data in relations
- Storing
Semi-Structured Data With
STORED A. Deutsch et al. []
- Relational
Databases for Querying XML Documents:
Limitations and Opportunities J. Shanmugasundaram et. al []
- Efficient XML Query Processing
- On
supporting containment queries in relational
database management systems. C. Zhang et al.
[]
- Structural
joins: A primitive for efficient XML query
pattern matching. S. Al-Khalifa et. al []
- Storing
and querying ordered XML using a relational
database system. I. Tatarinov
et al. []
- Staircase
Join: Teach a Relational DBMS to Watch its
(Axis) Steps. T. Grust
et al. []
- Keyword Search in XML Documents
- TexQuery: a Full-Text
Search Extension to XQuery S. Amer-Yahia et al. []
Presentation
Schedule
Pick a slot here.
Time your presentations to last maximum
20 minutes in total (each presentation team member
covers about half of this time.)
Do not exceed this time, we want to allow
time for discussion, questions
and interruptions. Think of the
presentations as catalysts for (hopefully intense and
unruly) group discussions covering
both the material and the critique of the
presentation.
Grading
The
project constitutes 80% of the final grade, the
remaining 20% are earned for the presentation and class
participation.
Formal XPath Semantics note
A brief informal XQuery tutorial (much briefer and more readable than the W3C standard below)
Textbook material (from the warmly recommended textbook "Web Data Management"):
- XQuery Advanced Topics slides.
The complete XQuery and XML Schema documentation (the
WWW Consortium standards):
- XQuery
Data Model
- XQuery
- XQuery
Formal Semantics (“XQuery core”)
- XML
Schema