Princeton University Computer Science Dept.

Computer Science 597D Principles of Database and Information Systems Andrea LaPaugh

Fall 2013

• Class presentation slides (pdf): introduction
  
• Reading:
  
  • R&G Chapter 1.
  • Paolo Atzeni et. al., The relational model is dead, SQL is dead, and I don’t feel so good myself, SIGMOD Record, June 2013 (Vol. 42, No. 2).
    

• Class presentation slides (pdf): relational model
  
• Reading
• Codd, E.F., A Relational Model of Data for Large Shared Data Banks, Comm. ACM 13, 6 (June 1970), 377-387.  Codd gives a lot of detail that we will cover in the next few days using the development in R&G.   Read this seminal paper for the major new ideas.
  
• R&G Chapter 3, Sections 3.1 (skip 3.1.1)and 3.2.
• Assignment due:   bring your written answers to questions on Codd paper to class and prepare to discuss
  

• Class presentation slides (pdf): relational calculus
  
• Reading:
• R&G Chapter 4, Sections 4.1 and 4.3 except  4.3.2. 

• Class presentation slides (pdf):  relational algebra
  
• Reading:
• R&G Chapter 4, Section 4.2
• Codd reduction paper postponed until Wednesday
  

• Class presentation slides (pdf): SQL - final
  
• Reading:
• SKIM, do not read in detail:  E. F. Codd: Relational Completeness of Data Base Sublanguages (pdf on course Blackboard site). In: R. Rustin (ed.): Database Systems: 65-98, Prentice Hall and IBM Research Report RJ 987, San Jose, California : (1972). Focus on Section 4, which contains the proof. The goal is to get a high-level notion of the proof technique.
• R&G Chap. 3:  Sections 3.1.1, 3.4, 3.7, 3.8
• R&G Chap. 5:  Sections 5.1-5.6   This is a lot of reading, and you don't have to complete it for today.  Just get the idea.  There will be an exercise on SQL in a few weeks, and then you can use this reading as your reference for details.
• Assignment due:   bring your written answers to questions on Codd' reduction paper to class and prepare to discuss

• Class presentation slides (pdf): see Sept 25.
  
• Reading:
• R&G Chap. 5 sections as listed for Sept. 25.

• Class presentation slides (pdf): functional constraints and redundancy
  Reading:
• R&G Chap. 19: Sections 1-7 (orig. for Sept 30)
  
• Introduction to Information Retrieval, Preface,  Chapter 1, Section 2.4
• Assignment due:   Problems on relational query languages (pdf)
  

• Class presentation slides (pdf): information retrieval - final
  
• Reading:
• Introduction to Information Retrieval Chapter 6: Sections 6.2 and 6.3; Chapter 21: Sections 21.1 and 21.2.  (Section 21.3 optional but recommended if you are interested in link analysis.)
  

• Class presentation slides (pdf):  see final version under Oct. 7
  
• Reading:  The papers below present many aspects of their respective storage systems, focusing on the distributed nature of the stores and the ability to scale.  At this point we only want to discuss the data models and why these models matches well with information retrieval and other Web applications.   Therefore, I have only assigned the portions of the papers that address these.  We will come back to the rest of the sections of the papers when we discuss distributed storage and consistency.
• Chang et. al.,  Bigtable: A Distributed Storage System for Structured Data, ACM Trans. on Computer Systems, Vol. 26(2),  June 2008.  (Earlier version in USENEX Symp. on Operating Systems Design and Implementation (OSDI), 2006.)  Read Sections 1, 2, 3, 8, and 11.
  
• Lakshman and Malik, Cassandra - A Decentralized Structured Storage System (pdf on course Blackboard site), SIGOPS Operating Systems Review, V44(2), April 2010.  Read Sections 1, 2, 3, 4 and 6.1
• Borthakur et. al.,   Apache Hadoop Goes Realtime at Facebook, Proc. ACM SIGMOD Intern. Conf. on Management of Data (SIGMOD '11), ACM, 2011, pgs 1071-1080.  Read Sections 1, 2, 3.

• Assignment due:   bring your written answers to questions on paper to class and prepare to discuss

• Class presentation slides (pdf): file organization and indexing
  
• Reading:
• R&G Chap 8 Sections 1-3
  
• R&G Chap 9, Section 1
• R&G Chap 10, Sections 1-6

• Class presentation slides (pdf): dynamic indexing
• Reading:
• R&G Chap 10, Sections 7, 8
• R&G Chap 11, Sections 1, 2

• Class presentation slides (pdf): transactions
  
• Reading  (Note for this class, the reading need not be done before class):
• R&G Chap 16, Sections 1-5
  
• R&G Chap 17 Sections 1-4
  

• Reading: 
  
• Ghemawat et. al.,  The Google File System, Proc. ACM Sym. on Operating Systems Principles (SOSP'03), ACM, 2003, pgs. 29-43.  Read Sections 1, 2.1 thru 2.6, 3.1, 3.2, 4.2, 4.3.
  
• Chang et. al.,  Bigtable: A Distributed Storage System for Structured Data, ACM Trans. on Computer Systems, Vol. 26(2),  June 2008.  (Earlier version in USENEX Symp. on Operating Systems Design and Implementation (OSDI), 2006.)  Read Sections 4, 5 except 5.2, and in 6 the subsections "Locality groups" and "Bloom filters".
  
• Lakshman and Malik, Cassandra - A Decentralized Structured Storage System (pdf on course Blackboard site), SIGOPS Operating Systems Review, V44(2), April 2010.  Read Section 5 Intro, 5.1, 5.2, 5.5, 5.6 and last paragraph of 5.7.
  
• Assignment due: bring your written answers to questions on papers to class and prepare to discuss  

• Class presentation slides (pdf): crash recovery
  
• Reading:
• R&G Chap 16, Section 7
  
• R&G Chap 18

• Reading:
• Eric Brewer, CAP Twelve Years Later:  How the "Rules" Have Changed, Computer,  IEEE, Vol. 45(2), February 2012, pgs 23-29.
  
• Ghemawat et. al.,  The Google File System, Proc. ACM Sym. on Operating Systems Principles (SOSP'03), ACM, 2003, pgs. 29-43.  Read Sections 2.7 and 5.1.
  
• Chang et. al.,  Bigtable: A Distributed Storage System for Structured Data, ACM Trans. on Computer Systems, Vol. 26(2),  June 2008.  (Earlier version in USENEX Symp. on Operating Systems Design and Implementation (OSDI), 2006.)  Read Section 5.2 and in 6 the subsection "Exploiting immutability".
  
• Lakshman and Malik, Cassandra - A Decentralized Structured Storage System (pdf on course Blackboard site), SIGOPS Operating Systems Review, V44(2), April 2010.  Read Section 5.3, 5.4 and 5.7.
• Assignment due:   bring your written answers to questions on paper to class and prepare to discuss

• Class presentation slides (pdf): single operation queries
• Reading:
• R&G Chapter 12, Sections 1-3
  
• R&G Chapter 13, Sections1-3
• R&G Chapter 14, Section 4
  

• Class presentation slides (pdf): query optimization,  example on board (pdf)
  
• Reading: 
• R&G Chapter 12, Sections 4-6
• R&G Chapter 14, rest of chapter (Section 4 assigned for Monday)
• R&G Chapter 15, Section 2 up to "Improved Statistics: Histograms"
  

• Class presentation slides (pdf):  cluster computing
  
• Reading:
•   In  Rajaraman, Anand; Leskovec, Jure; Ullman,  Jeffrey D,  Mining of Massive Data Sets, Cambridge University Press. 2011.  (You can download a pdf file of the latest version of the book - July 2013 as of this writing):
• Chapter 2: Introduction thru 2.3 and 2.5, skipping 2.3.3 thru 2.3.6  (but note the notation for grouping and aggregation in 2.3.3)

• Class presentation slides (pdf): see Nov. 25
  
• Reading:
• Daniel Peng and Frank Dabek, Large-scale Incremental Processing Using Distributed Transactions and Notifications(pdf),  in 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI '10), 2010.
• R&G Chapter 27, Sections 6 and 7.
  
• (If interested, a more thorough presentation can be found in Silberschatz et. al. Chapter 23,  Sections 1-4 and 7)
• Assignment due: bring your written answers to questions on paper to class and prepare to discuss  
  

• Class presentation slides (pdf): XML
  
• Reading:
• Taranov et. al., Sedna: Native XML Database Management System (Internals Overview), Proc. SIGMOD Intern. Conf. on Management of Data (SIGMOD'10), ACM, 2010, pgs 1037-1046.
  
• R&G Chapter 27, Section 8.2. 
• Assignments due: 
• today bring your written answers to questions on paper to class and prepare to discuss
  
• any time between today and last day of classes:   Xquery exercises

• Reading for Taylor's presentation:
  
• Al-Jaroodi, J., Mohamed, N., & Nuaimi, K. A. An Efficient Algorithm for Temporal Financial Information Monitoring (read using Adobe Reader).  2013 International Conference on High Performance Computing and Simulation (HPCS), 2013, pgs 115-122.
• Casas, C. Tactical Asset Allocation: An Artificial Neural Network Based Model. International Joint Conference on Neural Networks, 2001. Proceedings IJCNN '01, Vol. 3, pgs 1811-1816.
• Reading for Santiago's presentation:
• Acar, Belloch, and Harper, Adaptive Functional Programming, ACM Transactions on Programming Languages and Systems, Vol. 28, No. 6, November 2006, Pages 990–1034. 
• JS Foster et. al., Adapton: Composable, Demand-Driven Incremental Computation (pdf), draft, November 2013.

• Beginning of window in which to have project progress discussion with Prof. LaPaugh
  (see Project Page)

• Reading for Santiago's presentation:
• Suciu, D., Olteanu, D., Ré, C., and Koch, C. Probabilistic Databases. Morgan & Claypool, 2011.  Chapter 1 only (pp. 1-15).  Free download from the Princeton network.
• Reading for Anand's presentation:
•  Güting, Ralf Hartmut. "GraphDB: Modeling and querying graphs in databases." (pdf) VLDB. Vol. 94. 1994.
• For those interested, information on Neo4j can be found in the Neo4j manual.
  

• End of window in which to have project progress discussion with Prof. LaPaugh
  (see Project Page)

• Reading for Max's presentation:
• Sameer Agarwal, Barzan Mozafari, Aurojit Panda, Henry Milner, Samuel Madden, Ion Stoica. BlinkDB: Queries with Bounded Errors and Bounded Response Times on Very Large Data (pdf). In ACM EuroSys 2013.
  
• Sameer Agarwal, Aurojit Panda, Barzan Mozafari, Anand P. Iyer, Samuel Madden, Ion Stoica. Blink and It’s Done: Interactive Queries on Very Large Data (pdf). In PVLDB 5(12): 1902-1905, 2012.    2013 paper contains this content.
  
• Reading for Michael's presentation:
• Robbert van Renesse, Dan Mihai Dumitriu, Valient Gough, and Chris Thomas. Efficient reconciliation and flow control for anti-entropy protocols (pdf). In Proceedings of the 2nd Large Scale Distributed Systems and Middleware Workshop (LADIS ’08), New York, NY, USA, 2008. ACM.

Wed. Dec. 11: Ruth Dannenfelser presents;  wrap-up

• Class presentation slides (pdf): final summary
  Reading for Ruth's presentation: 
• Sadilek, Adam, Henry A. Kautz, and Vincent Silenzio.  Modeling Spread of Disease from Social Interactions (pdf) ICWSM. 2012.

IMPORTANT CHANGE

* on reserve in the Engineering Library