CMSC724: Database Management Systems

CMSC724: Database Management Systems
Prof. Amol Deshpande; CSIC 2120; Tue-Thur 11:00am-12:15pm

[Home]	[Schedule]	[Assignments]	[Resources]	[Announcements/Updates]

For each of the required papers, a critique must be submitted by 8:00am the day of the class. More below.

The posted slides may be from last time (annotated "spring 2009"), and I will post the updated slides before the class.

Schedule

Jan 25: Introduction/Overview [slides]
- Today's discussion of history was partly from the first paper ("Evolution of ..") in this ACM Computing Surveys, Mach 1976
- Lecture Recording
Jan 27: History/Data Modeling [slides], [modeling text notes]
- (summary required) "A Relational Model of Data for Large Shared Data Banks". E. F. Codd. Commun. ACM 13(6): 377-387 (1970). [pdf]
  [show details]
  Abstract:
  Future users of large data banks must be protected from having to know how the data is organized in the machine (the internal representation). A prompting service which supplies such information is not a satisfactory solution. Activities of users at terminals and most application programs should remain unaffected when the internal representation of data is changed and even when some aspects of the external representation are changed. Changes in data representation will often be needed as a result of changes in query, update, and report traffic and natural growth in the types of stored information. Existing noninferential, formatted data systems provide users with tree-structured files or slightly more general network models of the data. In Section 1, inadequacies of these models are discussed. A model based on n-ary relations, a normal form for data base relations, and the concept of a universal data sublanguage are introduced. In Section 2, certain operations on relations (other than logical inference) are discussed and applied to the problems of redundancy and consistency in the user's model.
  
  Think about:
  Codd's paper was prescient and foreshadowed many developments in the relational model. How did the operators he define compare to the relational algebra operators of today (especially see his definition of "join")? "Connection Trap" is interesting concept, and somewhat subtle. Cood had beginnings of the idea of "normal forms" (he only defines 1NF though); but weak redundancy was one notion that did not lead anywhere.
- (required reading - no summary) "What goes around comes around"; Mike Stonebraker and Joe Hellerstein; Redbook.
- (background/reference) Database System Concepts; Avi Silberschatz, Henry F. Korth, S. Sudarshan. Two Appendixes
  covering network model and hierarchical model in detail are available on the book webpage. [link]
- (background/reference) The Relational vs Network Models Debate
- (background/reference) Is your database relational ? Ted Codd Wikiepdia article
Feb 1: History/Data Modeling (Continued from above) [normalization overview slides]
- (summary required) "Querying semi-structured data". Serge Abiteboul. ICDT 1997. [pdf]
  [show details]
  Abstract:
  The amount of data of all kinds available electronically has increased dramatically in recent years. The data resides in different forms, ranging from unstructured data in file systems to highly structured in relational database systems. Data is accessible through a variety of interfaces including Web browsers, database query languages, application-specific interfaces, or data exchange formats. Some of this data is raw data, e.g., images or sound. Some of it has structure even if the structure is often implicit, and not as rigid or regular as that found in standard database systems. Sometimes the structure exists but has to be extracted from the data. Sometimes also it exists but we prefer to ignore it for certain purposes such as browsing. We call here semi-structured data this data that is (from a particular viewpoint) neither raw data nor strictly typed, i.e., not table-oriented as in a relational model or sorted-graph as in object databases. As will seen later when the notion of semi-structured data is more precisely defined, the need for semi-structured data arises naturally in the context of data integration, even when the data sources are themselves well-structured. Although data integration is an old topic, the need to integrate a wider variety of dataformats (e.g., SGML or ASN.1 data) and data found on the Web has brought the topic of semi-structured data to the forefront of research. The main purpose of the paper is to isolate the essential aspects of semistructured data. We also survey some proposals of models and query languages for semi-structured data.
- Lecture Recording
Feb 3: Architecture of a Database System [slides]
- (required reading - no summary) "Architecture of a Database System"; Joe Hellerstein, Mike Stonebraker, James Hamilton; Foundations and Trends 2007. (original paper; A crop-merged Version of that PDF)
Feb 8: Architecture of a Database System (Continued from above)
Feb 10: Data Mining [slides]
- (summary required) Tian Zhang, Raghu Ramakrishnan, Miron Livny. BIRCH: An Efficient Data Clustering Method for Very Large Databases. Proc. SIGMOD Conference, 1996, 103-114.
Feb 15: Data Mining (Cntd notes from above)
- (summary required) John C. Shafer, Rakesh Agrawal, Manish Mehta. SPRINT: A Scalable Parallel Classifier for Data Mining. Proc. VLDB, 1996, 544-555.
- (summary required) Surajit Chaudhuri, Vivek R. Narasayya, Sunita Sarawagi. Efficient Evaluation of Queries with Mining Predicates. Proc. ICDE, 2002, 529-.
Feb 17: Probabilistic Databases [slides]
- (summary required) Efficient query evaluation on probabilistic databases; Nilesh Dalvi, Dan Suciu; VLDB 2004
Feb 22: Midterm (in-class)
Feb 24: Query Processing [slides (to be completed)]
- (summary required) Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170 (1993) [link]
  
  Notes: This is a survey paper that covers the query processing architecture, operators, alternatives, advanced issues in great depth. You are required to read Sections 1 through 5.
  A critique/summary is required -- given the nature of the paper, this could either be questions about the paper -- something that you were not able to follow, or you could write some thoughts on how relevant are the tradeoffs discussed in the paper today -- e.g., query processing model/operators are based on the assumption that the data is disk-resident: how would this change if the storage media was primarily flash or a distributed key/value store like Google Bigtable where the data is stored in a distributed fashion in memory, with replication? Are large amounts of main memory making many of the tradeoffs irrelevant anyway?
March 1: Query Processing/Column-Stores (Slides cntd from above)
- (summary required) Column-stores vs. row-stores: how different are they really? Abadi et al.; SIGMOD 2008 [link to pdf]
March 3: Query Optimization (Slides cntd from above)
- (summary required) Surajit Chaudhuri: An Overview of Query Optimization in Relational Systems. PODS 1998: 34-43; [link to pdf]
  
  Notes: This is also a (short) survey paper. See Feb 24 reading for suggestions on how to write a critique.
- A very nice overview of DB2 Optimizer (by Guy Lohman)
March 8: Data Streams (Slides cntd from above)
- (required reading -- summary not required) Continuous queries over data streams; Babu, Widom; SIGMOD Record 2001[link to pdf]
- (optional) "The 8 Requirements of Real-Time Stream Processing"; M. Stonebraker, U. Cetintemel, and S. Zdonik. In SIGMOD Record, 2005. [pdf]
March 10: Parallel Databases; Mapreduce [slides]
- (summary required) MapReduce: A Flexible Data Processing Tool; Jeffrey Dean and Sanjay Ghemawat; CACM 2010
- (summary required) MapReduce and Parallel DBMSs: Friends or Foes? Stonebraker et al.; CACM 2010
  
  Notes: Write a single critique for both the papers combined.
Mar 15: Key/Value Stores (Slides cntd from above)
- (summary required) PNUTS: Yahoo!'s Hosted Data Serving Platform; Cooper et al.; VLDB 2008 [link]
- (optional reading) Pig latin: a not-so-foreign language for data processing; SIGMOD 2008 [link]
Mar 17: Access Methods [slides]
- (summary required) Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer. Generalized Search Trees for Database Systems. Proc. VLDB, 1995, 562-573.
Mar 22: Spring Break
Mar 24: Spring Break
Mar 29: Transactions: Overview [slides]
- (required reading - no summary) Concurrency Control and Recovery; Mike Franklin, 1997 [pdf link]
  
  Notes: This is an overview article, and although no summary is required, the next 3-4 papers may be hard to follow without this (or some other equivalent) survey.
Mar 31: Transactions: Concurrency (Cntd notes from above)
- (summary required) H. T. Kung, John T. Robinson. On Optimistic Methods for Concurrency Control. Proc. VLDB, 1979, 351.
- (summary required) Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981)
- (more details) A survey of B-tree locking techniques; Graefe, TODS 2010 [link]
April 5: Transactions: Concurrency (Cntd notes from above)
- (summary required) Berenson et al. A Critique of ANSI SQL isolation levels; SIGMOD 1995 [link]
April 7: Transactions: Recovery (Cntd notes from above)
- (summary required) C. Mohan, Donald J. Haderle, Bruce G. Lindsay, Hamid Pirahesh, Peter M. Schwarz. ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. ACM Trans. Database Syst., 17(1), 1992, 94-162. (Till Section 7)
April 12: Transactions: Replication (Cntd notes from above)
- (summary required) Dangers of replication and a solution; Gray et al.; SIGMOD 1996. [link]
- (no summary required) Eventual Consistency; Vogels; CACM 2009. [link]
- (optional, but may be helpful to read before the above) A short note by Mike Stonebraker on CAP and Eventual Consistency.
April 14: Transactions: Distributed Databases (Cntd notes from above)
- (summary required) Consensus on Transaction Commit; Gray, Lamport; TODS 2006. [link]
April 19: Data Warehousing [slides 1] [slides 2 - PPT]
- (summary required) Jim Gray, Surajit Chaudhuri, Adam Bosworth, Andrew Layman, Don Reichart, Murali Venkatrao, Frank Pellow, Hamid Pirahesh. Data Cube: A Relational Aggregation Operator Generalizing Group-by, Cross-Tab, and Sub Totals. Data Min. Knowl. Discov., 1(1), 1997, 29-53.
April 21: Data Warehousing (Cntd notes from above)
- (summary required) DynaMat: a dynamic view management system for data warehouses; Yannis Kotidis, Nick Roussopoulos. SIGMOD Conference 1999.
April 26: Auto Admin [slides]
- (summary required) Self-tuning database systems: a decade of progress; Chaudhuri, Narasayya; VLDB 2007 [link]
April 28: XML [slides]
- (summary required) Relational Databases for Querying XML Documents: Limitations and Opportunities; Jayavel Shanmugasundaram et al.; VLDB 1999
May 3: Performance
- (optional) Ailamaki et al.; DBMSs on a modern processor: where does the time go?; VLDB 1999
- (summary required) Ailamaki et al.; Weaving relations for cache performance; VLDB 2001
May 5: Performance
- (summary required) FAST: fast architecture sensitive tree search on modern CPUs and GPUs; SIGMOD 2010
May 10: Project Presentation. AVW 3258. 11am-1pm.

Web Accessibility