CSE 485/585 Advanced Database Systems (3 Credits)

Catalog description:

Relational calculus. Query processing and optimization. Transaction processing: failure, recovery, and concurrency. Database security. Logic-based systems. Parallel, distributed, and client/server systems. Object-oriented database systems. Emerging database technologies.

Prerequisite:

CSE 385 or equivalent

Required topics: (approximate weeks allocated):

  • Review of the relational data model, relational algebra, and SQL (.5)
  • Relational calculus (2)
    • tuple-oriented relational calculus
    • implementations of tuple calculus (Ingres/QUEL)
    • domain-oriented tuple calculus
    • implementations of domain calculus (Query-by-Example)
    • equivalence of relational algebra & relational calculus
  • Query processing and optimization (1)
    • functions of the query optimizer
    • converting queries to an internal parse tree
    • conversion to canonical form
    • access path selection
    • query plan generation
    • transformation or algebraic expressions
    • use of database statistics in optimization
    • implementations of the relational algebra operations
  • Database failure and recovery (1)
    • database transactions, transaction processing, and transaction manager
    • transaction recovery
    • system/media failures and recovery
    • two-phase commit
    • SQL support of database recovery
  • Concurrency control in database processing (1)
    • concurrency problems
    • locking
    • deadlock and deadlock resolution techniques
    • serializability and two-phase locking protocol
    • intent locking protocol
    • optimistic concurrency control and time-stamping
    • SQL support of concurrence
  • Database security (1)
    • basic concepts of database security
    • discretionary access control and audit trails
    • request modification
    • mandatory access control
    • data encryption, the data encryption standard, and public-key encryption
    • SQL support of database security
  • Missing information (1)
    • null values and three-valued logic
    • outer join
    • SQL support for nulls and three-valued logic
  • Logic-based database systems (1.5)
    • review of propositional and predicate calculus
    • proof-theoretic view of databases
    • deductive database systems and Datalog
    • recursive query processing
  • Parallel, distributed, and client/server databases (1.5)
    • multi-CPU architectures for databases
    • distributed databases
      • fundamental principles
      • objectives of distributed databases
      • data fragmentation, replication, and allocation techniques
      • types of distributed database systems
      • query processing
      • catalog management
      • update operations
      • recovery and concurrency control
    • client/server systems
  • Object-oriented databases (1.5)
    • basic concepts of object-oriented systems
    • object identity, object structure, and type constructors
    • encapsulation of operations
    • type and class hierarchies and inheritance
    • polymorphism
    • multiple and selective inheritance
    • examples of OODBMSs
  • Emerging database technologies (2)
    example topics:
    • natural language databases
    • multimedia databases
    • fuzzy databases
    • database machines
    • data warehousing
    • data visualization
  • Exams/Review (1)

*This part of the course may be done as student group projects and presentations.

Graduate students:

Students enrolled in CSE 585 will be given additional readings and/or assignments.

Course Outcomes

1: Be able to write queries in a relational database in a variety of languages:

1.1: Create domain and tuple relational calculus expressions to express queries on relational databases.

1.2: Use graphical database languages (such as Query-by-Example) to express queries on relational databases.

2: Be able to describe, apply, and implement techniques for performance tuning in databases.

2.1: Estimate the cost of performing a database query with a specific set of file structures.

2.2: Given a specific database the student can design a set of file structures to improve the performance of the system.

3: Be able to describe, apply, and implement techniques for robustness in databases.

3.1: Explain and use methods for concurrency control in a database system.

3.2: Explain and use methods for recovery in a database system.

3.3: Explain and use methods for security in relational databases.

4: Be able to describe and utilize non-relational database management systems.

4.1: Explain applications of logical database management Systems (LDBMS) as well as describe the difference between and LDBMS and a RDBMS (relational database management systems).

4.2: Explain applications of object-oriented database models as well as describe the difference between object-oriented database models and the relational database model.

5: Explain and use methods for distributed/parallel/client-server database architectures.

6: Describe and apply at least two emerging topics in database systems, with examples topics including: natural language databases, multimedia databases, fuzzy databases, data mining, data warehousing, data visualization, and XML databases.