sigmod_1999_elementary.txt

利用lwp：：get写的

Attributes in a data warehouse fact table typically have hierarchies defined on them (by means of auxiliary dimension tables). The product of the dimensional hierarchy levels forms a lattice and leads to a natural notion of query classes. Optimal clustering in this context is a combinatorially explosive problem with a huge search space (doubly exponential in number of hierarchy levels). We identify an important subclass of clustering strategies called lattice paths, and present a dynamic programming algorithm for finding the optimal lattice path clustering, in time linear in the lattice size. We additionally propose a technique called snaking, which when applied to a lattice path, always reduces its cost. For a representative class of star schemas, we show that for every workload, there is a snaked lattice path which is globally optimal. Further, we prove that the clustering obtained by applying snaking to the optimal lattice path is never much worse than the globally optimal snaked lattice path clustering. We complement our analyses and validate the practical utility of our techniques with experiments using TPC-D benchmark data.</abstract></paper><paper><title>OPTICS: ordering points to identify the clustering structure</title><author><AuthorName>Mihael Ankerst</AuthorName><institute><InstituteName>Institute for Computer Science, University of Munich, Oettingenstr, 67, D-80538 Munich, Germany</InstituteName><country></country></institute></author><author><AuthorName>Markus M. Breunig</AuthorName><institute><InstituteName>Institute for Computer Science, University of Munich, Oettingenstr, 67, D-80538 Munich, Germany</InstituteName><country></country></institute></author><author><AuthorName>Hans-Peter Kriegel</AuthorName><institute><InstituteName>Institute for Computer Science, University of Munich, Oettingenstr, 67, D-80538 Munich, Germany</InstituteName><country></country></institute></author><author><AuthorName>J&amp;#246;rg Sander</AuthorName><institute><InstituteName>Institute for Computer Science, University of Munich, Oettingenstr, 67, D-80538 Munich, Germany</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Management of Data</conference><citation><name>Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.94-105, June 01-04, 1998, Seattle, Washington, United States</name><name>Ankerst M., Keim D. A., Kriegel H.-P.: "'Circle Segments': A Technique for Visually Exploring Large Multidimensional Data Sets", Proc. Visualization'96, Hot Topic Session, San Francisco, CA, 1996.</name><name>Stefan Berchtold , Daniel A. Keim , Hans-Peter Kriegel, The X-tree: An Index Structure for High-Dimensional Data, Proceedings of the 22th International Conference on Very Large Data Bases, p.28-39, September 03-06, 1996</name><name>Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States</name><name>Paolo Ciaccia , Marco Patella , Pavel Zezula, M-tree: An Efficient Access Method for Similarity Search in Metric Spaces, Proceedings of the 23rd International Conference on Very Large Data Bases, p.426-435, August 25-29, 1997</name><name>Ester M., Kriegel H.-P., Sander J., Xu X.: "A Density- Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise", Proc. 2nd Int. Conf. on Knowledge Discovery and Data Mining, Portland, OR, AAAI Press, 1996, pp. 226-231.</name><name>Martin Ester , Hans-Peter Kriegel , J&amp;#246;rg Sander , Michael Wimmer , Xiaowei Xu, Incremental Clustering for Mining in a Data Warehousing Environment, Proceedings of the 24rd International Conference on Very Large Data Bases, p.323-333, August 24-27, 1998</name><name>Martin Ester , Hans-Peter Kriegel , Xiaowei Xu, Knowledge Discovery in Large Spatial Databases: Focusing Techniques for Efficient Class Identification, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.67-82, August 06-09, 1995</name><name>Grossman A., Morlet J.: "Decomposition oj'functions into wavelets of constant shapes and related tr~msforms". Mathematics and Physics: Lectures on Recent Restdts, World Scientific, Singapore, 1985.</name><name>Sudipto Guha , Rajeev Rastogi , Kyuseok Shim, CURE: an efficient clustering algorithm for large databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.73-84, June 01-04, 1998, Seattle, Washington, United States</name><name>Hinneburg A., Keim D.: "An Efficient Approa~:h to Clustering in Large Multimedia Databases with Noise"~, Proc. 4th Int. Conf. on Knowledge Discovery &amp; Data Milling, New York City, NY, 1998.</name><name>Hattori K., Torii Y.: "Effective algorithms for Jhe nearest neighbor method in the clustering problem", Patt~.,rn Recognition, 1993, Vol. 26, No. 5, pp. 741-746.</name><name>Huang Z.: "A Fast Clustering Algorithm to C,'uster Very Large Categorical Data Sets in Data Mining", 1)roc. SIG- OD Workshop on Research Issues on Data Mining and Knowledge Discovery, Tech. Report 97-07, UBC, Dept. of CS, 1997.</name><name>Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988</name><name>Daniel A. Keim, Pixel-oriented database visualizations, ACM SIGMOD Record, v.25 n.4, p.35-39, Dec. 1996</name><name>Daniel A. Keim, databases and visualization, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.543, June 04-06, 1996, Montreal, Quebec, Canada</name><name>Edwin M. Knorr , Raymond T. Ng, Finding Aggregate Proximity Relationships and Commonalities in Spatial Data Mining, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.884-897, December 1996</name><name>Kaufman L., Rousseeuw E J.: "Finding GrouFs in Data: An Introduction to Cluster Analysis", John Wiley &amp; Sons, 1990.</name><name>MacQueen, J.: "Some Methods for Classification and Analysis of Multivariate Observations", 5th Berkeley Synap. Math. Statist. Prob., Vol. 1, pp. 281-297.</name><name>Raymond T. Ng , Jiawei Han, Efficient and Effective Clustering Methods for Spatial Data Mining, Proceedings of the 20th International Conference on Very Large Data Bases, p.144-155, September 12-15, 1994</name><name>Press W. H.,Teukolsky S. A., Vetterling W. T., Flannery B. E: "Numerical Recipes in C", 2nd ed., Cambridl,ye University Press, 1992.</name><name>J. A. Richards, Remote Sensing Digital Image Analysis: An Introduction, Springer-Verlag New York, Inc., Secaucus, NJ, 1993</name><name>Schikuta E.: "'Grid clustering: An efficient hierarchical clustering method for very large data sets". Proc. 13th Int. Conf. on Pattern Recognition, Vol 2, 1996, pp. 101-105.</name><name>Erich Schikuta , Martin Erhart, The BANG-Clustering System: Grid-Based Data Analysis, Proceedings of the Second International Symposium on Advances in Intelligent Data Analysis, Reasoning about Data, p.513-524, August 04-06, 1997</name><name>Gholamhosein Sheikholeslami , Surojit Chatterjee , Aidong Zhang, WaveCluster: A Multi-Resolution Clustering Approach for Very Large Spatial Databases, Proceedings of the 24rd International Conference on Very Large Data Bases, p.428-439, August 24-27, 1998</name><name>Sibson R.: "SLINK: an optimally efficient alggrithm for the single-link cluster method".The Comp. Journal, Vol. ]'~ 6, No. 1, 1973, pp. 30-34.</name><name>Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: an efficient data clustering method for very large databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.103-114, June 04-06, 1996, Montreal, Quebec, Canada</name></citation><abstract>Cluster analysis is a primary method for database mining. It is either used as a stand-alone tool to get insight into the distribution of a data set, e.g. to focus further analysis and data processing, or as a preprocessing step for other algorithms operating on the detected clusters. Almost all of the well-known clustering algorithms require input parameters which are hard to determine but have a significant influence on the clustering result. Furthermore, for many real-data sets there does not even exist a global parameter setting for which the result of the clustering algorithm describes the intrinsic clustering structure accurately. We introduce a new algorithm for the purpose of cluster analysis which does not produce a clustering of a data set explicitly; but instead creates an augmented ordering of the database representing its density-based clustering structure. This cluster-ordering contains information which is equivalent to the density-based clusterings corresponding to a broad range of parameter settings. It is a versatile basis for both automatic and interactive cluster analysis. We show how to automatically and efficiently extract not only 'traditional' clustering information (e.g. representative points, arbitrary shaped clusters), but also the intrinsic clustering structure. For medium sized data sets, the cluster-ordering can be represented graphically and for very large data sets, we introduce an appropriate visualization technique. Both are suitable for interactive exploration of the intrinsic clustering structure offering additional insights into the distribution and correlation of the data.</abstract></paper><paper><title>Fast algorithms for projected clustering</title><author><AuthorName>Charu C. Aggarwal</AuthorName><institute><InstituteName>IBM T. J. Watson Research Center, Yorktown Heights, NY</InstituteName><country></country></institute></author><author><AuthorName>Joel L. Wolf</AuthorName><institute><InstituteName>IBM T. J. Watson Research Center, Yorktown Heights, NY</InstituteName><country></country></institute></author><author><AuthorName>Philip S. Yu</AuthorName><institute><InstituteName>IBM T. J. Watson Research Center, Yorktown Heights, NY</InstituteName><country></country></institute></author><author><AuthorName>Cecilia Procopiuc</AuthorName><institute><InstituteName>Duke University, Durham, NC</InstituteName><country></country></institute></author><author><AuthorName>Jong Soo Park</AuthorName><institute><InstituteName>Sungshin Women's University, Seoul, Korea</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Management of Data</conference><citation><name>Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.94-105, June 01-04, 1998, Seattle, Washington, United States</name><name>D. Hand, Order Statistics. John Wiley and Sons, New York, 1981.</name><name>M. Berger, I. Rigoutsos. An Algorithm for Point Clustering and Grid Generation. IEEE Transactions on Systems, Man and Cybernetics, Vol. 21, 5:1278-1286, 1991.</name><name>M. R. Brito, E. Chavez, A. Quiroz, J. Yukich. Connectivity of the Mutual k-Nearest-Neighbor Graph for Clustering and Outlier Detection. Siatis~ics and Probability Letters, 35 (1997) pages 33-42.</name><name>P. Cheeseman, j. Kelly, S. Matthew. AutoClass: A Bayesian Classification System. Proceedings of ~he 5~h International Conference on Machine Learning, Morgan Kaufmann, June 1988.</name><name>R. Dubes, A. Jain. Clustering Meihodologies in Exploratory Data Analysis. Advances in Computers, Edited by M. Yovits, Vol. 19, Academic Press, New York, 1980.</name><name>M. Ester, H.-P. Kriegel, X. Xu. A Database Interface for Clu.,~tering in Large Spatial Databases. Proceedings of the first International Conference on Knowledge Discovery and Data Mining, 1995.</name><name>Martin Ester , Hans-Peter Kriegel , Xiaowei Xu, Knowledge Discovery in Large Spatial Databases: Focusing Techniques for Efficient Class Identification, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.67-82, August 06-09, 1995</name><name>M. Ester, H.-P. Kriegel, J. Sander, X. Xu. A Density Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. Proceedings of ~he 2nd International Conference on Knowledge Discovery in Databases and Da~a Mining, Portland, Oregon, August 1.995.</name><name>Upendra Shardanand , Pattie Maes, Social information filtering: algorithms for automating &amp;ldquo;word of mouth&amp;rdquo;, Proceedings of the SIGCHI conference on Human factors in computing systems, p.210-217, May 07-11, 1995, Denver, Colorado, United States</name><name>Douglas H. Fisher, Knowledge Acquisition Via Incremental Conceptual Clustering, Machine Learning, v.2 n.2, p.139-172, September 1987</name><name>D. Fisher. Optimization and Simplification of Hierarchical Clusters. Proceedings of ~he International Conference on Knowledge Discovery and Data Mining, August 1995.</name><name>David Gibson , Jon M. Kleinberg , Prabhakar Raghavan, Clustering Categorical Data: An Approach Based on Dynamical Systems, Proceedings of the 24rd International Conference on Very Large Data Bases, p.311-322, August 24-27, 1998</name><name>T. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, Vol. 38, pp. 293-306, 1985.</name><name>Sudipto Guha , Rajeev Rastogi , Kyuseok Shim, CURE: an efficient clustering algorithm for large databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.73-84, June 01-04, 1998, Seattle, Washington, United States</name><name>Toshihide Ibaraki , Naoki Katoh, Resource allocation problems: algorithmic approaches, MIT Press, Cambridge, MA, 1988</name><name>Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988</name><name>L. Kaufman, P. Rousseeuw. Finding Groups in Data- An Introduction to Cluster Analysis. Wiley Series in Probability and Mathematical Statistics, 1990.</name><name>R. Kohavi, D. Sommerfield. Feature Subset Selection Using the Wrapper Method" Overfitting and Dynamic Search Space Topology. Proceedings of ~he First International Conference on Knowledge Discovery and Data Mining, 1995.</name><name>R. Lee. Clustering Analysis and its applicagions. Advances in Information Systems Science, edited by :I. Toum, Vol. 8, pp. 169-292, Plenum Press, New York, 1981.</name><name>Raymond T. Ng , Jiawei Han, Efficient and Effective Clustering Methods for Spatial Data Mining, Proceedings of the 20th International Conference on Very Large Data Bases, p.144-155, September 12-15, 1994</name><name>Stefan Berchtold , Christian B&amp;#246;hm , Daniel A. Keim , Hans-Peter Kriegel, A cost model for nearest neighbor search in high-dimensional data space, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.78-86, May 11-15, 1997, Tucson, Arizona, United States</name><name>S. Wharton. A Generalized Histogram Clustering for Multidimensional Image Data. Pattern Recognition, Vol. 16, No. 2: pp. 193-199, 1983.</name><name>Xiaowei Xu , Martin Ester , Hans-Peter Kriegel , J&amp;#246;rg Sander, A Distribution-Based Clustering Algorithm for Mining in Large Spatial Databases, Proceedings of the Fourteenth International Conference on Data Engineering, p.324-331, February 23-27, 1998</name><name>Mohamed Za&amp;#239;t , Hammou Messatfa, A comparative study of clustering methods, Future Generation Computer Systems, v.13 n.2-3, p.149-159, Nov. 1997</name><name>Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: an efficient data clustering method for very large databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.103-114, June 04-06, 1996, Montreal, Quebec, Canada</name></citation><abstract>The clustering problem is well known in the database literature for its numerous applications in problems such as customer segmentation, classification and trend analysis. Unfortunately, all known algorithms tend to break down in high dimensional spaces because of the inherent sparsity of the points. In such high dimensional spaces not all dimensions may be relevant to a given cluster. One way of handling this is to pick the closely correlated dimensions and find clusters in the corresponding subspace. Traditional feature selection algorithms attempt to achieve this. The weakness of this approach is that in typical high dimensional data mining applications different sets of points may cluster better for different subsets of dimensions. The number of dimensions in each such cluster-specific subspace may also vary. Hence, it may be impossible to find a single small subset of dimensions for all the clusters. We therefore discuss a generalization of the clustering problem, referred to as the projected clustering problem, in which the subsets of dimensions selected are specific to the clusters themselves. We develop an algorithmic framework for solving the projected clustering problem, and test its performance on synthetic data.</abstract></paper><paper><title>Logical logging to extend recovery to new domains</title><author><AuthorName>David Lomet</AuthorName><institute><InstituteName>Microsoft Research, Redmond, WA</InstituteName><country></country></institute></author><author><AuthorName>Mark Tuttle</AuthorName><institute><InstituteName>Compaq Cambridge Research Lab, Cambridge, MA</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Management of Data</conference><citation><name>Bernstein, P. Goodman, N. and Hadzilacos, V. Recover~ Algorithms for Database Systems. IFIP World Computer Congres:;, (Sept. 83) 799-807.</name><name>Crus, R. Data recovery in IBM Database 2. IBM Systems Journal 23,2 (1984) 178-188.</name><name>Jim Gray , Paul McJones , Mike Blasgen , Bruce Lindsay , Raymond Lorie , Tom Price , Franco Putzolu , Irving Traiger, The Recovery Manager of the System R Database Manager, ACM Computing Surveys (CSUR), v.13 n.2, p.223-242, June 1981</name><name>Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992</name><name>Theo Haerder , Andreas Reuter, Principles of transaction-oriented database recovery, ACM Computing Surveys (CSUR), v.15 n.4, p.287-317, December 1983</name><name>Vijay Kumar , Meichun Hsu, Recovery mechanisms in database systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998</name><name>David B. Lomet, Persistent Applications Using Generalized Redo Recovery, Proceedings of the Fourteenth International Conference on Data Engineering, p.154-163, February 23-27, 1998</name><name>David B. Lomet , Mark R. Tuttle, Redo Recovery after System Crashes, Proceedings of the 21th International Conference on Very Large Data Bases, p.457-468, September 11-15, 1995</name><name>Lomet, D. and Tuttle, M. A Formal Treatment of Redo Recovery with Pragmatic Implications. Tech. Report (in preparatioJa).</name><name>Lomet, D. Media Recovery When Using Logical Log Operations. (submitted for publication).</name><name>C. Mohan , Don Haderle , Bruce Lindsay , Hamid Pirahesh , Peter Schwarz, ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging, ACM Transactions on Database Systems (TODS), v.17 n.1, p.94-162, March 1992</name><name>Rob Strom , Shaula Yemini, Optimistic recovery in distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.3, p.204-226, Aug. 1985</name></citation><abstract>Recovery can be extended to new domains at reduced logging cost by exploiting &amp;ldquo;logical&amp;rdquo; log operations. During recovery, a logical log operation may read data values from any recoverable object, not solely from values on the log or from the updated object. Hence, we needn't log these values, a substantial saving. In [8], we developed a redo recovery theory that deals with general log operations and proved that the stable database remains recoverable when it is explained in terms of an installation graph. This graph was used to derived a write graph that determines a flush order for cached objects that ensures that the database remains recoverable. In this paper, we introduce a refined write graph that permits more flexible cache management that flushes smaller sets of objects. Using this write graph, we show how: (i) the cache manager can inject its own operations to break up atomic flush sets; and (ii) the recovery process can avoid redoing operations whose effects aren't needed by exploiting generalized recovery LSNs. These advances permit more cost-effective recovery for, e.g., files and applications.</abstract></paper><paper><title>Efficient concurrency control for broadcast environments</title><author><AuthorName>Jayavel Shanmugasundaram</AuthorName><institute><InstituteName>University of Wisconsin-Madison and University of Massachusetts, Amherst</InstituteName><country></country></institute></author><author><AuthorName>Arvind Nithrakashyap</AuthorName><institute><InstituteName>University of Massachusetts, Amherst</InstituteName><country></country></institute></author><author><AuthorName>Rajendran Sivasankaran</AuthorName><institute><InstituteName>University of Massachusetts, Amherst</InstituteName><country></country></institute></author><author><AuthorName>Krithi Ramamritham</AuthorName><institute><InstituteName>University of Massachusetts, Amherst and Indian Institute of Technology, Bombay</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Management of Data</conference><citation><name>Swarup Acharya , Rafael Alonso , Michael Franklin , Stanley Zdonik, Broadcast disks: data management for asymmetric communication environments, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.199-210, May 22-25, 1995, San Jose, California, United States</name><name>Swarup Acharya , Michael J. Franklin , Stanley B. Zdonik, Disseminating Updates on Broadcast Disks, Proceedings of the 22th International Conference on Very Large Data Bases, p.354-365, September 03-06, 1996</name><name>Rafael Alonso , Daniel Barbara , Hector Garcia-Molina, Data caching issues in an information retrieval system, ACM Transactions on Database Systems (TODS), v.15 n.3, p.359-384, Sept. 1990</name><name>Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987</name><name>Paul M. Bober , Michael J. Carey, Multiversion Query Locking, Proceedings of the 18th International Conference on Very Large Data Bases, p.497-510, August 23-27, 1992</name><name>P.M. Bober and M.J. Carey. Multiversion Query Locking. Computer Science Technical Report TR 1160, University of Wisconsin-Madison, 1993.</name><name>Michael J. Carey , Michael J. Franklin , Miron Livny , Eugene J. Shekita, Data caching tradeoffs in client-server DBMS architectures, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.357-366, May 29-31, 1991, Denver, Colorado, United States</name><name>Michael Jay Franklin, Caching and memory management in client-server database systems, University of Wisconsin at Madison, Madison, WI, 1993</name><name>Sreenivas Gukal , Edward Omiecinski, Transient versioning for consistency and concurrency in client-server systems, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.274-287, December 18-20, 1996, Miami Beach, Florida, United States</name><name>Gary Herman , K. C. Lee , Abel Weinrib, The datacycle architecture for very high throughput database systems, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.97-103, May 27-29, 1987, San Francisco, California, United States</name><name>Tomasz Imielinski , B. R. Badrinath, Mobile wireless computing: challenges in data management, Communications of the ACM, v.37 n.10, p.18-28, Oct. 1994</name><name>Suresh Kumar , Eng-Kee Kwang , Divyakant Agrawal, Caprera: An Activity Framework for Transaction Processing on Wide-Area Networks, Proceedings of the 23rd International Conference on Very Large Data Bases, p.585-589, August 25-29, 1997</name><name>Hector Garcia-Molina , Gio Wiederhold, Read-only transactions in a distributed database, ACM Transactions on Database Systems (TODS), v.7 n.2, p.209-234, June 1982</name><name>Brian Oki , Manfred Pfluegl , Alex Siegel , Dale Skeen, The Information Bus: an architecture for extensible distributed systems, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.58-68, December 05-08, 1993, Asheville, North Carolina, United States</name><name>Christos Papadimitriou, The theory of database concurrency control, Computer Science Press, Inc., New York, NY, 1986</name><name>Scalable Processing of Read-Only Transactions in Broadcast Push, Proceedings of the 19th IEEE International Conference on Distributed Computing Systems, p.432, May 31-June 04, 1999</name><name>Krithi Ramamritham , Panos K. Chrysanthis, A taxonomy of correctness criteria in database applications, The VLDB Journal &amp;mdash; The International Journal on Very Large Data Bases, v.5 n.1, p.085-097, January 1996</name><name>J. Shanmugasundaram, et. al. Efficiellt Concurrency Control for Broadcast Environmqmts Univ. of Massachusetts Technical Report 199g.</name><name>S. Shekar and D. Liu. Genesis and Advanced Traveler Information Systems (ATIS): Killer App]tications for Mobile Computing. MOBID.~.TA Workshop, New Jersey, 1994.</name><name>White Paper, http://www.vitria.com.</name><name>Yongdong Wang , Lawrence A. Rowe, Cache consistency and concurrency control in a client/server DBMS architecture, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.367-376, May 29-31, 1991, Denver, Colorado, United States</name><name>William E. Weihl, Distributed version management for read-only actions, IEEE Transactions on Software Engineering, v.13 n.1, p.55-64, Jan. 1987</name><name>Kevin Wilkinson , Marie-Anne Neitmat, Maintaining consistency of client-cached data, Proceedings of the sixteenth international conference on Very large databases, p.122-134, September 1990, Brisbane, Australia</name><name>Ping Xuan , Subhabrata Sen , Oscar Gonzalez , Jesus Fernandez , Krithi Ramamritham, Broadcast on Demand: Efficient and Timely Dissemination of Data in Mobile Environments, Proceedings of the 3rd IEEE Real-Time Technology and Applications Symposium (RTAS '97), p.38, June 09-11, 1997</name></citation><abstract>A crucial consideration in environments where data is broadcast to clients is the low bandwidth available for clients to communicate with servers. Advanced applications in such environments do need to read data that is mutually consistent as well as current. However, given the asymmetric communication capabilities and the needs of clients in mobile environments, traditional serializability-based approaches are too restrictive, unnecessary, and impractical. We thus propose the use of a weaker correctness criterion called update consistency and outline mechanisms based on this criterion that ensure (1) the mutual consistency of data maintained by the server and read by clients, and (2) the currency of data read by clients. Using these mechanisms, clients can obtain data that is current and mutually consistent &amp;ldquo;off the air&amp;rdquo;, i.e., without contacting the server to, say, obtain locks. Experimental results show a substantial reduction in response times as compared to existing (serializability-based) approaches. A further attractive feature of the approach is that if caching is possible at a client, weaker forms of currency can be obtained while still satisfying the mutual consistency of data.</abstract></paper><paper><title>Update propagation protocols for replicated databates</title><author><AuthorName>Yuri Breitbart</AuthorName><institute><InstituteName>Bell Laboratories, Murray Hill, NJ</InstituteName><country></country></institute></author><author><AuthorName>Raghavan Komondoor</AuthorName><institute><InstituteName>University Of Wisconsin, Madison, WI</InstituteName><country></country></institute></author><author><AuthorName>Rajeev Rastogi</AuthorName><institute><InstituteName>Bell Laboratories, Murray Hill, NJ</InstituteName><country></country></institute></author><author><AuthorName>S. Seshadri</AuthorName><institute><InstituteName>Bell Laboratories, Murray Hill, NJ</InstituteName><country></country></institute></author><author><AuthorName>Avi Silberschatz</AuthorName><institute><InstituteName>Bell Laboratories, Murray Hill, NJ</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Management of Data</conference><citation><name>Todd Anderson , Yuri Breitbart , Henry F. Korth , Avishai Wool, Replication, consistency, and practicality: are these mutually exclusive?, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.484-495, June 01-04, 1998, Seattle, Washington, United States</name><name>Yuri Breitbart , Henry F. Korth, Replication and consistency: being lazy helps sometimes, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.173-184, May 11-15, 1997, Tucson, Arizona, United States</name><name>Yuri Breitbart, Raghavan Komondoor, Rajeev Rastogi, S. Seshadri, and Avi Silberschatz. Update propagation algorithms for replicated database systems. Technical R,,~port BL0112370-981028-11TM, Bell Labs, Oc~:ober 1998.</name><name>Philip Bohannon , Daniel Lieuwen , Rajeev Rastogi , Avi Silberschatz , S. Seshadri , S. Sudarshan, The Architecture of the Dal&amp;iacute; Main-Memory Storage Manager, Multimedia Tools and Applications, v.4 n.2, p.115-151, March 1997</name><name>Parvathi Chundi , Daniel J. Rosenkrantz , S. S. Ravi, Deferred Updates and Data Placement in Distributed Databases, Proceedings of the Twelfth International Conference on Data Engineering, p.469-476, February 26-March 01, 1996</name><name>Guy Even , Joseph (Seffi) Naor , Satish Rao , Baruch Schieber, Fast approximate graph partitioning algorithms, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.639-648, January 05-07, 1997, New Orleans, Louisiana, United States</name><name>J. Gray, E Homan, H. Korth, and R. Oberrnack. A strawman analysis of the probability of wait and deadlock. Technical Report RJ2131, ]BM San Jose Research Laboratory, 1981.</name><name>Jim Gray , Pat Helland , Patrick O'Neil , Dennis Shasha, The dangers of replication and a solution, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.173-182, June 04-06, 1996, Montreal, Quebec, Canada</name><name>Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman &amp; Co., New York, NY, 1979</name><name>T. Leighton, F. Makedon, and S. TragouJas. Approximation algorithms for vlsi partitioxfing problems. In IEEE International Symposiun~ on Circuits and Systems, 1990.</name><name>Abraham Silberschatz , Zvi Kedem, Consistency in Hierarchical Database Systems, Journal of the ACM (JACM), v.27 n.1, p.72-80, Jan. 1980</name><name>Horst D. Simon , Shang-Hua Teng, How Good is Recursive Bisection?, SIAM Journal on Scientific Computing, v.18 n.5, p.1436-1445, Sept. 1997</name></citation><abstract>Replication is often used in many distributed systems to provide a higher level of performance, reliability and availability. Lazy replica update protocols, which propagate updates to replicas through independent transactions after the original transaction commits, have become popular with database vendors due to their superior performance characteristics. However, if lazy protocols are used indiscriminately, they can result in non-serializable executions. In this paper, we propose two new lazy update protocols that guarantee serializability but impose a much weaker requirement on data placement than earlier protocols. Further, many naturally occurring distributed systems, like distributed data warehouses, satisfy this requirement. We also extend our lazy update protocols to eliminate all requirements on data placement. The extension is a hybrid protocol that propagates as many updates as possible in a lazy fashion. We implemented our protocols on the Datablitz database system product developed at Bell Labs. We also conducted an extensive performance study which shows that our protocols outperform existing protocols over a wide range of workloads.</abstract></paper><paper><title>Belief reasoning in MLS deductive databases</title><author><AuthorName>Hasan M. Jamil</AuthorName><institute><InstituteName>Department of Computer Science, Mississippi State University</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Management of Data</conference><citation><name>D. E. Bell and L. J. La Padula. Secure computer systems: Unified exposition and multics interpretation. Technical Report ESD-TR-75-.306, The MITRE Corporation, Bedford, MA, March 1976.</name><name>Piero A. Bonatti , Sarit Kraus , V. s. Subrahmanian, Foundations of Secure Deductive Databases, IEEE Transactions on Knowledge and Data Engineering, v.7 n.3, p.406-422, June 1995</name><name>M. Bugliesi. A declarative view of inheritance in logic programming, in K. Apt, editor, Proc. Joint Int. Conference and Symposium on Logic Programming, pages 113-130. The MIT Press, 1992.</name><name>Michele Bugliesi , Hasan M. Jamil, A Logic for Encapsulation in Object Oriented Languages, Proceedings of the 6th International Symposium on Programming Language Implementation and Logic Programming, p.215-229, September 14-16, 1994</name><name>Michele Bugliesi , Hasan M. Jamil, A Stable Model Semantics for Behavioral Inheritance in Deductive Object Oriented Languages, Proceedings of the 5th International Conference on Database Theory, p.222-237, January 11-13, 1995</name><name>K. Sel&amp;#231;uk Candan , Sushil Jajodia , V. S. Subrahmanian, Secure Mediated Databases, Proceedings of the Twelfth International Conference on Data Engineering, p.28-37, February 26-March 01, 1996</name><name>Fr&amp;#233;d&amp;#233;ric Cuppens, Querying a Multilevel Database: A Logical Analysis, Proceedings of the 22th International Conference on Very Large Data Bases, p.484-494, September 03-06, 1996</name><name>D. E. Denning, T. F. Lunt, R. R. Schell, M. Heckman, and W. R. Shockley. A multilevel relational data model. In Proc. of the IEEE Symposium on Security and Privacy, pages 220-234. IEEE Computer Society Press, 1987.</name><name>D. Chimenti , R. Gamboa , R. Krishnamurthy , S. Naqvi , S. Tsur , C. Zaniolo, The LDL System Prototype, IEEE Transactions on Kn