CSE291 Spring 2001, Query Processing: Beyond SQL Systems

Resident guest lecturer: Victor Vianu

More talks by Bertram Ludascher and Vagelis Hristidis

Time & Place: Monday 11:30AM – 2:00PM @ APM 4218, unless otherwise announced (see below).

Prerequisites: CSE132A, CSE232A or equivalent courses that provide knowledge of schema design, SQL, relational algebra, and the essentials of query processing.

Grading Scheme: Grading will be based on class participation and (primarily) on the quality of a lecture that the student will prepare and give during one of the last meetings of the class. The lecture will be based on one or more papers, whose number is dependent on the number of units that the student has signed up for. For example,

· if you sign up for one unit you may choose to study the XML Query Algebra and present a lecture with title “Type Inference for XML Query Algebra expressions”. We will have covered during the class type inference for XML queries (Apr 16) and we will have described properties of the inferred type, such as tightness. Your task will be to present type inference for queries expressed in XML query algebra. Present the algorithms in a way that will be precise and easily understood to the audience. Draw the parallels with view inference as discussed in class and comment on, say, tightness.

If you sign up for four units you may choose to present a study of Complex Value, Object-Oriented and XML Query algebras and address issues of expressiveness (what can an algebra do that others don’t?), appropriateness for implementation (can we use a particular algebra easily as part of the basic architectures we’ll present in class? Why? Why not?)

The difference between the 1 and 4-unit projects is that in the first case the questions you are asked to answer are very concrete and straightforward. In the second case, your comments and lecture are more open-ended and it largely depends on you to produce an interesting talk. And, of course, the reading load is smaller in the case of the 1-unit.

Textbook: We strongly recommend “Data on the Web: From Relations to Semistructured Data and XML” by Abiteboul, Buneman, Suciu. Published by Morgan-Kauffman, ISBN 1-55860-622-X.

Lecture List:

[Apr 9] Introduction to the course and its theme. Introduction to XML and the XQuery query language. Reading material:

Victor Vianu A Web Odyssey: From Codd to XML (pdf); PODS 2001.
L. Gravano, Y. Papakonstantinou "Mediating and Metasearching on the Internet" ( ps) In Data Engineering Bulletin 21(2), 1998.
Extensible Markup Language (XML) 1.0 (Second Edition); W3C Recommendation, 6 October 2000.
XQuery: A Query Language for XML, W3C Working Draft, 15 February 2001.

[Apr 13] More on query and transformation languages for XML.

1. Structural recursion using XSLT (by Bertram Ludascher)

2. Skolems and information fusion using XML-QL and MSL

3. Visual Paradigms for XML Querying

Reading material:

1. XSL Transormations, Version 1.1, W3C Working Draft, 12 December 2000.

2. A. Deutch etal. “A Query Language for XML”; W3C Technical Report.

3. K. Munroe, Y. Papakonstantinou " BBQ: A Visual Interface for Browsing and Querying XML". ( ps) In Visual Database Systems (VDB) 2000

4. M. Petropoulos, V. Vassalos, Y. Papakonstantinou “ XML Query Forms (XQForms): Declarative Specificationof XML Query Interfaces” ( pdf). In WWW 10, 2001

[Apr 16] Type checking and type inference for XML Queries (by Victor Vianu). Reading material:

1. Y. Papakonstantinou and V. Vianu; “DTD Inference for Views of XML Data” (pdf); PODS 2000.

2. T. Milo, D. Suciu and V. Vianu; “Typechecking XML Transformers” (pdf,postcript); PODS 2000.

[Apr 23] An XML Query Processor Architecture for Databases and Mediators

1. B. Ludascher, Y. Papakonstantinou, P. Velikhov "Navigation-Driven Evaluation of Virtual Mediated Views (pdf)". ( ps). In EDBT 2000.

2. “A Physical-Level Algebra for XML Queries”; Technical Report in preparation.

[Apr 30] The April 30 lecture will be moved to May 2^nd, same time, place to be announced.
[May 2] Wrapping sources and Query processing in the presence of limited capabilities. Practical architectures. Reading material:

1. Laura Haas, etal “Optimizing Queries Across Heterogeneous Data Sources”; VLDB 97.

[May 7] Answering Queries Using Views and Capabilities-Based Rewriting (by V. Vassalos)

Reading material:

1. A. Levy “Answering Queries Using Views: A Survey”

2. V. Vassalos, Y. Papakonstantinou "Expressive Capabilities Description Languages and Query Rewriting Algorithms" (ps) In Journal of Logic Programming.

[May 14] Keyword queries, Ranked queries on relational and semistructured databases.

1. Ranked Queries on Multiparametric Objects (by Vagelis Hristidis)

2. Keyword Search on Relational and Semistructured Databases

Reading Material:

1. V. Hristidis, N. Koudas, Y. Papakonstantinou “PREFER: A System for the Efficient Execution of Multi-Parametric Ranked Queries (pdf)”; SIGMOD 2001.

2. R. Goldman, N. Shivakumar, S. Venkatasubramanian, and H. Garcia-Molina. “Proximity Search in Databases”. VLDB 1998. (ps) (pdf)

[May 21] First set of student presentations.
[May 28, Memorial Day, Rescheduled for May 30] Representing and Querying XML with Incomplete Information (by Victor Vianu). Depending on schedule, student lectures as well. Reading material:

1. S. Abiteboul, L. Segoufin and V. Vianu: “Representing and Querying XML with Incomplete Information” (pdf), PODS 2001.

[Jun 4] Second set of student presentations.
[Jun 11] Deadline for submission of presentation material. No class meeting.

Topics List:

Query Processing Optimization Issues for Mediators on Relational Database Sources (2 units)
Type Checking and Inference (3 units)

1. Type checking for XML Views with datavalues

2. Typechecking XML views of relational databases (lics 01)

Ranked Queries and Metasearchers (flexible, 1-3 units)
Object-Oriented Algebras and XML Algebras (flexible, 2-4 units)
Mediating on Sources With Limited Interfaces (1-3 units)

New topics on the topic list will be annotated with NEW and taken topics will be annotated with the name of the student of team of students who has taken over.