Difference between revisions of "Course: Advanced Databases"

From VistrailsWiki
Jump to navigation Jump to search
 
(11 intermediate revisions by the same user not shown)
Line 9: Line 9:


== News ==
== News ==
February 10th, 2014:
* Wiki is now up-to-date
* Wiki is now up-to-date
* Added research papers for reading assignment
* Added research papers for reading assignment
Line 17: Line 19:
Here is the list of selected papers for the reading assignment:
Here is the list of selected papers for the reading assignment:


# [http://gsl.azurewebsites.net/Portals/0/Users/dewitt/Papers/paralleldb/PDIS93.pdf DeWitt, D. J., Naughton, J. F., & Burger, J. (1993, January). Nested loops revisited. In Parallel and Distributed Information Systems, 1993., Proceedings of the Second International Conference on (pp. 230-242). IEEE.]
# [http://gsl.azurewebsites.net/Portals/0/Users/dewitt/Papers/paralleldb/PDIS93.pdf Nested loops revisited. D. J. DeWitt, J. F. Naughton, and J. Burger. 1993, January. In Proceedings of the Second International Conference on Parallel and Distributed Information Systems, (pp. 230-242).]
# [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.6493&rep=rep1&type=pdf G. N. Paulley and Per-Åke Larson. 1994. Exploiting Uniqueness in Query Optimization. In Proceedings of the Tenth International Conference on Data Engineering. IEEE Computer Society, Washington, DC, USA, 68-79.]
# [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.6493&rep=rep1&type=pdf Exploiting Uniqueness in Query Optimization. G. N. Paulley and Per-Åke Larson. 1994. In Proceedings of the Tenth International Conference on Data Engineering. IEEE Computer Society, Washington, DC, USA, 68-79.] (Assigned to Group 1)
# [http://www.researchgate.net/publication/2851695_Accelerating_XPath_Location_Steps/file/d912f50a27052d7d26.pdf Grust, Torsten. "Accelerating XPath location steps." Proceedings of the 2002 ACM SIGMOD international conference on Management of data. ACM, 2002.]
# [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.331.8616&rep=rep1&type=pdf Accelerating XPath location steps. Torsten Grust. Proceedings of the 2002 ACM SIGMOD international conference on Management of data.]
# [http://www.vldb.org/conf/2003/papers/S11P03.pdf A. Lerner and D. Shasha. AQuery: query language for ordered data, optimization techniques, and experiments. In Proc. Int. Conf. on Very Large Data Bases (VLDB), pages 345–356, 2003.]
# [http://www.vldb.org/conf/2003/papers/S11P03.pdf AQuery: query language for ordered data, optimization techniques, and experiments. A. Lerner and D. Shasha. In Proc. Int. Conf. on Very Large Data Bases (VLDB), pages 345–356, 2003.]
# [http://homepages.inf.ed.ac.uk/libkin/papers/sigmod96b.pdf Algorithms for deferred view maintenance. Latha Colby, Timothy Griffin, Leonid Libkin, Inderpal Mumick and Howard Trickey. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD'96), pages 469-480.]
# [http://homepages.inf.ed.ac.uk/libkin/papers/sigmod96b.pdf Algorithms for deferred view maintenance. Latha Colby, Timothy Griffin, Leonid Libkin, Inderpal Mumick and Howard Trickey. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD'96), pages 469-480.]
# [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.1999&rep=rep1&type=pdf Potamianos, Surajit Chaudhuri Ravi Krishnamurthy Spyros, and Kyuseok Shim. "Optimizing Queries with Materialized Views." Data Engineering 11 (1995): 190.]
# [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.1999&rep=rep1&type=pdf Optimizing Queries with Materialized Views. Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, and Kyuseok Shim. Data Engineering 11 (1995): 190.] (Assigned to group 6).
# [http://www.vldb.org/conf/2002/S17P02.pdf Popa, L., Velegrakis, Y., Hernández, M. A., Miller, R. J., & Fagin, R. (2002, August). Translating web data. In Proceedings of the 28th international conference on Very Large Data Bases (pp. 598-609). VLDB Endowment.]
# [http://www.vldb.org/conf/2002/S17P02.pdf Translating web data. L. Popa, Y. Velegrakis, M. A. Hernández, R. J. Miller, and R. Fagin. (In Proceedings of the 28th international conference on Very Large Data Bases (pp. 598-609). VLDB Endowment. August 2002. ] (Assigned Group 4).
# [http://ilpubs.stanford.edu:8090/262/1/1997-49.pdf Kossmann, Laura M. Haas Donald, and Edward L. Wimmers Jun Yangy. "Optimizing Queries across Diverse Data Sources." Proceedings of the... International Conference on Very Large Data Bases. Vol. 23. Morgan Kaufmann Pub, 1997.]
# [http://ilpubs.stanford.edu:8090/262/1/1997-49.pdf Optimizing Queries across Diverse Data Sources. Laura M. Haas, Donald Kossmann, Edward L. Wimmers and  Jun Yangy. Proceedings of the International Conference on Very Large Data Bases. Vol. 23. Morgan Kaufmann Pub, 1997.] (Assigned Group 3).
# [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.34.9263&rep=rep1&type=pdf Arocena, Gustavo O., and Alberto O. Mendelzon. "WebOQL: Restructuring documents, databases and webs." Data Engineering, 1998. Proceedings., 14th International Conference on. IEEE, 1998.]
# [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.34.9263&rep=rep1&type=pdf WebOQL: Restructuring documents, databases and webs. Gustavo O. Arocena, and Alberto O. Mendelzon. 14th International Conference on Data Engineering. IEEE, 1998.] (Assigned Group 2).
# [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.42.1232&rep=rep1&type=pdf Peter Buneman, Susan B. Davidson, Kyle Hart, G. Christian Overton, and Limsoon Wong. 1995. A Data Transformation System for Biological Data Sources. In Proceedings of the 21th International Conference on Very Large Data Bases (VLDB '95)]
# [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.42.1232&rep=rep1&type=pdf A Data Transformation System for Biological Data Sources. Peter Buneman, Susan B. Davidson, Kyle Hart, G. Christian Overton, and Limsoon Wong. 1995. In Proceedings of the 21th International Conference on Very Large Data Bases (VLDB '95)] (Assigned Group 7.).
# [http://www.ambuehler.ethz.ch/CDstore/www10/papers/pdf/p220.pdf Freire, Juliana, Bharat Kumar, and Daniel Lieuwen. "WebViews: accessing personalized web content and services." Proceedings of the 10th international conference on World Wide Web. ACM, 2001.]
# [http://www.ambuehler.ethz.ch/CDstore/www10/papers/pdf/p220.pdf WebViews: accessing personalized web content and services. Juliana Freire, Bharat Kumar, and Daniel Lieuwen. Proceedings of the 10th international conference on World Wide Web. ACM, 2001.]
# [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.30.2620&rep=rep1&type=pdf Using schema matching to simplify heterogeneous data translation. Tova Milo and Sagit Zohar. VLDB. Vol. 98. 1998.]


== Week 1: Tuesday Feb 4th - Course Overview ==
== Week 1: Tuesday February 4th - Course Overview ==


* Course overview and introduction
* Course overview and introduction
Line 48: Line 51:
* [http://en.wikipedia.org/wiki/Enterprise_Information_Integration Enterprise Information Integration (Wikipedia)]
* [http://en.wikipedia.org/wiki/Enterprise_Information_Integration Enterprise Information Integration (Wikipedia)]


== Week 2:  Tuesday February. 11th - Query Compilation 1 ==
== Week 2:  Tuesday February 11th - Query Compilation 1 ==


*  
* Query Compilation 1. Indexing and Storage
* Lecture notes:  
* Lecture notes:  
=== Assignment ===
* [[cs9223 Mapreduce Assignment]]
* This is an individual assignment. You may not collude with any other individual, or plagiarise their work.
For more details see http://cis.poly.edu/policies.
* You assignment is ''due on Sun Sept 29th''. '''Make sure you can login and access my.poly.edu!'''
* If you have questions about the assignment, we will hold office hours on Sept 23, 2013 from 2:30-3:30pm at 2 Metrotech, room 10.018


=== Required Reading ===
=== Required Reading ===
Line 66: Line 61:
* [http://research.google.com/archive/mapreduce.html original google map-reduce paper]
* [http://research.google.com/archive/mapreduce.html original google map-reduce paper]


== Week 3: Monday Sept. 23rd - Data Management for Big Data ==
== Week 3: Tuesday February 18th - Query Compilation 2 ==
 
* Databases and Big Data: Persistence, Querying, Indexing, Transactions
* Lecture notes: http://vgc.poly.edu/~juliana/courses/cs9223/Lectures/paralleldb-vs-hadoop.pdf
 
=== Related Topics ===
* BigTables and NoSQL stores. Tuple store vs. column stores: [http://hbase.apache.org/ HBase], [http://www.mongodb.org/ MongoDB], [http://cassandra.apache.org/ Cassandra]
* HBase book HBase: The Definitive Guide. Random Access to Your Planet-Size Data: http://shop.oreilly.com/product/0636920014348.do
* HBase book. Chapter 8 Architecture for information about transactional processing, WriteAhead Log notably, and how consistency is being maintained.
* Transactions in NoSQL stores. Google's percolator, [http://research.google.com/pubs/pub36726.html].
* "NewSQL" stores: more on [http://hive.apache.org/ Hive], [http://voltdb.com/ VoltDB], [http://db.cs.yale.edu/hadoopdb/hadoopdb.html HadoopDB],
* Beyond MapReduce: [http://spark-project.org/ Berkeley's Spark], [http://asterix.ics.uci.edu/ UC Irvine's Asterix], Google's [http://code.google.com/p/dremel/ Dremel]
 
=== Required Reading ===
* [http://cacm.acm.org/magazines/2010/1/55743-mapreduce-and-parallel-dbmss-friends-or-foes/fulltext PDMBS vs. MapReduce]
* http://cacm.acm.org/magazines/2010/1/55744-mapreduce-a-flexible-data-processing-tool/fulltext
* [http://www.cs.arizona.edu/~bkmoon/papers/sigmodrec11.pdf Parallel data processing with MapReduce: a survey. Lee et al, SIGMOD Record 2011]
* [http://database.cs.brown.edu/sigmod09/benchmarks-sigmod09.pdf Benchmark DBMS vs MapReduce (2009)]
 
=== Additional References ===
* http://www.computerworld.com/s/article/9224180/What_s_the_big_deal_about_Hadoop_
* [http://research.google.com/archive/bigtable.html Bigtable: A Distributed Storage System for Structured Data]
* [http://cs-www.cs.yale.edu/homes/dna/papers/hadoopdb.pdf HadoopDB: An Architectural Hybrid of MapReduce and DBMS Technologies for Analytical Workloads]
* [http://cs-www.cs.yale.edu/homes/dna/papers/hstore-cc.pdf Low Overhead Concurrency Control for Partitioned Main Memory Databases]
* [http://asterix.ics.uci.edu/pub/ASTERIX-DPD-2011.pdf ASTERIX: Towards a Scalable, Semistructured Data Platform for Evolving-World Models.]
* [http://research.google.com/pubs/pub36632.html Dremel: Interactive Analysis of Web-Scale Datasets]
* [http://research.google.com/pubs/pub36726.html Large-scale Incremental Processing Using Distributed Transactions and Notifications]
 
== Week 4:  Monday Sept 30th - ''Invited lecture by Dr. C. Mohan (IBM)'' ==
 
* '''Note that we will meet at a different location: NYU CUSP, 1 Metrotech Center, 19th floor'''
 
* Tutorial: An In-Depth Look at Modern Database Systems: http://bit.ly/CMnMDS
 
* Abstract: This tutorial is targeted at a broad set of database systems and applications people. It is intended to let the attendees better appreciate what is really behind the covers of many of the modern database systems (e.g., NoSQL and NewSQL systems), going beyond the hype associated with these open source and commercial systems. The capabilities and limitations of such systems will be addressed. Modern extensions to decades old relational DBMSs will also be described. Some application case studies will also be presented. An outline of problems for which no adequate solutions exist will be included. Such problems could be fertile grounds for new research work.
 
* Presenter: Dr. C. Mohan, IBM Fellow, IBM Almaden Research Center, San Jose, CA 95120, USA.
 
* Bio: Dr. C. Mohan has been an IBM researcher for 31 years in the information management area, impacting numerous IBM and non-IBM products, the research community and standards, especially with his invention of the ARIES family of locking and recovery algorithms, and the Presumed Abort commit protocol. This IBM, ACM and IEEE Fellow has also served as the IBM India Chief Scientist. In addition to receiving the ACM SIGMOD Innovation Award, the VLDB 10 Year Best Paper Award and numerous IBM awards, he has been elected to the US and Indian National Academies of Engineering, and has been named an IBM Master Inventor. This distinguished alumnus of IIT Madras received his PhD at the University of Texas at Austin. He is an inventor of 38 patents. He serves on the advisory board of IEEE Spectrum and on the IBM Software Group Architecture Board’s Council. More information can be found in his home page at http://bit.ly/CMohan
 
== Week 5: Monday Oct. 7th - Query Processing on Mapreduce and High-level Languages ==
 
* Pig Latin and Query Processing:
** [http://www.vistrails.org/images/1-RelationalOnMapReduce.pdf Relational processing over MapReduce]
** [http://www.vistrails.org/images/2-PigOnMapReduce.pdf Queries over MapReduce]
* In-class assignment
 
=== Required Reading ===
 
* [http://pages.cs.brandeis.edu/~olga/cs228/Reading%20List_files/piglatin.pdf Pig Latin: A Not-So-Foreign Language for Data Processing]
 
=== Additional References ===
 
* [http://www.mpi-inf.mpg.de/~rgemulla/publications/beyer11jaql.pdf Jaql: A Scripting Language for Large Scale Semistructured Data Analysis]
* [http://www.vldb.org/pvldb/2/vldb09-938.pdf Hive - A Warehousing Solution Over a Map-Reduce Framework]
 
== Week 6:  Mon Oct. 14th - Fall Break - No class ==
 
== Week 6:  Wed Oct. 16th - Fall Break - Make-up class ==
* Reproducibility and Data Exploration: http://vgc.poly.edu/~juliana/courses/cs9223/Lectures/reproducibility.pdf
* Large-scale information integration: http://vgc.poly.edu/~juliana/courses/cs9223/Lectures/web-information-integration.pdf
 
 
== Week 7:  Monday Oct. 21st - Invited Speaker: Alberto Lerner ==
 
* Inside MongoDB
 
== Week 8: Monday Oct 28th- Statistics is easy - Invited Speaker: Dennis Shasha ==
 
* Guest lecture by [http://cs.nyu.edu/shasha/ Dennis Shasha]:  [http://vgc.poly.edu/~juliana/courses/cs9223/Lectures/stateasy.pdf Statistics is Easy]
* Introduction to Provenance
 
=== Required Reading ===
* http://www.morganclaypool.com/doi/abs/10.2200/S00142ED1V01Y200807MAS001 -- book is available for free for NYU students
* Second edition of the book: http://www.morganclaypool.com/doi/pdf/10.2200/S00295ED1V01Y201009MAS008
 
 
* We will cover the material planned for "Week 10: Monday Nov. 11th": Finding Similar Items
 
== Week 9: Monday Nov. 4th  - Finding Similar Items, Information Integration ==
* Similarity: Applications, Measures and Efficiency considerations
** Lecture notes: http://vgc.poly.edu/~juliana/courses/cs9223/Lectures/similarity.pdf
* Similarity application: Information integration on the Web:
** Lecture notes: http://vgc.poly.edu/~juliana/courses/cs9223/Lectures/web-info-integration.pdf
* Homework presentation and demo
 
=== Required Reading ===
* [http://infolab.stanford.edu/~ullman/mmds/ch3.pdf Mining of Massive Datasets, chapter 3; information integration; entity resolution]
 
=== Homework Assignment ===
'''Due Nov 15th, 2013'''
Your assignment is in  http://www.newgradiance.com/services. Please see http://vgc.poly.edu/~juliana/courses/cs9223 for instructions on how to access this service.
 
== Week 10: Monday Nov. 11th  - MapReduce Algorithm Design ==
 
* Lecture notes: http://vgc.poly.edu/~juliana/courses/cs9223/Lectures/mapreduce-indexing-graph.pdf
 
=== Required Reading ===
 
* Chapters 3 and 4 in textbook: Data-Intensive Text Processing with MapReduce, by Lin and Dyer
 
=== Homework Assignment ===
'''Due Nov 15th, 2013'''
Your assignment is in  http://www.newgradiance.com/services. Please see http://vgc.poly.edu/~juliana/courses/cs9223 for instructions on how to access this service.
 
== Week 11: Monday Nov 18th- MapReduce Algorithm Design and Graph Processing ==
* Lecture notes: http://vgc.poly.edu/~juliana/courses/cs9223/Lectures/mapreduce-indexing-graph.pdf
 
=== Homework Assignment ===
Your Mapreduce/Pig assignment is available from Blackboard. '''It is Due December  1st'''.
 
 
=== Required Reading ===
* [http://lintool.github.com/MapReduceAlgorithms/MapReduce-book-final.pdf Data-Intensive Text Processing with MapReduce, Chapter 4 (Inverted Indexing for Text Retrieval) and 5(Graph Algorithms)]
 
=== Additional Reading ===
* [http://infolab.stanford.edu/pub/papers/google.pdf 1998 PageRank Paper]
* [http://infolab.stanford.edu/~ullman/mmds/ch5.pdf Mining of Massive Datasets, Chapter 5 (Link Analysis)]
* Pregel: A System for Large-Scale Graph Processing. Google. [http://kowshik.github.com/JPregel/pregel_paper.pdf]
 
== Week 12: Monday Nov. 25th - Large-Scale Visualization ==
 
* Invited lectures by:
** Dr. Lauro Lins (AT&T Research)
** Dr. Huy Vo (NYU Center for Urban Science and Progress)
 
* Lecture notes:
** https://www.dropbox.com/s/7t2vqryj5zgs44n/intro-to-visualization.pdf
** https://www.dropbox.com/s/btb3ocupkmpgefi/nanocubes.pdf
 
 
=== Required Reading ===
The Value of Visualization, Jarke Van Wijk
http://www.win.tue.nl/~vanwijk/vov.pdf
 
Tamara Munzner's Book draft 2 available online
http://www.cs.ubc.ca/~tmm/courses/533/book/
 
Nanocubes Paper
http://nanocubes.net
http://nanocubes.net/assets/pdf/nanocubes_paper_preprint.pdf
 
=== Additional Reading ===
imMens Paper (to contrast with nanocubes)
http://vis.stanford.edu/papers/immens
 
 
== Week 13: Monday Dec. 2nd - Frequent Itemsets ==
* Lecture notes: http://vgc.poly.edu/~juliana/courses/cs9223/Lectures/association-rules.pdf
 
=== Additional Reading ===
* Mining association rules between sets of items in large databases. Agrawal et al., SIGMOD 1993. http://www.almaden.ibm.com/cs/quest/papers/sigmod93.pdf
* Fast algorithms for mining association rules. Agrawal and Srikant, VLDB 1994. https://www.seas.upenn.edu/~jstoy/cis650/papers/Apriori.pdf
* An effective hash-based algorithm for mining association rules. Park et al., SIGMOD 1995. http://www.dmi.unict.it/~apulvirenti/agd/PCY95.pdf
 
=== Optional Quiz ===
'''Due Dec 9th'''
 
== Week 14: Monday Dec. 9th - - EM and exam review ==
 
* Lecture notes: http://vgc.poly.edu/~juliana/courses/cs9223/Lectures/hmm-em-mapreduce.pdf
 
=== Readings ===
 
Data-Intensive Text Processing with MapReduce, Chapter 6 (EM Algorithms for Text Processing)


== Week 15  Monday Dec. 16th -  Final Exam ==
* Query Compilation and Rewriting

Latest revision as of 17:27, 20 February 2014

NYU School of Engineering. CS6093: Spring 2014

Advanced Database Systems (CS6093) Syllabus for this semester: Syllabus (pdf)

This schedule is tentative and subject to change

Make sure to check my.poly.edu for course announcements

News

February 10th, 2014:

  • Wiki is now up-to-date
  • Added research papers for reading assignment
  • Added slides for lecture 1 & 2

Reading Assignment

Here is the list of selected papers for the reading assignment:

  1. Nested loops revisited. D. J. DeWitt, J. F. Naughton, and J. Burger. 1993, January. In Proceedings of the Second International Conference on Parallel and Distributed Information Systems, (pp. 230-242).
  2. Exploiting Uniqueness in Query Optimization. G. N. Paulley and Per-Åke Larson. 1994. In Proceedings of the Tenth International Conference on Data Engineering. IEEE Computer Society, Washington, DC, USA, 68-79. (Assigned to Group 1)
  3. Accelerating XPath location steps. Torsten Grust. Proceedings of the 2002 ACM SIGMOD international conference on Management of data.
  4. AQuery: query language for ordered data, optimization techniques, and experiments. A. Lerner and D. Shasha. In Proc. Int. Conf. on Very Large Data Bases (VLDB), pages 345–356, 2003.
  5. Algorithms for deferred view maintenance. Latha Colby, Timothy Griffin, Leonid Libkin, Inderpal Mumick and Howard Trickey. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD'96), pages 469-480.
  6. Optimizing Queries with Materialized Views. Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, and Kyuseok Shim. Data Engineering 11 (1995): 190. (Assigned to group 6).
  7. Translating web data. L. Popa, Y. Velegrakis, M. A. Hernández, R. J. Miller, and R. Fagin. (In Proceedings of the 28th international conference on Very Large Data Bases (pp. 598-609). VLDB Endowment. August 2002. (Assigned Group 4).
  8. Optimizing Queries across Diverse Data Sources. Laura M. Haas, Donald Kossmann, Edward L. Wimmers and Jun Yangy. Proceedings of the International Conference on Very Large Data Bases. Vol. 23. Morgan Kaufmann Pub, 1997. (Assigned Group 3).
  9. WebOQL: Restructuring documents, databases and webs. Gustavo O. Arocena, and Alberto O. Mendelzon. 14th International Conference on Data Engineering. IEEE, 1998. (Assigned Group 2).
  10. A Data Transformation System for Biological Data Sources. Peter Buneman, Susan B. Davidson, Kyle Hart, G. Christian Overton, and Limsoon Wong. 1995. In Proceedings of the 21th International Conference on Very Large Data Bases (VLDB '95) (Assigned Group 7.).
  11. WebViews: accessing personalized web content and services. Juliana Freire, Bharat Kumar, and Daniel Lieuwen. Proceedings of the 10th international conference on World Wide Web. ACM, 2001.
  12. Using schema matching to simplify heterogeneous data translation. Tova Milo and Sagit Zohar. VLDB. Vol. 98. 1998.

Week 1: Tuesday February 4th - Course Overview

Textbooks

Additional References

Week 2: Tuesday February 11th - Query Compilation 1

  • Query Compilation 1. Indexing and Storage
  • Lecture notes:

Required Reading

Week 3: Tuesday February 18th - Query Compilation 2

  • Query Compilation and Rewriting
Retrieved from "https://www.vistrails.org//index.php?title=Course:_Advanced_Databases&oldid=6920"