CIS 650: Data Sharing and the Web

Spring 2003

Instructor:  Zachary Ives, zives@cis.upenn.edu, 562 Moore-GRW
Location:  Towne 321
Times:  MW 4:30-6PM
Office Hours: Thursday 2:00-3:00PM or by appointment

Objectives

The goals of this course are to gain a better understanding of the issues of querying, integrating, and otherwise sharing data across the Internet and the World-Wide Web. Data integration is perhaps the best-studied instance of this problem, and we focus on it for much of the semester.  We begin with a study of relational query processing as a foundation, and then move on to answering queries using views and adaptive query processing.

We also examine architectures for larger-scale or richer data exchange:  wide-area data sharing (as proposed by projects such as Mariposa in the 1990s and Piazza today) and sharing with very expressive data definition formalisms (the Semantic Web).

Finally, we hope to investigate several efforts to support data exchange scenarios that are not merely query-driven:  publish-subscribe, groupware applications, collaborative web sites (such as Sourceforge.net), and versioning-based systems.

Format

The goal of this course is to give a strong understanding of the research issues in the area of focus, but also to stimulate discussion and interaction and build presentation skills. Some topics that involve a great deal of background knowledge will be covered in standard lectures, but there will also be a mix of student-led presentations and project presentations.  I expect each student to prepare for and lead a paper discussion, in consultation with me.  Moreover, each student will be expected to write and post a short analysis of the assigned papers for each lecture.

There will be a term project, which can either be a survey and analysis paper or an implementation of a novel idea or system. During the last week, there will be a take-home final exam.

Topics and Readings

For each week's readings, a 1-page report posted to the upenn.cis.cis650 newsgroup, is due by NOON, 12:00:00PM, the day the paper is to be discussed in class. Any submission made after this deadline is considered LATE and will receive a 30% point deduction. You may miss one review over the course of the semester.

Data Integration Overview and Introduction

• Garcia-Molina et al.  The TSIMMIS Approach to Mediation: Data Models and Languages.  JIIS 8(2).
• Levy et al.  Querying Heterogeneous Information Sources Using Source Descriptions. VLDB 1996.
  Additional papers discussed in lecture:
  • Haas et al.  Optimizing Queries Across Diverse Data Sources. VLDB 1997.
  • Chandrasekaran et al.  TelegraphCQ: Continuous Dataflow Processing for an Uncertain World
  . CIDR 2003.

Data Sharing across the Wide Area

• Stonebraker et al. Mariposa: A Wide-Area Distributed Database System. VLDB Journal 5(1).
• Gribble et al.  What Can Databases Do for Peer-to-Peer?  WebDB 2001.

Query Optimization Basics

• Selinger et al. Access Path Selection in a Database Management System.  SIGMOD 1979.
• Graefe & McKenna.  The Volcano Optimizer Generator:  Extensibility and Efficient Search.  ICDE 1993.
  Suggested background reading:
  • Graefe & DeWitt.  The EXODUS Optimizer Generator.  SIGMOD 1987.
  
  Additional papers covered in lecture:
  • Haas et al.  Extensible Query Processing in Starburst.  SIGMOD 1989.

Query Execution Basics

• Graefe.  Query Evaluation Techniques for Large Databases. ACM Computing Surveys, 1993. (portions assigned)

Adaptive Query Processing

• Kabra & DeWitt. Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans.  SIGMOD 1998.
• Ives et al.  An Adaptive Query Execution System for Data Integration.  SIGMOD 1999.
• Avnur & Hellerstein.  Eddies:  Continuously Adaptive Query Processing.  SIGMOD 2000.
• Bruno & Chaudhuri.  Exploiting Statistics on Query Expressions for Optimization.  SIGMOD 2002.

Querying the Web

• Florescu et al.  Integrating Keyword Search into XML Query Processing. WWW9.
• Cohen. Integration of Heterogeneous Databases Without Common Domains Using Queries Based on Textual Similarity. SIGMOD 1998.
• Christos Faloutsos and Douglas W. Oard. A Survey of Information Retrieval and Filtering Methods. Technical Report, University of Maryland, 1995.
  For review/reference: 
  • XQuery spec.

XML Processing

• Ives et al.  An XML Query Engine for Network-Bound Data. VLDB Journal, 2002.
• Altinel & Franklin.  Efficient Filtering of XML Documents for Selective Dissemination of Information. VLDB 2000.
• For additional depth:  Ludaescher et al. A Transducer-Based XML Query Processor. VLDB 2002.

Answering Queries Using Views

• Halevy.  Answering queries using views: A survey.  VLDB Journal 10(4).
• Halevy et al.  Schema Mediation in a Peer Data Management System.  ICDE 2003.

Versioning, Diffs, and Updates

• Chawathe & Garcia-Molina.  Meaningful Change Detection in Structured Data.  SIGMOD 97.
• Ghandeharizadeh et al. Heraclitus: Elevating Deltas to be First-Class Citizens in a Database Programming Language.  TODS 21(3).
• Harmony/Unison  (if possible: guest lecture by project member)

Alternative Data Sharing Paradigms

• Berners-Lee et al. The Semantic Web.  Scientific American, May 17, 2001.
• Decker et al.  The Semantic Web: On the Roles of XML and RDF. IEEE Internet Computing.
• Halevy et al.  Piazza: Data Management Infrastructure for Semantic Web Applications. Submission to WWW 2003.
• Study of:  Groove, Lotus Notes; Slashdot, Sourceforge, competitors

Reading Papers and Writing Reviews

Here are some things to consider every time you read a paper and write an analysis/review:

• What is the goal of the paper?
• What are the main 2 or 3 contributions of this paper?
• How well does the paper meet its goals? How convincing is it?
• What are the strengths and weaknesses of the paper?
• What was confusing about the paper?
• How does the paper relate to other research done in the same area? To the topic of this seminar?

Take notes or scribble in the margins while you read. Don't expect that you'll get everything out of a single read; you may have to come back to certain parts several times. If you start getting bogged down in too many details in a section of the paper, sometimes it's helpful to take a step back and try to figure out what the authors are trying to do in that section.

Also, after you've figured out the main points of your review, it may be interesting and educational to see what other people have said. Feel free to respond to other people's comments -- that's why this is an open forum.

I will try to read all of the (on-time) reviews before the evening's class, and to address any points of confusion or bring up points of debate.

Grading

The grading breakdown will tentatively be as follows:

• Class participation 10%
• Paper reviews/analysis 20%
• Class presentation 10%
• Term project 40%
• Final exam 20%

You may miss one paper review without penalty. Any review posted after 12:00 noon on the day it is due is LATE, and it will receive a 30% point deduction.

Tentative Schedule

Papers highlighted in GREEN are papers that are presented by a student. Papers highlighted in BLUE will be presented by myself or a guest lecturer.

Significant Dates

• Jan 13th:  Classes begin
• Jan 20th:  MLK Jr. holiday
• Jan 24th:  Add period ends
• Feb 14th:  Drop period ends
• March 10th-14th:  Spring break
• April 25th:  End of Spring classes
• May 1-9:  Final exams