Advanced Database Systems (Sensor Network Databases)
Organizer
Lecturers
News
- The slides concerning the exam structure from the Q&A session are now available
- The exam information below has been updated. Please make sure to read the information carefully.
- The mailing list has been created. We have subscribed all the email addresses collected in the lecture
(but unfortunately some of them failed for readability reasons). Please check if you have been subscribed
and, if not, subscribe manually.
The mailing list works as follows
- To subscribe, send an empty mail to adbis09-request@informatik.uni-freiburg.de with subject subscribe.
- To unsubscribe, send an empty mail to adbis09-request@informatik.uni-freiburg.de with subject unsubscribe.
- To send a mail to the list (once you are subscribed), send a mail to adbis09@informatik.uni-freiburg.de.
Exam Information (updated!)
Due to various requests, we have again changed the regularities for the exam. Here is the final plan:- As announced before, bachelor students must take an oral exam (due to restrictions imposed by the examination office). This oral exam will take place on Mo, 08 Mar 2010; the time and location will be announced soon.
- For all non-bachelor students, we will offer a written exam (so, if you are not a bachelor student, you'll have to take the written exam). The following slides contain some more information on the structure of the exam. Each student must pick exactly one out of the following two dates:
- Mo, 22 Feb 2010 (2pm s.t., Building 101, HS 00-026)
- Mo, 08 Mar 2010 (2pm s.t., Buildling 51, HS 00-006)
Important: Please verify that you have registered for the ADBIS course with the HIS-LSF system (the registration system will open soon). If you are not registered, we cannot accept your participation in the exam.
Content
The lecture covers basic properties of distributed database systems, sensor network datatabase systems, and mobile databases. It gives insights into concepts and theory behind distributed systems, such as process synchronisation, data consistency, data replication, and fault tolerance. Beyond distributed databases, we provide an introduction into advanced database techniques such as in-network query processing, data stream processing, and probabilistic databases.
Time, Location, and Organisation
Location:
- Lecture and Standard Exercises: Building 51, Room 00-006
- Lab Exercises: Building 82, Room 00-029 (CIP-Pool)
Time:
- Monday, 2pm-4pm
- Wednesday, 2pm-4pm
Language: English
Mode: 2hrs lecture + 1hr exercise + 1 hr lab exercise per week (see the tentative time table).
ECTS: 6 Points
Program of Study:: Master CS and Applied CS
Qualification: There will be both practical and theoretical assignments (see below for more information). In addition, there will be a written exam at the end of the semester (except for bachelor students, which must take an oral exam).
Exercises
The exercise session consists of programming assignments (lab exercises) and theoretical assignments in form of exercise sheets. The active participation in the exercise sessions is mandatory, which means that your presence in the exercise sessions is required. You are allowed to miss at most one exercise session without an official excuse (such as a medical certificate); if you miss more than one exercise session, you will be disqualified for the final exam. More information are available in the following slides.The progamming assignments will cover the first part of the lecture (i.e, Stream Processing); this project will take place before christmas. In addition there will be a programming project related to the last part of the lecture (i.e., Distributed Systems). More information can be found on the tentative time table. The remaining three parts of the lecture, Incomplete Information and Probabilistic Databases, In-Network Query Processing, and Sensor Network Databases will be accompanied by exercise sheets; the submission of these exercise sheets is voluntary.
You must successfully solve all programming assignments to qualify for the final exam. In case you solve all practical assignments in time, you will receive a 0.3 grade bonus for the final exam. If you do not succeed in time, you can hand in the solutions for the practical assignments later, until February 14, 23.59:59 (followed by a successful personal demonstration in the days after the submission) to get the qualification for the final exam.
Literature:
- Part I: Stream Processing
- Dan Olteanu, Holger Meuss, Tim Furche, Francois Bry: XPath Looking Forward. In Proc. EDBT 2002, Workshop on XML-based Data Management.
- Todd J. Green , Gerome Miklau, Makoto Onizuka, Dan Suciu: Processing XML Streams with Deterministic Automata. In ACM Transactions on Database Systems, 2004.
- Stefanie Scherzinger: Bulk data in Main Memory-based XQuery Evaluation. In Proc. XIME-P 2007.
- Amelie Marian, Jerome Simeon: Projecting XML documents. In Proc. VLDB, 2003.
- Irina Botan, Donald Kossmann, Peter M. Fischer, Tim Kraska, Dana Florescu, Rokas Tamosevicius: Extending XQuery with Window Functions. In Proc. VLDB 2007.
- Part II: Incomplete Information and Probabilistic Databases
- Book Chapter 19 on Incomplete Information in the book:
Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases
(you can download the book here). - Tomasz Imielinski, Witold Lipski: Incomplete Information in Relational Databases. In Journal of the Association for Computing Machinery, 1994.
- Serge Abiteboul, Paris Kanellakis, Gösta Grahne: On the Representation and Querying of Sets of Possible Worlds. In Journal of Theor. Comp. Sci., 1991.
- Nilesh Dalvi, Dan Suciu: Efficient Query Evaluation on Probabilistic Databases. In VLDB Journal, 2007.
- Dan Olteanu, Jiewen Huang: Using OBDDs for Efficient Query Evaluation on Probabilistic Databases. In Proc. SUM, 2008.
- Dan Olteanu, Jiewen Huang, Christoph Koch: SPROUT: Lazy vs. Eager Plans for Tuple-Independent Probabilistic Databases. In Proc. ICDE, 2009.
- Part III: In-Network Query Processing
- Chapter 6 of Feng Zhao and Leonidas Guibas, Wireless Sensor Networks: An Information Processing Approach. Morgan Kaufmann (ISBN 1-55860-914-8), 2004.
- The Design and Evaluation of a Query Processing Architecture for Sensor Networks, UC Berkeley Ph.D. Thesis , 2003, Samuel Madden
- TAG: a Tiny AGgregation Service for Ad-Hoc Sensor Networks, Proceedings of OSDI , 2002 Samuel Madden, Michael Franklin, Joseph Hellerstein, and Wei Hong
- Part IV: Sensor Databases
- Joseph Hellerstein, Wei Hong, Samuel Madden, and Kyle Stanek. Beyond Average: Towards Sophisticated Sensing with Queries. In Proceedings of IPSN, 2003.
- Suman Nath, Phillip B. Gibbons, Zachary Anderson, and Srinivasan Seshan, Synopsis Diffusion for Robust Aggregation in Sensor Networks". In proceedings of ACM SenSys'04.
- Jeffrey Considine, Feifei Li, George Kollios and John Byers, Approximate Aggregation Techniques for Sensor Databases, Proc. ICDE 2004.
- Sylvia Ratnasamy, Brad Karp, Li Yin, Fang Yu, Deborah Estrin, Ramesh Govindan, Scott Shenker: GHT: a geographic hash table for data-centric storage. WSNA 2002: 78-87
- Brad Karp, H. T. Kung: GPSR: greedy perimeter stateless routing for wireless networks. MOBICOM 2000: 243-254
- Part V: Distributed Systems
- A. S. Tanenbaum, M. Van Stehen. Distributed Systems: Principles and Paradigms (2nd Ed.). Pearson International Edition, 2007.