Karthik

About

I was a graduate student from August 1994 to May 2000 working towards
my Ph.D in databases with my advisor Jeffrey Naughton. I completed in July 2001.
My research interests spans across various areas of computer science including

Data Warehousing

Object Relational Database Systems

Networking and Routing

File Systems

I worked with Jeffrey Naughton in the BORG data warehouse project and
with David Dewitt in Paradise project.

Projects

BORG Data Warehouse
Paradise Parallel Database
Miscellaneous hacking for David Dewitt and Jeffrey Naughton

Dissertation

Efficient Storage and Query Processing of Set-Valued Attributes

Abstract

In order to better support complex applications, object relational systems provide features
that are absent in relational systems. The main distinguishing features are abstract data types
and type constructors. The set constructor creates a new type by providing collections of
existing types. It is well known that sets are useful in modeling a great deal of real world data.
However, such powerful modelling comes at a price; without an efficient implementation, using
sets can yield a performance much worse than that obtained using only traditional relational
constructs. This dissertation explores novel ways of implementing set-valued attributes in an object
relational system. Specifically, it considers various options for efficiently storing set-valued
attributes, and ways of computing the challenging set containment join operation.

We first address the problem of storing set-valued attributes. Using the orthogonal attributes
of nesting and location we identify four options for representing sets: nested internal and external,
and unnested external and internal. These representations can be combined with the creation of
various indices to create various classes of indexed representations. We evaluate each of these
representations with respect to conjunctive and disjunctive queries. Our results show that overall
the nested implementations perform better than the unnested implementations because

they exploit group semantics while fetching the members of a set instance
they allow the evaluation of set predicates directly on the set instance

Next we consider the problem of efficiently evaluating set containment joins. For unnested external
representation, the set containment join can be expressed directly in SQL. By contrast, the most
obvious algorithm for computing set containment joins on nested representations is the signature
nested loops algorithm, which computes set signatures and compares each signature in a relation with
all the signatures in the other relation. To improve on the performance of this algorithm we propose
a new partitioned set join algorithm (PSJ), which uses a multi-level scheme of partitioning by
replicating the inner relation. Our performance study shows that for extremely small relation and small
set cardinalities, the SQL query approach and signature nested loops perform comparably to PSJ.
However, as the size of the data sets increase (in both relation and set cardinality), PSJ clearly dominates.

Download

Efficient Storage and Query Processing of Set-Valued Attributes
Karthikeyan Ramasamy
Ph.D dissertation, Computer Sciences Department, Madison, Wisconsin, July 2001.
(ps-version) ; (pdf-version)

Publications

Data Warehouse

Caching Multidimensional Queries Using Chunks
Prasad M. Deshpande, Karthikeyan Ramasamy, Amit Shukla and Jeffrey F Naughton
Proceedings of the 1998 SIGMOD Conference, Seattle, Washington, June 1998.
(ps-version) ; (pdf-version)

Array-Based Evaluation of Multi-Dimensional Queries in Object Relational Database
Systems
Yihong Zhao, Karthikeyan Ramasamy, Kristin Tufte and Jeffrey F Naughton
International Conference on Data Engineering, Orlando, United States, 1998.
(ps-version) ; (pdf-version)

Cubing Algorithms, Storage Estimation, and Storage and Processing Alternatives for OLAP
Prasad M. Deshpande, Jeffrey F. Naughton, Karthikeyan Ramasamy Amit Shukla, Kristin Tufte
and Yihong Zhao
Data Engineering Bulletin, IEEE Computer Society, March 1997, Vol 20 No.1

Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies
Amit Shukla, Prasad M Deshpande, Jeffrey F Naughton and Karthikeyan Ramasamy
Proceedings of the 22nd International Conference on Very Large Databases (VLDB), Mumbai(Bombay), 1996.
(ps-version) ; (pdf-version)

Object Relational Database Systems

Set Containment Joins: The Good, The Bad and The Ugly
Karthikeyan Ramasamy, Jignesh M Patel, Jeffrey F Naughton and Raghav Kaushik
Proceedings of the 26th International Conference on Very Large Databases (VLDB) Cairo, Egypt, 2000.
(ps-version) ; (pdf-version)

Set Containment Joins: The Good, The Bad and The Ugly: Expanded Version
Karthikeyan Ramasamy, Jignesh M Patel, Jeffrey F Naughton and Raghav Kaushik
(ps-version) ; (pdf-version)

Building a Scalable Geo Spatial DBMS: Technology, Implementation and Evaluation
Jignesh Patel, Jiebing Yu, Navin Kabra, Kristin Tufte, Biswadeep Nag, Josef Burger, Nancy
Hall, Karthikeyan Ramasamy, Roger Lueder, Curt Ellman, Jim Kupsch, Shelly Guo, Johan
Larson, David DeWitt and Jeffrey F Naughton
Proceedings of the 1997 SIGMOD Conference, Tucson, Arizona, May 1997.
(ps-version) ; (pdf-version)

Selected Professional Activities

Technical Program Committee