Presentation Topics for CS240A: Winter 98

• Students team-up in pairs.
• Presentations should take 45 minutes. A presentation normally covers two closely related papers
• Annotated transparencies must be made available to the rest of the class---preferably using the WEB.
• A presentation for remote web users supplies an excellent guideline
• For better coverage, only few presentations per topic (first-come-first-serve)
• Classroom discussion essential: questions on presentations will be in the take-home final.
• Evaluation Based on:
• Response by participants
• Clarity of exposition
• Quality of commented hand-outs
• Technical Depth

• Deductive Database Systems 

(A good topic for CS249)
• Active DBs systems
• Implementation Issues 
• Rule analysis and design,

termination and determinism 
• Composite Events
• Integrity constraints 
• Temporal Databases
• Models and Query Languages 
• Storage structurs for Temporal Databases
• Time Series and TSMSs 
• Spatial Databases
• Language Issues 
• Storage structures, indexing and searching 
• Uncertainty in Databases
• Extensible Databases
• ROLAPS and Data warehouses 
• Data Mining 
• Concrete Views 
• Databases and the WEB
• Queries without schema, and wrappers 

REFERENCES: How to get the papers

• Many papers can be downloaded from the WEB. Start from the homepage of the authors. There, you might also find their most recent papers on the subject.

• ACM-SIGMOD has links to several DB repositories

• Links to topic-specific repositories are listed in this page under the appropiate header.

• If everything else fails, ask the instructor.

Deductive Database Systems

Chimenti, D. et al., The LDL System Prototype," IEEE Journal on Data and Knowledge Engineering, vol. 2, no. 1, pp. 76-90, March 1990.

Phipps, G., M.A., Derr and K. A. Ross, Glue-Nail: a Deductive Database System," Proc. 1991 ACM-SIGMOD Conference on Management of Data, pp. 308-317 (1991).

Ramakrishan, R., Srivastava D. and Sudarshan, S., Coral: Control, Relations and Logic," in Proceedings of the 18th Very Large Database Conference, 1992.

Rao, K. An Implementation Overview of Aditi", 3rd Int. Conference, on Deductive and Object-Oriented Databases, Scottsdales, AZ, Dec. 6-8, 1993.

Active DBs systems

• Implementation Issues

J. Widom, R. J. Cochrane, and B. G. Lindsay, Implementing set-oriented production rules as an extension to Starburst", Proceedings of the Seventeenth International Conference onVery Large Data Bases, pp. 275-285, Barcelona, Spain, September 1991.

M. Stonebraker et al. "On Rules, Procedures, Caching and Views in Database Systems," ACM SIGMOD 1990, 281-290.

D. R. McCarthy and U. Dayal, The architecture of an active database management system" Proceedings of the ACM SIGMOD International Conference on Management of Data, pp 215-224, Portland, Oregon, May 1989.

• Active DBs Rule analysis and design, termination, determinism

 A. Aiken, J. Widom and M. Hellerstein, Behavior of database production rules: Termination, confuence and observable termination. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 59-68, 1992.

S. Ceri E. Baralis and S. Paraboschi. Run-Time Detection of Non-Terminating Active Rule Systems. In A. Mendelzon T. W. Ling and L. Vielle, editors, Procs of 4th Deductive and O-O Databases Conference: DOOD'96, pages 38-44. Springer-Verlag, 1995.

E. Baralis et al. Improved rule analysis by means of trigggering and activation graphs. In Proceedings of the 2nd International Workshop on Rules in Database Systems, Athens, Greece, 1995.

C. Zaniolo. Active Database Rules with transaction-conscious stable-model semantics. In A. Mendelzon T. W. Ling and L. Vielle, editors, Procs of 4th Deductive and O-O Databases Conference: DOOD'96, pages 54-72. Springer-Verlag, 1995.


• Active DBs: Composite Events

S. Gatziu and K. R. Dittrich. Detecting composite events in active databases using Petri Nets. In Proceedings of the 4th Intl. Workshop on Research Issues in Data Engineering: Active Database Systems, pages 2-9, February 1994.

N. H. Gehani, H. V. Jagadish, and O. Shmueli. Composite event specifcation in active databases: Model and implementation. In Proceedings of the 18th VLDB International Conference, pages 327-338, 1992.

N. H. Gehani, H. V. Jagadish, and O. Shmueli. Event specification in an active object-oriented database. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 81-90, 1992.

I. Motakis and C. Zaniolo. Composite Temporal Events in Active Database Rules: A Logic-Oriented Approach. In Proceedings of the 4th Intl. Conference on Deductive and Object-Oriented Databases, 1995.

• Active DBs and Integrity constraint enforcement

Ceri, S., and Widom, J., Deriving Production Rules in Incremental View Maintenance," Procs. of 7th VLDB Conference (1991).

S. Ceri, et al., Automatic Generation of Production Rules for Integrity Maintenance," ACM TODS, 19(3), pp. 367-422, Sept. 1994.

Temporal Databases

• Data Models and Query languages

N. A. Lorentzos and Roger G. Johnson, An Extension of the Relational Model to Support Generic Intervals," in Advances in Database Technology, (Schmidt, Ceri and Missicoff, eds.), pp. 528-542, Springer Verlag, Lecture Notes in C.S., 1988.

T. Y. Cliff Leung and R. Muntz, "Stream Processing: Temporal Query Processing and Optimization," in, Temporal Databases, A.U.Tansel et al. (eds), Benjamin/Cummings, 1993.

N. L. Sarda, HSQL: A Historical Query Language," in, Temporal Databases, A.U.Tansel et al. (eds), Benjamin/Cummings, 1993.

M. Baudinet, M. Nizette and P. Wolper, On the Representation of Infinite Temporal Data and Queries, Procs. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1991.

• Temporal DB: Intexing and Storage Structures

B. Salzberg and V.J. Tsotras, "A Comparison of Access Methods forTime-Evolving Data,"
ACM Computing Surveys, to  appear (This is a general survey that can also that can also be obtained from from
http://www.cs.auc.dk/general/DBS/tdb/TimeCenter/publications2.html)

B. Becker, S. Gschwind, T. Ohler, B. Seeger, and P. Widmayer, "An
Asymptotically Optimal Multiversion B-Tree," Very Large Data Bases J., Vol. 5, no. 4, pp. 264-275, 1996.

D. Lomet and B. Salzberg, Transaction-Time Databases," in, Temporal Databases, A. U. Tansel et al. (eds), Benjamin/Cummings, 1993.

Vassilis J. Tsotras, B. Gopinath, and George W. Hart, Efficient Management of Time-Evolving Databases, IEEE Transactions on Knowledge and Data Engineering, Vol. 7, No. 4, August 1995

V.J.Tsotras, N. Kangelaris, "The Snapshot Index, an I/O-Optimal Access Method for Snapshot Queries", Information Systems, An International Journal, Vol. 20 No. 3, pp 237-260, 1995.

Time Series and TSMSs

D. Schmidt et al. Time Series, a Neglected Issue in Temporal Database Research? In J. Clifford and A. Tuzhilin, editors, Recent Advances in Temporal Databases, Workshops in Computing Series, pages 214-232. Springer, 1995.

A. Segev and A. Soshani, A Temporal Data Model Based on Time Sequences," in Temporal Databases, A.U. Tansel et al. (eds), Benjamin/Cummings, 1993.

R. Chandra and A. Segev. Managind temporal financial data in an extensible database. In Proc. of the 19th VLDB, pages 302-313, 1993.

R. Chandra, A. Segev, and M. Stonebraker. Implementing Calendars and Temporal Rules in Next Generation Databases. In Proc. of the 10th IEEE Intl. Conference on Data Engineering, pages 264-273, 1994.

P. Seshadri, M. Livny, and R. Ramakrishnan. Sequence query processing. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 430-441, 1994.

P. Seshadri, M. Livny, and R. Ramakrishnan. SEQ: Design and implementation of a sequence database system. submitted for publication, 1996.

Also see Chang-Shing Perng's references (with comments and links) on Time Series

Spatial Databases

• Language Issues

N. Rossoupoulos, C. Faloustsos and T. Sellis, An Efficient Pictorial Database System for PSQL,", IEEE Transactions on Software Engineering, 14, 5, May 1988.

L. Mohan and R.L. Kashyap, An Object-Oriented Knowledge Representation for Spatial Information," IEEE Transactions on Software Engineering, 14, 5, May 1988.


• Spatial DBs: Storage structures, indexing, and searching

E. G. Hoel and H. Samet, A Qualitative Comparison Study of Data Structures for Large Line Segmented Databases," Procs. 1992 ACM SIGMOD Int. Conference on Management of Data, pp. 205-214, ACM, 1992.

G. Nagy and S. Wagle, Geographic Data Processing," ACM Computing Surveys, 11, 2, June 1979.

C. Kolovoson and M. Stonebraker, Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Data," Procs. 1991 ACM SIGMOD Int. Conference on Management of Data, pp. 138-147, ACM, 1991.

Also Part IV in ADS Textbook.

Uncertainty in Databases

Part V of ADS Textbook

L. Lackshaman and N. Shiri, "A Parametric Approach to Deductive Databases with Uncertainty," Logic In Databases, Int. Workshop LID'96 Procs., Springer Verlag, 1966.

Extensible Databases

Praveen Seshadri, Miron Livny, Raghu Ramakrishnan, "The Case for Enhanced Abstract Data Types, VLDB 1997, pp. 66-75. Project Web Page: http://www.cs.cornell.edu/Info/Projects/PREDATOR

Surajit Chaudhuri, Kyuseok Shim: Optimization of Queries with User-defined Predicates. VLDB 1996: pp. 87-98.

ROLAPS and Data Warehouses

Peter Scheuermann, Junho Shim, Radek Vingralek: WATCHMAN : A Data Warehouse Intelligent Cache Manager. Procs VLDB 96, Bombay, India pp. 51-62.

Wilburt Labio, Hector Garcia-Molina: Efficient Snapshot Differential Algorithms for Data Warehousing. Procs VLDB 96, Bombay, India pp. 63-74.

R. Agrawal, K. Shim: ``Developing Tightly-Coupled Data Mining Applications on a Relational Database System'', Proc. of the 2nd Int'l Conference on Knowledge Discovery in Databases and Data Mining, Portland , August, 1996

R. Agrawal, A. Swami: "A One-Pass Space-Efficient Algorithm for Finding Quantiles", Proc. of the 7th Int'l Conference Management of Data (COMAD-95), Pune, India, December 1995.

R. Agarwal, R. Agrawal, P.M. Deshpande, A. Gupta, J.F. Naughton, R. Ramakrishnan, S. Sarawagi, "On the Computation of Multidimensional Aggregates", Proc. of the 22th Int'l Conference on Very Large Databases, Mumbai (Bombay), India, Sept. 1996.

D. Srivastava and K. A. Ross, ``Fast Computation of Sparse Datacubes'', Proceedings of the 1997 VLDB Conference, pages 116-125, August 1997.

Data Mining       Data Mining WEB site

Association Rules

R. Srikant, Q. Vu, R. Agrawal, "Mining Association Rules with Item Constraints", Proc. of the 3rd Int'l Conference on Knowledge Discovery in Databases and Data Mining, Newport Beach, California, August, 1997.

R. Agrawal, J.C. Shafer, "Parallel Mining of Association Rules: Design, Implementation and Experience", IEEE Transactions on Knowledge and Data Engineering, Vol.8, No. 6, Dec. 1996.

R. Agrawal, H. Mannila, R. Srikant, H. Toivonen and A. I. Verkamo, ``Fast Discovery of Association Rules'', Advances in Knowledge Discovery and Data Mining, Chapter 12, AAAI/MIT Press, 1995.

R. Srikant, R. Agrawal: "Mining Generalized Association Rules", Proc. of the 21st Int'l Conference on Very Large Databases, Zurich, Switzerland, Sep. 1995.

Sergey Brin, Rajeev Motwani, Jeffrey Ullman, and Shalom Tsur, Dynamic Itemset Counting and Implication Rules for Market Basket Data, Proc. of ACM-SIGMOD 1997

Sequential Patterns

R. Srikant, R. Agrawal, "Mining Sequential Patterns: Generalizations and Performance Improvements," Proc. of the Fifth Int'l Conference on Extending Database Technology (EDBT), Avignon, France, March 1996.

Time Series

R. Agrawal, C. Faloutsos, A. Swami: "Efficient Similarity Search in Sequence Databases", Proc. of the 4th Int'l Conference on Foundations of Data Organization and Algorithms, Chicago, Oct. 1993,

Classifiers

C. Elkan, Boosting and Naive Bayesian Learning. Knowledge Discovery in Databases (KDD'97), August 1997.

J.C. Shafer, R. Agrawal, M. Mehta, "SPRINT: A Scalable Parallel Classifier for Data Mining", Proc. of the 22th Int'l Conference on Very Large Databases, Mumbai (Bombay), India, Sept. 1996.

Clustering

Wei Wang, J. Yang and R. Muntz, STING: A stastistical information grid approach to spatial data mining," VLDB97, pp. 186-195.

Concrete Views

Y. Zhughe et al., View Maintenance in a Warehousing Environment," Procs. 1995 ACM SIGMOD Int. Conference on Management of Data, SIGMOD Record, 24:2, pp. 316-327, June 1995.

T. Griffin and L. Libkin Incremental Maintenance of Views with Duplicates," Procs. 1995 ACM SIGMOD Int. Conference on Management of Data, SIGMOD Record, 24:2, pp. 328-339, June 1995.

"Efficient Maintenance of Materialized Mediated Views," Procs. 1995 ACM SIGMOD Int. Conference on Management of Data, SIGMOD Record, 24:2, pp. 340-351, June 1995.

A. Y. Levy, et al. , "Answering Queries Using Views," Procs. 14th PODS Symposium, pp. 95-104, 1995.

Kenneth A. Ross, Divesh Srivastava, S. Sudarshan, Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time. In Procs. ACM SIGMOD 1996, pp. 447-458.

Claire Morpain, Michhle Cart, Jean Ferrii, Jean-Frangois Pons: Maintaining Database Consistency in Presence of Value Dependencies in Multidatabase Systems. In Procs. ACM SIGMOD 1996, pp. 459-468.

Latha S. Colby, Timothy Griffin, Leonid Libkin, Inderpal Singh Mumick, Howard Trickey: Algorithms for Deferred View Maintenance. in Procs. ACM SIGMOD 1996, pp. 469-480

Richard Hull, Gang Zhou: A Framework for Supporting Data Integration Using the Materialized and Virtual Approaches. in Procs. ACM SIGMOD 1996, pp. 481-492.

Martin Staudt, Matthias Jarke: Incremental Maintenance of Externally Materialized Views. Procs VLDB 96, Bombay, India pp. 63-74.

Divesh Srivastava, Shaul Dar, H. V. Jagadish, Alon Y. Levy: Answering Queries with Aggregation Using Views. Procs VLDB 96, Bombay, India pp. 318-329.

Databases and the WEB

DB Support for WEB Publishing

Allaire: Cold Fusion 1.5 Overview and Features
http://fbsolutions.com/ntfnt/cfusion.htm, 17 Nov 96.

Informix, Press Announcement: New Version of Web DataBlade Module.
http://www.informix.com/informix/corpinfo/ifxnews/press/1996/webblade.htm, 3 Dec 96.

Querying WEB Documents

By T. Minohara and R. Watanabe. "Queries on structure in hypertext," In Foundations of Data Organization and Algorithms, FODO'93, page 394-411. Springer, 1993

A. O. Mendelzon and P. T. Wood, "Finding regular simple paths in graph databases," In SIAM J. Comp., 24(6), 1995

D. Konopnicki and O. Shmueli. "W3QS: A query system for the World Wide Web." In Proc. of VLDB'95, pages 54-65, 1995

By G.A. Mihaila A. Mendelzohn and T. Milo. "Querying the world wide web." ftp://ftp.math.tau.ac.il/pub/milo/websql.ps.Z

Vassilis Christophides, Sophie Cluet, Guido Moerkotte: Evaluating Queries with Generalized Path Expressions. pp. 413-422

S. Abiteboul, R. Hull, and V. Vianu, "Querying semistructured data." In Proc. ICDT, Greece, 1997

Vassilis Christophides, Serge Abiteboul, Sophie Cluet, Michel Scholl: From Structured Documents to Novel Query Facilities. SIGMOD Conference 1994, pp. 313-324

Laks V.S. Lakshmanan, Fereidoon Sadri, and Iyer N. Subramanian, "A declarative language for querying and restructuring the Web." In Proc. of 6th International Workshop on Research Issues in Data Engineering, RIDE '96, New Orleans, February 1996.

C. Schlepphorst, R. Himmeröder, G. Lausen, B. Ludäscher, ``On a Declarative Semantics for Web Queries'', Proc. 5th Intl. Conf. on Deductive and Object-Oriented Databases (DOOD'97), 1997, Montreux, Switzerland, LNCS 1341, Springer.

Queries without schema and Wrappers

P. Papakonstantinou et al., A Query Translation Schem for Rapid Implementation of Wrappers," Procs. of Deductive and Object-Oriented Databases, DOOD95, pp.161-186, Singapore 95.

A. Rajaraman, Y. Sagiv, J. Ullman, Answering Queries Using Templates with Binding Patterns," Procs. PODS Congerence, pp. 105-112, 1995.