CSI5311 -- Reading List

Reading List for the CSC5311 Course

Introductory Note

Many of the recent (and some of the old) papers can be found on line at the authors' web pages. The old ones may be found at the ACM on-line library (ACM portal) that is usually accessible from your home University library. Another place to find database papers on line is the famous DBLP Computer Science Bibliography. The DBLP server permits a search using authors, titles, etc, as key words.

The list is a mix of classical papers and recent material. It is still under construction. Right now, I have mostly put material on interoperability and multidatabases. Material on design, web data and transactions is partial. The rest will come progressively. Therefore, consult this list regularly.

Database Design

Methodologies

L. Kazerouni and K. Karlapalem. Stepwise Redesign of Distributed Relational Databases. Tech. Report HKUST-CS97-12. Hong Kong Univ. of SCience and Technology, Dept. of Computer Science, 1997.
Alok R. Chaturvedi, Samir Gupta, Subhajyoti Bandyopadhyay. SimDS: A Simulation Environment for the Design of Distributed Database Systems. DATA BASE 29(3): 65-81 (1998).
K. Karlapalem, S.B. Navathe, and M. Ammar. Optimal Redsign Policies to Support Dynamic Processing of Applications on a Distributed Relational Database System. Information Systems 21(4): 353-367 (1996).
Ravi Mukkamala, Steven C. Bruell, Roger K. Shultz. Design of Partially Replicated Distributed Database Systems: An Integrated Methodology. SIGMETRICS 1988, p. 187-196.
S. Muro, T. Ibaraki, H. Miyajima, and T. Hasegawa. Evaluation of File Redundancy in Distributed Database Systems. IEEE Trans. on Software Eng. 11(2):199-205 (1985).
S. Ceri and B. Pernici. DATAID--D: Methodology for Distributed Database Design. In A. Albano, V. de Antonellis, and A. di Leva (eds.), Computer Aided Database Design, Amsterdam, North-Holland, 1985, p. 157-183.

Fragmentation

S. Ceri, S. Navathe, and G. Wiederhold. Distribution Design of Logical Database Schemes. IEEE Trans. on Soft. Eng. 9(4): 487-503 (1983).
S. Ceri, B. Pernici, and G. Wiederhold. Distributed Database Design Methodologies. Proc IEEE ICDE 75(5): 533-546 (1987).
S. Navathe, S. Ceri, G. Wiederhold, and J. Dou. Vertical Partitioning of Algorithms for Database Design. ACM Trans. on Database Systems 9(4): 680-710 (1984).
D. Sacca, and G. Wiederhold. Database Partitioning in a Cluster of Processors. ACM Trans. on Database Systems 10(1): 29-56 (1985).
L.W. Dowdy and D.V. Foster. Comparative Models of the File Assignment Problem. ACM Computing Surveys 14(2): 287-313 (1982).

Data Allocation Problem

B. Kemme and G. Alonso. A New Approach to Developing and Implementing Eager Database Replication Protocols. ACM Trans. on Database Systems, September 2000.
E. Pacitti and E. Simon. Update Propagation Strategies to Improve Freshness in Lazy Master Replicated Databases. VLDB Journal 8(3-4): 305-318 (2000).
Y. Breitbart et al. Update Propagation Protocols for Replicated Databases. ACM SIGMOD 1999, p. 97-108.
Kamalakar Karlapalem, Ng Moon Pun. Query-Driven Data Allocation Algorithms for Distributed Database Systems. DEXA 1997, p. 347-356.
J. Gray, P. Helland, P. O'Neil, and D. Shasha. The Dangers of Replication and a Solution. ACM SIGMOD 1996, p. 173-182.
S.B. Davidson, H. Garcia-Molina, and D. Skeen. Consistency in Partitioned Networks. ACM Computing Surveys 17(3): 341-370 (1985).
S. Ceri and G. Pelagatti. A Solution Method for the Non-additive Ressource Allocation Problem in Distributed System Design. Information Processing Letters 15(4): 174-178 (Oct. 1982).
P.S. Fischer and D.S. Hochbaum. Database Location in Computer Networks. Journal of the ACM 27(4): 718-735 (Oct. 1980).
S.K. Chang and A.C. Liu. File Allocation in a Distributed Database. International Journal of Computation and Information Science 11(5): 325-340 (1982).

Query Processing

Transaction Management and Concurrency Control

General

Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman. Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987.

Specifics

Ahmed K. Elmagarmid, Ajoy Kumar Datta. Two-Phase Deadlock Detection Algorithm. IEEE Transactions on Computers 37(11): 1454-1458 (1988).
Ajoy Kumar Datta, Sukumar Ghosh, Douglas Harms, Ahmed K. Elmagarmid. Deadlock-Avoidance Mechanisms in Distributed Systems. Journal of Computer Systems Science and Engineering 3(2): 67-82 (1988).
Ahmed K. Elmagarmid, Neelam Soundararajan, Ming T. Liu. A Distributed Deadlock Detection and Resolution Algorithm and Its Correctness Proof. TSE 14(10): 1443-1452 (1988).
Ahmed K. Elmagarmid, Yungho Leu. An Optimistic Concurrency Control Algorithm for Heterogeneous Distributed Database Systems. Data Engineering Bulletin 10(3): 26-32 (1987).
Ahmed K. Elmagarmid. Fault-Tolerant Deadlock Detection in Distributed Database Systems. Journal of Computer Systems Science and Engineering 2(1): 16-28 (1987).
Amit P. Sheth, Anoop Singhal, Ming T. Liu. An Adaptive Concurrency Control Strategy for Distributed Database Systems. ICDE 1984: 474-482.
Ahmed K. Elmagarmid, Amit P. Sheth, Ming T. Liu. Deadlock Detection Algorithms in Distributed Database Systems. ICDE 1986: 556-564.
Ahmed K. Elmagarmid. A Survey of Distributed Deadlock Algorithms. SIGMOD Record 15(3): 37-45 (1986).

Database Interoperability

General

A. Sheth and J. Larson. Federated Databases: Architectures and Issues. ACM Computing Surveys, 22 (3), September 1990, pp. 183-236.
Witold Litwin, Leo Mark, Nick Roussopoulos. Interoperability of Multiple Autonomous Databases. ACM Computing Surveys 22(3): 267-293 (1990).
Carlo Batini, Maurizio Lenzerini, Shamkant B. Navathe. A Comparative Analysis of Methodologies for Database Schema Integration. ACM Computing Surveys 18(4): 323-364 (1986).
Ahmed Elmagarmid, Marek Rusinkiewicz, Amit Sheth. Management of Heterogeneous and Autonomous Database Systems. Morgan Kaufmann, 1999.

Specifics

S. Thacker, A. Sheth and S. Patel. Complex Relationships for the Semantic Web. In D. Fensel, J. Hendler, H. Liebermann, and W. Wahlster (eds.). Spinning the Semantic Web, MIT Press, 2002.
L. V. S. Lakshmanan, F. Sadri, and S. N. Subramanian. SchemaSQL—An: Extension to SQL for Multidatabase Interoperability. ACM TODS 26(4), 476-519, 2001.
Sharad Mehrotra, Rajeev Rastogi, Yuri Breitbart, Henry F. Korth, Abraham Silberschatz. Overcoming Heterogeneity and Autonomy in Multidatabase Systems. Information and Computation 167(2): 137-172 (2001).
A. Sheth. Changing Focus on Interoperability. In Information Systems: From System, Syntax, Structure to Semantics. In M. F. Goodchild, M. J. Egenhofer, R. Fegeas, and C. A. Kottman (eds.)Interoperating Geographic Information Systems, Kluwer, Academic Publishers, 1998, pp. 5-30.
Eduardo Mena, Arantza Illarramendi, Vipul Kashyap, Amit P. Sheth. OBSERVER: An Approach for Query Processing in Global Information Systems Based on Interoperation Across Pre-Existing Ontologies. In Distributed and Parallel Databases 8(2): 223-271 (2000)
Eduardo Mena, Vipul Kashyap, Arantza Illarramendi, Amit P. Sheth. Imprecise Answers in Distributed Environments: Estimation of Information Loss for Multi-Ontology Based Query Processing. IJCIS 9(4): 403-425 (2000)
K. Shah and A. Sheth. InfoHarness: An Information Integration Platform for Managing Distributed, Heterogeneous Information. IEEE Internet Computing, November-December 1999, p. 18-28.
R. J. Miller. Using Schematically Heterogeneous Structures. SIGMOD 1998, p. 189-200.
V. Kashyap and A. Sheth. Schematic and Semantic Similarities between Database Objects: A Context-based Approach. Very Large Data Bases (VLDB) Journal, 5(4), October 1996, pp. 276-304.
N. Krishnakumar and A. Sheth. Managing Heterogeneous Multi-system Tasks to Support Enterprise-wide Operations,” Distributed and Parallel Databases Journal, 3 (2), April 1995, pp. 155-186.
Yuri Breitbart, Hector Garcia-Molina, Abraham Silberschatz. Transaction Management in Multidatabase Systems. Modern Database Systems: The Object Model, Interoperability, and Beyond. 1995: 573-591.
George Karabatis, Marek Rusinkiewicz, Amit P. Sheth. Correctness and Enforcement of Multidatabase Interdependencies. LNCS 759: 337-358 (1993).
Amit P. Sheth, Vipul Kashyap. So Far (Schematically) yet So Near (Semantically). DS-5 1992: 283-312.
John Grant, Witold Litwin, Nick Roussopoulos, Timos K. Sellis: Query Languages for Relational Multidatabases. VLDB Journal 2(2): 153-171 (1993).
L. Suardi, Marek Rusinkiewicz, Witold Litwin: Execution of Extended Multidatabase SQL. ICDE 1993: 641-650.
Amit P. Sheth, Marek Rusinkiewicz, George Karabatis. Using Polytransactions to Manage Interdependent Data. In A. Elmagarmid et al., Database Transaction Models for Advanced Applications 1992: 555-581.
Marek Rusinkiewicz, Amit P. Sheth. Multidatabase Applications: Semantic and System Issues. VLDB 1992: 545.
Mansoor Ansari, Linda Ness, Marek Rusinkiewicz, Amit P. Sheth. Using Flexible Transactions to Support Multi-System Telecommunication Applications. VLDB 1992: 65-76.
Sharad Mehrotra, Rajeev Rastogi, Yuri Breitbart, Henry F. Korth, Abraham Silberschatz: Ensuring Transaction Atomicity in Multidatabase Systems. PODS 1992: 164-175.
Yuri Breitbart, Abraham Silberschatz. Strong Recoverability in Multidatabase Systems. RIDE-TQP 1992: 170-175.
Sharad Mehrotra, Rajeev Rastogi, Yuri Breitbart, Henry F. Korth, Abraham Silberschatz. The Concurrency Control Problem in Multidatabases: Characteristics and Solutions. SIGMOD Conference 1992: 288-297.
Yuri Breitbart, Abraham Silberschatz, Glenn R. Thompson. Transaction Management Issues in a Failure-Prone Multidatabase System Environment. VLDB Journal 1(1): 1-39 (1992).
Yuri Breitbart, Hector Garcia-Molina, Abraham Silberschatz. Overview of Multidatabase Transaction Management. VLDB Journal 1(2): 181-293 (1992).
Yuri Breitbart, Hector Garcia-Molina, Witold Litwin, Nick Roussopoulos, Hans-Jörg Schek, Gio Wiederhold. Interoperability In Multidatabases: Semantic and System Issues (Panel). VLDB 1991: 561.
Yuri Breitbart, Dimitrios Georgakopoulos, Marek Rusinkiewicz, Abraham Silberschatz. On Rigorous Transaction Scheduling. TSE 17(9): 954-960 (1991).
Weimin Du, Ahmed K. Elmagarmid, Won Kim. Maintaining Quasi Serializability in Multidatabase Systems. ICDE 1991: 360-367.
Dimitrios Georgakopoulos, Marek Rusinkiewicz, Amit P. Sheth. On Serializability of Multidatabase Transactions Through Forced Local Conflicts. ICDE 1991: 314-323.
Marek Rusinkiewicz, Amit P. Sheth, George Karabatis. Specifying Interdatabase Dependencies in a Multidatabase Environment. IEEE Computer 24(12): 46-53 (1991).
Ravi Krishnamurthy, Witold Litwin, William Kent. Interoperability of Heterogeneous Databases with Schematic Discrepancies. RIDE-IMS 1991: 144-155.
Ravi Krishnamurthy, Witold Litwin, William Kent. Language Features for Interoperability of Databases with Schematic Discrepancies. SIGMOD Conference 1991: 40-49.
Yungho Leu, Ahmed K. Elmagarmid. A Hierarchical Approach to Concurrency Control for Multidatabases. DPDS 1990: 202-210.
Ahmed K. Elmagarmid, Weimin Du. A Paradigm for Concurrency Control in Heterogeneous Distributed Database Systems. ICDE 1990: 37-46.
Ahmed K. Elmagarmid, Yungho Leu, Witold Litwin, Marek Rusinkiewicz. A Multidatabase Transaction Model for InterBase. VLDB 1990: 507-518.
Witold Litwin, Abdelaziz Abdellatif. Multidatabase Interoperability. IEEE Computer 19(12): 10-18 (1986).

Mobile Databases

General

E. Pitoura and G. Samaras. Data Management for Mobile Computing. Kluwer, 1998.
T. Imielinski and B.R. Badrinath. Mobile Wireless Computing: Challenges in Data Management. Communications of the ACM 37(10):18-28 (Oct. 1994).

Specifics

Abdelkader Hameurlain, Franck Morvan, Philipp Tomsich, Robert M. Bruckner, Harald Kosch, and Peter Brezany. Mobile Query Optimization Based on Agent-Technology for Distributed Data Warehouse and OLAP Applications. DEXA Workshops 2002, p. 795-799.
Ken C. K. Lee, Hong Va Leong, Antonio Si. Incremental View Maintenance for Mobile Databases. Knowledge and Information Systems 2(4): 413-437 (2000).
Shirish Hemant Phatak and B. R. Badrinath. Conflict Resolution and Reconciliation in Disconnected Databases. DEXA Workshop 1999, p. 76-81.
Shirish Hemant Phatak, B. R. Badrinath. Multiversion Reconciliation for Mobile Databases. ICDE 1999, p. 582-589.
Shirish Hemant Phatak, B. R. Badrinath. Data Partitioning for Disconnected Client Server Databases. MobiDE 1999, p. 102-109.
Siwoo Byun, Songchun Moon. Resilient Data Management for Replicated Mobile Database Systems. DKE 29(1): 43-55 (1999).
Ioana Stanoi, Divyakant Agrawal, Amr El Abbadi, Shirish Hemant Phatak, and B. R. Badrinath. Data Warehousing Alternatives for Mobile Environments. MobiDE 1999, p. 110-115.
V. Kumar. A Timeout-Based Mobile Transaction Commitment Protocol. ADBIS-DASFAA 2000, p. 339-345.
Ahmed K. Elmagarmid, Jin Jing, Omran A. Bukhres. An Efficient and Reliable Reservation Algorithm for Mobile Transactions. CIKM 1995, p. 90-95.
Zhiming Ding, Xiaofeng Meng, Shan Wang. O2PC-MT: A Novel Optimistic Two-Phase Commit Protocol for Mobile Transactions. DEXA 2001, p. 846-856.
Patricia Serrano-Alvarado, Claudia Roncancio, Michel E. Adiba: Analyzing Mobile Transaction Supports for DBMS. DEXA Workshop 2001, p. 595-600.
M. M. Gore, R. K. Ghosh. Recovery of Mobile Transactions. DEXA Workshop 2000, p. 23-27.
Jin Jing, Omran A. Bukhres, Ahmed K. Elmagarmid. Distributed Lock Management for Mobile Transactions. ICDCS 1995, p. 118-125.
Venu K. Murthy: Seamless Mobile Transaction Processing: Models, Protocols and Software Tools. ICPADS 2001, p. 147-156.

Data on the Web

M. Lenzerini. Data Integration: A Theoretical Perspective. PODS 2002.
S. Lam and M.T. Özsu, "Querying Web Data - The WebQA Approach. WISE 2002.
M. Spielmann, J. Tyszkiewicz and J. Van den Bussche. Distributed Computation of Web Queries Using Automata. PODS 2002.
M. Rabinovich and O. Spatscheck. Web Caching and Replication. Addison Wesley, 2002.
R. J. Miller, L. M. Haas, M. A. Hernández. Schema Mapping as Query Discovery. VLDB 2000.
C-C. K. Chang, H. Garcia-Molina, "Approximate Query Translation Across Heterogeneous Information Sources. VLDB 2000.
K. Yagoub, D. Florescu, V. Issarny, P. Valduriez. Caching Strategies for Data-Intensive Web Sites. VLDB 2000: 188-199.
D. Florescu and A. Levy and A. Mendelzon. Database techniques for the World Wide Web: A survey. SIGMOD Record, 27(3):59-74, 1998.
A. O. Mendelzon and G. A. Mihaila and T. Milo. Querying the World Wide Web. Journal on Digital Libraries, 1(1): 54-67, 1997
S. Abiteboul and D. Quass and J. McHugh and J. Widom and J. Wiener. The Lorel query language for semistructured data. Journal of Digital Libraries, 1(1): 68-88, 1997.
P. Buneman and S. Davidson and G. Hillebrand and D. Suciu. A query language and optimization techniques for unstructured data. SIGMOD 1996: 505-516.

Peer-to-Peer Multidatabases

General

Andy Oram, editor. Peer-to-Peer: Harnessing the Power of Disruptive Technologies. O'Reilly, March 2001.
Michael Miller. Discovering P2P, electronic book, San Francisco, CA, SYBEX, 2001.

Data Management Issues

P. Bernstein, F. Giunchiglia, T Kementsietsidis, J. Mylopoulos, L. Serafini, Zaihrayeu. Data Management for Peer-to-Peer Computing: A Vision WebDB Workshop on Databases and the Web, Madison, Winsconsin, USA, June 2002.
Steven Gribble, Alon Halevy, Zachary Ives, Maya Rodrig, Dan Suciu. What Can Databases do for Peer-to-Peer? WebDB Workshop on Databases and the Web, June 2001.
L. Serafini, F. Giunchiglia, J. Mylopoulos, and P. Bernstein. The Local Relational Model: Model and Proof Theory . Technical Report DIT-02-0009
F. Giunchiglia, I. Zaihrayeu. Making peer databases interact - a vision for an architecture supporting data coordination .in Proceedings of the Conference on Information Agents (CIA 2002), Madrid, September 2002
Karl Aberer, and Hans Hauswirth. Peer-to-Peer Information Systems: Concepts and Models, State-of-the-Art, and Future Systems. Tutorial, ICDE 2002, San Jose, CA.
Wee Siong Ng, Beng Chin Ooi, Kian Lee Tan and AoYing Zhou. PeerDB: A P2P-based System for Distributed Data Sharing.
Petar Maymounkov and David Mazieres. Kademlia: A Peer-to-peer Information System Based on the XOR Metric. In Proc. of IPTPS'02. Frank Dabek, Emma Brunskill, M. Frans Kaashoek, David Karger, Robert Morris,
Ion Stoica, and Hari Balakrishnan. Building Peer-to-Peer Systems With Chord, a Distributed Lookup Service. Proceedings of the 8th Workshop on Hot Topics in Operating Systems (HotOS-VIII), May 2001.
Anastasios Kementsietsidis, Marcelo Arenas, and Renee Miller. Data Mapping in Peer-to-Peer Systems. Technical Report CSRG-456, July 2002.
M. Lenzerini. Data Integration: A Theoretical Perspective. PODS'02, Madison, Winsconsin, USA, June 2002.
Jayant Madhavan, Phil Bernstein, Pedro Domingos, Alon Halevy. Representing and Reasoning about Mappings Between Domain Models. Proceedings of the AAAI Eighteenth National Conference on Artificial Intelligence 2002.

System Description

Munindar P. Singh, Philip Cannata, Michael N. Huhns, Nigel Jacobs, Tomasz Ksiezyk, KayLiang Ong, Amit P. Sheth, Christine Tomlinson, Darrell Woelk. The Carnot Heterogeneous Database Project: Implemented Applications. Distributed and Parallel Databases 5(2): 207-225 (1997).
Ling-Ling Yan, M. Tamer Özsu, Ling Liu. Accessing Heterogeneous Data Through Homogenization and Integration Mediators. CoopIS 1997: 130-139.
Yuri Breitbart, Tom C. Reyes: Overview of the ADDS System. Modern Database Systems: The Object Model, Interoperability, and Beyond. 1995: 683-701.
Omran A. Bukhres, Jiansan Chen, Ahmed K. Elmagarmid, Xianging Liu, James G. Mullen. InterBase: A Multidatabase Prototype System. SIGMOD Conference 1993: 534-539.
Michael Stonebraker, Paul M. Aoki, Witold Litwin, Avi Pfeffer, Adam Sah, Jeff Sidell, Carl Staelin, Andrew Yu. Mariposa: A Wide-Area Distributed Database System. VLDB Journal 5(1): 48-63 (1996).
Rafi Ahmed, Joseph Albert, Weimin Du, William Kent, Witold Litwin, Ming-Chien Shan. An Overview of Pegasus. RIDE-IMS 1993: 273-277.
Marek Rusinkiewicz, Bogdan D. Czejdo. Query Transformation in a Multidatabase Environments Using a Universal Symbolic Manipulation System. ACM Conference on Computer Science 1989: 46-53.