Table of Contents: Sigmod 1996 Proceedings

All links on this page are to abstracts of papers. Some of the abstracts contain links to postscript of the papers. Some of the tutorial abstracts also contain a link to the full tutorial notes.

CONCEPT AND EXPERIENCE TRACK

SESSION: Data Mining (Tuesday 10:30 - 12:00)

Chair: Dennis Shasha (NYU)

Mining Quantitative Association Rules in Large Relational Tables.
Ramakrishnan Srikant (IBM Almaden Research Center) and Rakesh Agrawal (IBM Almaden Research Center): Page 1

Data Mining Using Two-Dimensional Optimized Association Rules: Scheme, Algorithms, and Visualization.
Takeshi Fukuda (IBM Tokyo Research Laboratory), Yasuhiko Morimoto (IBM Tokyo Research Laboratory), Shinichi Morishita (IBM Tokyo Research Laboratory), and Takeshi Tokuyama (IBM Tokyo Research Laboratory): Page 13

IDEA: Interactive Data Exploration and Analysis.
Peter G. Selfridge (AT&T Research), Divesh Srivastava (AT&T Research), and Lynn O. Wilson (AT&T): Page 24

SESSION: Reordering Optimization (Tuesday 10:30 - 12:00)

Chair: Kenneth A. Ross (Columbia University)

Rapid Bushy Join-order Optimization with Cartesian Products.
Bennet Vance (Oregon Graduate Institute) and David Maier (Oregon Graduate Institute): Page 35

SQL Query Optimization: Reordering for a General Class of Queries.
Piyush Goel (IBM Database Technology Institute) and Bala Iyer (IBM Database Technology Institute): Page 47

Fundamental Techniques for Order Optimization.
David E. Simmen (IBM Santa Teresa Laboratory), Eugene J. Shekita (IBM Almaden Research Center), and Timothy Malkemus (IBM Austin): Page 57

SESSION: Multimedia (Tuesday 2:00 -- 3:30)

Chair: Michael Ubell (Informix Corporation)

A Teradata Content-Based Multimedia Object Manager for Massively Parallel Architectures.
William O'Connell (Bell Laboratories), Ion T. Ieong (NCR), David Schrader (NCR), Cam Watson (NCR), Grace Au (NCR), Alexandros Biliris (AT&T Research), Susan Choo (NCR), Pierre Colin (NCR), Glenn Linderman (NCR), Euthimios Panagos (AT&T Research), June Wang (NCR), and Todd Walter (NCR): Page 68

Fault-tolerant Architectures for Continuous Media Servers.
Banu Ozden (Bell Laboratories), Rajeev Rastogi (Bell Laboratories), Prasant Shenoy (University of Texas, Austin), and Avi Silberschatz (Bell Laboratories): Page 79

Optimizing Queries over Multimedia Repositories.
Surajit Chaudhuri (HP Laboratories) and Luis Gravano (HP Laboratories and Stanford University): Page 91

SESSION: Clustering and Indexing (Tuesday 4:00 - 5:30)

Chair: Alexandros Biliris (AT&T Research)

BIRCH: An Efficient Data Clustering Method for Very Large Databases.
Tian Zhang (University of Wisconsin, Madison, Raghu Ramakrishnan (University of Wisconsin, Madison), and Miron Livny (University of Wisconsin, Madison): Page 103

On-line Reorganization of Sparsely-populated B+ trees.
Chendong Zou (Northeastern University) and Betty Salzberg (Northeastern University) : Page 115

Two Techniques for On-Line Index Modification in Shared Nothing Parallel Databases.
Kiran J. Achyutuni (Informix Corporation), Edward Omiecinski (Georgia Institute of Technology), and Shamkant B. Navathe (Georgia Institute of Technology): Page 125

SESSION: Integrating Systems (Wednesday 10:30 - 12:00)

Chair: Hans-Joerg Schek (ETH, Zurich)

Query Caching and Optimization in Distributed Mediator Systems.
Sibel Adali (University of Maryland), Kasim Selcuk Candan (University of Maryland), Yannis Papakonstantinou (Stanford University), and V.S. Subrahmanian (University of Maryland): Page 137

Performance Tradeoffs for Client-Server Query Processing.
Michael J. Franklin (University of Maryland), Bjorn Thor Jonsson (University of Maryland), and Donald Kossmann (University of Maryland): Page 149

Data Access for the Masses through OLE DB.
Jose Blakeley (Microsoft): Page 161

SESSION: Replication and Storage (Wednesday 10:30 - 12:00)

Chair: Jon Solworth (University of Illinois, Chicago)

The Dangers of Replication and a Solution.
Jim Gray (Microsoft), Pat Helland (Microsoft), Patrick O`Neil (University of Massachusetts), and Dennis Shasha (New York University): Page 173

Hot mirroring : A method of hiding parity update penalty and degradation during rebuilds for RAID5.
Kazuhiko Mogi (University of Tokyo) and Masaru Kitsuregawa (University of Tokyo): Page 183

Random I/O Scheduling in Online Tertiary Storage Systems.
Bruce K. Hillyer (Bell Laboratories) and Avi Silberschatz (Bell Laboratories): Page 195

SESSION: Decision Support (Wednesday 1:30 - 3:00)

Chair: Ted Johnson (University of Florida)

Implementing Data Cubes Efficiently.
Venky Harinarayan (Stanford University), Anand Rajaraman (Stanford University), and Jeffrey D. Ullman (Stanford University): Page 205

Providing Better Support for a Class of Decision Support Queries.
Sudhir Rao (Indiana University), Antonio Badia (Indiana University), and Dirk Van Gucht (Indiana University): Page 217

A Query Language for Multidimensional Arrays: Design, Implementation, and Optimization Techniques.
Leonid Libkin (Bell Laboratories), Rona Machlin (University of Pennsylvania), and Limsoon Wong (Institute of Systems Science): Page 228

SESSION: High Performance Algorithms (Wednesday 3:30 - 5:00)

Chair: Hans-Peter Kriegel (University of Munich)

A Super Scalar Sort Algorithm for RISC Processors.
Ramesh C. Agarwal (IBM Watson Research Center): Page 240

Spatial Hash-Joins.
Ming-Ling Lo (University of Michigan) and C. V. Ravishankar (University of Michigan): Page 247

Partition Based Spatial-Merge Join.
Jignesh M. Patel (University of Wisconsin, Madison) and David J. DeWitt (University of Wisconsin, Madison): Page 259

SESSION: Estimation (Wednesday 3:30 - 5:00)

Chair: Jeff Naughton (University of Wisconsin, Madison)

Bifocal Sampling for Skew-Resistant Join Size Estimation.
Sumit Ganguly (Rutgers University), Phillip B. Gibbons (Bell Laboratories), Yossi Matias (Bell Laboratories), and Avi Silberschatz (Bell Laboratories): Page 271

Estimating Alphanumeric Selectivity in the Presence of Wildcards.
P. Krishnan (Bell Laboratories), Jeffrey Scott Vitter (Duke University), and Bala Iyer (IBM Santa Teresa Laboratory): Page 282

Improved Histograms for Selectivity Estimation of Range Predicates.
Viswanath Poosala (University of Wisconsin, Madison), Yannis E. Ioannidis (University of Wisconsin, Madison), Peter J. Haas (IBM Almaden Research Center), and Eugene J. Shekita (IBM Almaden Research Center): Page 294

SESSION: Object-Oriented Systems (Thursday 10:15 - 12:15)

Chair: Malcolm Atkinson (University of Glasgow)

Structures for Manipulating Proposed Updates in Object-Oriented Databases.
Michael Doherty (University of Colorado), Richard Hull (University of Colorado), and Mohammed Rupawalla (University of Colorado): Page 306

Safe and Efficient Sharing of Persistent Objects in Thor.
Barbara Liskov (MIT), Atul Adya (MIT), Miguel Castro (MIT), Mark Day (Lotus), Sanjay Ghemawat (Digital Systems Research Lab.), Robert Gruber (AT&T Research), Umesh Maheshwari (MIT), Andrew C. Myers (MIT), and Liuba Shrira (MIT): Page 318

An Open Abstract-Object Storage System.
Stephen Blott (ETH, Zurich), Lukas Relly (ETH, Zurich), and Hans-Joerg Schek (ETH, Zurich): Page 330

Static Detection of Security Flaws in Object-Oriented Databases.
Keishi Tajima (Kyoto University): Page 341

SESSION: Resource Management (Thursday 10:15 - 12:15)

Chair: Krithi Ramamritham (University of Massachusetts, Amherst)

Goal-Oriented Buffer Management Revisited.
Kurt P. Brown (64k Inc.), Michael J. Carey (IBM Almaden Research Center), and Miron Livny (University of Wisconsin, Madison): Page 353

Multi-dimensional Resource Scheduling for Parallel Queries.
Minos N. Garofalakis (University of Wisconsin, Madison), and Yannis E. Ioannidis (University of Wisconsin, Madison): Page 365

Semi-automatic, Self-adaptive Control of Garbage Collection Rates in Object Databases.
Jonathan E. Cook (University of Colorado), Artur W. Klauser (University of Colorado), Alexander L. Wolf (University of Colorado), and and Benjamin G. Zorn (University of Colorado) : Page 377

Towards Effective and Efficient Free Space Management.
Mark L. McAuliffe (University of Wisconsin, Madison), Michael J. Carey (IBM Almaden Research Center), and Marvin H. Solomon (University of Wisconsin, Madison): Page 389

SESSION: Query Optimization (Thursday 10:15 - 12:15)

Chair: Xiaolei Qian (SRI)

Rule Languages and Internal Algebras for Rule-Based Optimizers.
Mitch Cherniack (Brown University) and Stanley B. Zdonik (Brown University): Page 401

Evaluating Queries with Generalized Path Expressions.
Vassilis Christophides (INRIA), Sophie Cluet (INRIA), and Guido Moerkotte (Aachen University): Page 413

Query Execution Techniques for Caching Expensive Methods.
Joseph M. Hellerstein (University of California, Berkeley), and Jeffrey F. Naughton (University of Wisconsin, Madison): Page 423

Cost-Based Optimization for Magic: Algebra and Implementation.
Praveen Seshadri (University of Wisconsin, Madison), Joseph M. Hellerstein (University of California, Berkeley), Hamid Pirahesh (IBM Almaden Research Center), T.Y. Cliff Leung (IBM Santa Teresa Laboratory), Raghu Ramakrishnan (University of Wisconsin, Madison), Divesh Srivastava (AT&T Research), Peter J. Stuckey (University of Melbourne), and S. Sudarshan (Indian Institute of Technology): Page 435

SESSION: Views (Thursday 1:45 - 3:45)

Chair: Laks Lakshmanan (Concordia University)

Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time.
Kenneth A. Ross (Columbia University), Divesh Srivastava (AT&T Research), and S. Sudarshan (Indian Institute of Technology): Page 447

Maintaining Database Consistency in Presence of Value Dependencies in Multidatabase Systems .
Claire Morpain (LSI Laboratory), Michele Cart (LSI Laboratory), Jean Ferrie (LSI Laboratory), and Jean-Francois Pons (LSI Laboratory): Page 459

Algorithms for Deferred View Maintenance.
Latha S. Colby (Bell Laboratories), Timothy Griffin (Bell Laboratories), Leonid Libkin (Bell Laboratories), Inderpal Singh Mumick (Bell Laboratories), and Howard Trickey (Bell Laboratories): Page 469

A framework for supporting data integration using the materialized and virtual approaches.
Richard Hull (University of Colorado) and Gang Zhou (University of Southern California and University of Colorado): Page 481

SESSION: New Applications (Thursday 1:45 - 3:45)

Chair: Dean Daniels (Oracle)

Change Detection in Hierarchically Structured Information.
Sudarshan S. Chawathe (Stanford University), Anand Rajaraman (Stanford University), Hector Garcia-Molina (Stanford University), and Jennifer Widom (Stanford University) : Page 493

A Query Language and Optimization Techniques for Unstructured Data.
Peter Buneman (University of Pennsylvania), Susan Davidson (University of Pennsylvania), Gerd Hillebrand (University of Pennsylvania and Karlsruhe University), and Dan Suciu (AT&T Research): Page 505

Is GUI Programming a Database Research Problem?.
Nita Goyal (HP Laboratories), Charles Hoch (HP Laboratories), Ravi Krishnamurthy (HP Laboratories), Brian Meckler (HP Laboratories), and Michael Suckow (HP Laboratories): Page 517

Accessing Relational Databases from the World Wide Web.
Tam Nguyen (IBM Santa Teresa Laboratory) and V. Srinivasan (IBM Santa Teresa Laboratory): Page 529

TUTORIALS:

The Ins and Outs (and everything in between) of Data Warehousing.
Donovan Schneider (Red Brick Systems) and Phil Fernandez (Red Brick Systems): Page 541

Repository System Engineering.
Philip A. Bernstein (Microsoft): Page 542

Databases and Visualization.
Daniel Keim (University of Munich): Page 543

State of the Art in Workflow Management Research and Products.
C. Mohan (IBM Almaden Research Center): Page 544

Data Mining Techniques.
Jiawei Han (Simon Fraser University): Page 545

DEMOS:

Thinksheet: a tool for tailoring complex documents.
Peter Piatko (New York University), Roman Yangarber (New York University), Daoi Lin (New York University), and Dennis Shasha (New York University) : Page 546

HyperStorM - Administering Structured Documents Using Object-Oriented Database Technology.
Klemens Boehm (GMD - Integrated Publication and Information Systems Institute) and Karl Aberer (GMD - Integrated Publication and Information Systems Institute) : Page 547

DBSim: A Simulation Tool for Predicting Database Performance.
Mike Lefler (PRC Inc.), Mark Stokrp (PRC Inc.), and Craig Wong (PRC Inc.): Page 548

LORE: A Lightweight Object REpository for Semistructured Data.
Dallan Quass, Jennifer Widom, Roy Goldman, Kevin Haas, Qingshan Luo, Jason McHugh, Svetlozar Nestorov, Anand Rajaraman, Hugo Rivero, Serge Abiteboul, Jeffrey D. Ullman, and Janet Wiener (Stanford University): Page 549

DBMiner: Interactive Mining of Multiple-Level Knowledge in Relational Databases.
Jiawei Han, Yongjian Fu, Wei Wang, Jenny Chiang, Osmar R. Zaiane, and Krzysztof Koperski (Simon Fraser University): Page 550

Prospector: A Content-Based Multimedia Server for Massively Parallel Architectures.
Grace Au (NCR), Alexandros Biliris (AT&T Research), Homer Chen (Bell Laboratories), Susan Choo (NCR), Kicha Ganapathy (Bell Laboratories), Glenn Linderman (NCR), William O'Connell (Bell Laboratories), Euthimios Panagos (AT&T Research), and David Schrader (NCR): Page 551

METU Interoperable Database System.
Asuman Dogac, Ugur Halici, Ebru Kilic, Gokhan Ozhan, Fatma Ozcan, Sena Nural, Cevdet Dengi, Sema Mancuhan, Budak Arpinar, Pinar Koksal, and Cem Evrendilek (Middle East Technical University, Turkey) : Page 552

SONAR: System for Optimized Numeric Association Rules.
Takeshi Fukuda (IBM Tokyo Research Laboratory), Yasuhiko Morimoto (IBM Tokyo Research Laboratory), Shinichi Morishita (IBM Tokyo Research Laboratory), and Takeshi Tokuyama (IBM Tokyo Research Laboratory): Page 553

CapBasED-AMS: A Capability Based and Event-driven Activity Management System.
Patrick C. K. Hung (Hong Kong University of Science and Technology), Helen P. Yeung (Hong Kong University of Science and Technology), and Kamalakar Karlapalem (Hong Kong University of Science and Technology): Page 554

The MultiView Project: Object-Oriented View Technology and Applications.
Elke Rundensteiner, Harumi A. Kuno, Young-Gook Ra, Viviane Crestana-Taube, Matthew Jones, and Pedro Marron (University of Michigan, Ann Arbor): Page 555

BeSS: Storage Support for Interactive Visualization Systems.
Alexandros Biliris (AT&T Research), Thomas Funkhouser (Bell Laboratories), William O'Connell (Bell Laboratories), and Euthimios Panagos (AT&T Research): Page 556

The Garlic Project.
Mary Tork Roth, Manish Arya, Laura M. Haas, Michael J. Carey, William Cody, Ron Fagin, Peter M. Schwarz, John Thomas, and Edward L. Wimmers (IBM Almaden Research Center): Page 557

Author Index: Page 558

Inderpal Singh Mumick, mumick@research.att.com