Database Seminar Series (2010-2011)

Database query processing traditionally relies on three alternative join algorithms: index nested loops join exploits an index on its inner input, merge join exploits sorted inputs, and hash join exploits differences in the sizes of the join inputs. Cost-based query optimization chooses the most appropriate algorithm for each query and for each operation. Unfortunately, mistaken algorithm choices during compile-time query optimization are common yet expensive to investigate and to resolve.

Our goal is to end mistaken choices among join algorithms by replacing the three traditional join algorithms with a single one. Like merge join, this new join algorithm exploits sorted inputs. Like hash join, it exploits different input sizes for unsorted inputs. In fact, for unsorted inputs, the cost functions for recursive hash join and for hybrid hash join have guided our search for the new join algorithm. In consequence, the new join algorithm can replace both merge join and hash join in a database management system.

The in-memory components of the new join algorithm employ indexes. If the database contains indexes for one (or both) of the inputs, the new join can exploit persistent indexes instead of temporary in-memory indexes. Using database indexes to match input records, the new join algorithm can also replace index nested loops join.

Goetz's areas of expertise within database management systems cover compile-time query optimization including extensible query optimization, run-time query execution including parallel query execution, indexing, and transactions. He has also worked on transactional memory, specifically techniques for software implementations of transactional memory.

Goetz pursued undergraduate studies in business and in computer science at multiple German universities. In 1983, he was admitted to the University of Wisconsin - Madison, where he was granted a MS degree in 1984 and a Ph.D. in 1987.

Dr. Divyakant Agrawal is a Professor of Computer Science at the University of California at Santa Barbara. His research expertise is in the areas of database systems, distributed computing, data warehousing, and large-scale information systems. Dr. Agrawal served as the Chair of Computer Science Department at UCSB from 1999 to 2003. From January 2006 through December 2007, Dr. Agrawal served as VP of Data Solutions and Advertising Systems at the Internet Search Company ASK.com. Dr. Agrawal has also served as a Visiting Senior Research Scientist at the NEC Laboratories of America in Cupertino, CA from 1997 to 2009.

During his professional career, Dr. Agrawal has served on numerous Program Committees of International Conferences, Symposia, and Workshops and served as an editor of the journal of Distributed and Parallel Databases (1993-2008), the VLDB journal (2003-2008) and currently serves on the editorial boards of the Proceedings of the VLDB and ACM Transactions on Database Systems. He recently served as the Program Chair of the 2010 ACM International Conference on Management of Data and served as the General Chair of the 2010 ACM SIGSPATIAL Conference on Advances in Geographical Information Systems.

Dr. Agrawal organized an NSF Workshop on the Science of Cloud Computing in March’2011, is serving as the General Co-Chair of ACM SIGSPATIAL Conference on Advances in GIS (ACM GIS’2011), and is serving as the Program Co-Chair of ACM Workshop on Large Scale Distributed Systems and Middleware (ACM LADIS’2011). Dr. Agrawal's research philosophy is to develop data management solutions that are theoretically sound and are relevant in practice. He has published 300+ research manuscripts in prestigious forums (journals, conferences, symposia, and workshops) on wide range of topics related to data management and distributed systems and has advised more than 30 Doctoral students during his academic career.

Recently, Dr. Agrawal has been recognized as an Association of Computing Machinery (ACM) Distinguished Scientist. His current interests are in the area of scalable data management and data analysis in Cloud Computing environments, security and privacy of data in the cloud, and scalable analytics over social networks data and social media.

Cloud computing has become a popular paradigm for efficiently processing computationally and data-intensive tasks. Such tasks can be executed on demand on powerful distributed hardware and service infrastructures. The parallel execution of complex tasks is facilitated by different programming models (e.g., MapReduce), distributed data stores, and the ability to employ computing capacity on demand. Data integration can notably benefit from cloud computing because accessing multiple data sources and integration of instance data are usually expensive tasks.

In the first part of the talk we introduce CloudFuice, a data integration system that follows a mashup-like specification of advanced data flows for data integration. CloudFuice's task-based execution approach allows for an efficient, asynchronous, and parallel execution of data flows in the cloud and utilizes recent cloud-based web engineering instruments. The second part of the talk deals with the effectiveness and scalability of MapReduce-based implementations for entity resolution. In the presence of skewed data, sophisticated redistribution approaches become necessary to achieve load balancing among all reduce tasks to be executed in parallel. The proposed approaches support blocking techniques to reduce the search space of entity resolution and effectively distribute the entities of large blocks among multiple reduce tasks.