How to Forget the Past Without Repeating It (2009)
Jeffrey F. Naughton, Raghu Ramakrishnan
Those who cannot remember the past are condemned to repeat it.- George Santayana Bottom-up evaluation of deductive database programs has the advantage that it avoids repeated computation by storing...
The Case for a Structured Approach to Managing Unstructured Data (2009)
Anhai Doan, Jeffrey F. Naughton, Akanksha Baid, Xiaoyong Chai, Fei Chen, Ting Chen, ...
The challenge of managing unstructured data represents perhaps the largest data management opportunity for our community since managing relational data. And yet we are risking letting this...
Transparently Gathering Provenance with Provenance Aware Condor (2009)
Christine F. Reilly, Jeffrey F. Naughton
We observed that the Condor batch execution system exposes a lot of information about the jobs that run in the system. This observation led us to explore whether this system information could be used...
Qiong Luo, Jeffrey F. Naughton, Wenwei Xue, J. F. Naughton
Abstract Web caching proxy servers are essential for improving web performance and scalability, and recent research has focused on making proxy caching work for database-backed web sites. In this...
On the Provenance of Non-Answers to Queries over Extracted Data ∗ ABSTRACT (2009)
Jiansheng Huang, Ting Chen, Anhai Doan, Jeffrey F. Naughton
In information extraction, uncertainty is ubiquitous. For this reason, it is useful to provide users querying extracted data with explanations for the answers they receive. Providing the provenance...
Middle-tier database caching for e-business (2009)
Qiong Luo, Sailesh Krishnamurthy, C. Mohan, Hamid Pirahesh, Honguk Woo, Bruce G. Lindsay, ...
Scaling up to the enormous and growing Internet population with unpredictable usage patterns, E-commerce applications face severe challenges in cost and manageability, especially for database servers...
Stratis D. Viglas, Leonidas Galanis, David J. Dewitt, Jeffrey F. Naughton, David Maier
While the XML community appears to be converging on XQuery as a standard for querying XML documents, there is currently much less consensus about a standard algebra. In this paper, we describe the...
University of Wisconsin-Madison (2009)
Raghav Kaushik, Jeffrey F. Naughton, Raghu Ramakrishnan, Venkatesan T. Chakravarthy
Database systems use precomputed synopses of data to estimate the cost of alternative plans during query optimization. A number of alternative synopsis structures have been proposed, but histograms...
XML Views as Integrity Constraints and their Use in Query Translation (2009)
Rajasekar Krishnamurthy, Raghav Kaushik, Jeffrey F Naughton
The SQL queries produced in XML-to-SQL query translation are often unnecessarily complex, even for simple input XML queries. In this paper we argue that relational systems can do a better job of...
• Familiar with various DBMSs, GIS systems, and Operating Systems RESEARCH INTERESTS (2009)
Advisor Prof, Jeffrey F. Naughton
• Solid academic and practical background in computer programming and databases • Research in semi-structured data management • Research in DBMS under Internet, mobile, and client-server...
Abstract An Array-Based Algorithm for Simultaneous Multidimensional Aggregates * (2008)
Yihong Zhao, Prasad M. Deshpande, Jeffrey F. Naughton
Computing multiple related groupbys and aggregates is one of the core operations of On-Line Analytical Processing (OLAP) applications. Recently, Gray et al. [GBLP95] proposed the “Cube ”...
- Worked on translating Matlab scripts to programs in C/C++ language as a part of (2008)
Ph. D. Student, Advisor Prof, Jeffrey F. Naughton, Advisor Prof, Bong-hee Hong
• Solid academic and practical background in computer programming, computer networking, and databases • Research in computer networking and network security • Research in databases under...
ABSTRACT Middle-Tier Database Caching for e-Business * (2008)
Qiong Luo, Sailesh Krishnamurthy, C. Mohan, Hamid Pirahesh, Honguk Woo, Bruce G. Lindsay, ...
While scaling up to the enormous and growing Internet population with unpredictable usage patterns, E-commerce applications face severe challenges in cost and manageability, especially for database...
Dealing with (un)structuredness in XML Data and Queries Using Relational Databases (2008)
Rajasekar Krishnamurthy, Jeffrey F. Naughton, Jayavel Shanmugasundaram, Eugene Shekita
An XML database can contain documents with varying degrees of schema information. The queries can also range from fully specified structured SQL like queries to partially specified regular path...
K-Relevance: A Spectrum of Relevance for Data Sources Impacting a Query ∗ (2008)
Jiansheng Huang, Jeffrey F. Naughton
Copyright ACM, (2007). This is the author’s version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in...
Transaction Reordering with Application to Synchronized Scans (2008)
Gang Luo, Jeffrey F. Naughton, Curt J. Ellmann, Michael W. Watzke
Traditional workload management methods mainly focus on the current system status while information about the interaction between queued and running transactions is largely ignored. An exception to...
Auxiliary Relations for Join View Maintenance in Parallel RDBMS Abstract (2008)
Gang Luo, Jeffrey F. Naughton, Curt J. Ellmann, Michael W. Watzke
In a typical data warehouse, materialized views are used to speed up query execution. Upon updates to the base relations in the warehouse, these materialized views must also be updated. The need to...
Maximizing the Output Rate of Multi-Join Queries over Streaming Information Sources (2008)
List Stratis, D. Viglas, Jeffrey F. Naughton, Josef Burger, Contact Stratis, D. Viglas, ...
Recently there has been a growing focus in the research community on join query evaluation for scenarios in which input characteristics may not be entirely known and inputs enter the system at highly...
Transaction Reordering and Grouping for Continuous Data Loading (2008)
Gang Luo, Jeffrey F. Naughton, Curt J. Ellmann, Michael W. Watzke
With the increasing popularity of operational data warehousing, the ability to load data quickly and continuously into an RDBMS is becoming more and more important. However, in the presence of...
Transaction Reordering and Grouping for Continuous Data Loading (2008)
Gang Luo, Jeffrey F. Naughton, Curt J. Ellmann, Michael W. Watzke
Abstract. With the increasing popularity of operational data warehousing, the ability to load data quickly and continuously into an RDBMS is becoming more and more important. However, in the presence...
Real-Time, Concurrent Checkpoint (2008)
Kai Li, Jeffrey F. Naughton, James S. Plank
We have developed and implemented a checkpointing
Optimization and Performance Optimizing Fixed-Schema XML to SQL Query Translation (2007)
Contact Rajasekar Krishnamurthy, Rajasekar Krishnamurthy, Rajasekar Krishnamurthy, Raghav Kaushik, Raghav Kaushik, Jeffrey F. Naughton, ...
Recently, there has been a lot of work on evaluating XML queries over data stored in relational database systems. The vast majority of this work has focused on the cases where either the relational...
A Brief Note on Path Indexability (2007)
Raghav Kaushik, Jeffrey F. Naughton
In [1], a theory of indexability is developed. The authors essentially classify all indexing problems as one of blocking up the data elements (from set I) into fixed size blocks for a given query...
A Comparison of Three Methods for Join View Maintenance in Parallel RDBMS (2007)
Gang Luo, Jeffrey F. Naughton, Curt J. Ellmann, Michael W. Watzke
In a typical data warehouse, materialized views are used to speed up query execution. Upon updates to the base relations in the warehouse, these materialized views must also be maintained. The need...
Karthikeyan Ramasamy, Raghav Kaushik, Jeffrey F Naughton
naughton cs. wisc. edu Efficient support for set-valued attributes is likely to grow in importance as object-relational database systems, which either support set-valued attributes or propose to do...
ABSTRACT On the Complexity of Join Predicates (2007)
Jin-yi Cai, Venkatesan T. Chakaravarthy, Raghav Kaushik, Jeffrey F. Naughton
We consider the complexity of join problems, focusing on equijoins, spatial-overlap joins, and set-containment joins. We use a graph pebbling model to characterize these joins combinatorially, by the...
1 A Non-blocking Parallel Spatial Join Algorithm (2007)
Gang Luo, Jeffrey F. Naughton, Curt J. Ellmann
Interest in incremental and adaptive query processing has led to the investigation of equijoin evaluation algorithms that are non-blocking. This investigation has yielded a number of algorithms,...
1 Auxiliary Relations for Join View Maintenance in Parallel RDBMS (2007)
Gang Luo, Jeffrey F. Naughton, Curt J. Ellmann, Michael W. Watzke
In a typical data warehouse, materialized views are used to speed up query execution. Upon updates to the base relations in the warehouse, these materialized views must also be updated. The need to...
Form-based proxy caching for database-backed web sites : keywords and functions (2006)
Luo, Qiong, Naughton, Jeffrey F., Xue, Wenwei
Web caching proxy servers are essential for improving web performance and scalability, and recent research has focused on making proxy caching work for database-backed web sites. In this paper, we...
Database support for matching: limitations and opportunities (2006)
Ameet Kini, Srinath Shankar, Jeffrey F. Naughton, David J. Dewitt
We define a match join of R and S with predicate θ to be a subset of the θ-join of R and S such that each tuple of R and S contributes to at most one result tuple. Match joins and their...
Multi-query SQL progress indicators (2006)
Gang Luo, Jeffrey F. Naughton, Philip S. Yu
Abstract. Recently, progress indicators have been proposed for SQL queries in RDBMSs. All previously proposed progress indicators consider each query in isolation, ignoring the impact simultaneously...
Database support for matching: limitations and opportunities (2006)
Ameet Kini, Srinath Shankar, Jeffrey F. Naughton, David J. Dewitt
We define a match join of R and S with predicate θ to be a subset of the θ-join of R and S such that each tuple of R and S contributes to at most one result tuple. Match joins and their...
Multi-query SQL progress indicators (2006)
Gang Luo, Jeffrey F. Naughton, Philip S. Yu
Abstract. Recently, progress indicators have been proposed for SQL queries in RDBMSs. All previously proposed progress indicators consider each query in isolation, ignoring the impact simultaneously...
Extending RDBMSs to support sparse datasets using an interpreted attribute storage format (2006)
Jennifer L. Beckmann, Alan Halverson, Rajasekar Krishnamurthy, Jeffrey F. Naughton
“Sparse ” data, in which relations have many attributes that are null for most tuples, presents a challenge for relational database management systems. If one uses the normal “horizontal ”...
Increasing The Accuracy and Coverage of SQL Progress Indicators (2005)
Gang Luo, Jeffrey F. Naughton, Curt J. Ellmann, Michael W. Watzke
Recently, progress indicators have been proposed for long-running SQL queries in RDBMSs. Although the proposed techniques work well for a subset of SQL queries, they are preliminary in the sense that...
The Lowell Database Research Self-Assessment (2005)
Abiteboul, Serge, Agrawal, Rakesh, Bernstein, Philip A., Carey, Michael J., Ceri, Stefano, Croft, W. Bruce, ...
Database needs are changing, driven by the Internet and increasing amounts of scientific and sensor data. In this article, the authors propose research into several important new directions for...
Efficient XML-to-SQL Query Translation: Where to Add the Intelligence (2004)
Rajasekar Krishnamurthy, Raghav Kaushik, Jeffrey F Naughton
We consider the efficiency of queries generated by XML to SQL translation. We first show that published XML-to-SQL query translation algorithms are suboptimal in that they often translate simple path...
Static optimization of conjunctive queries with sliding windows over infinite streams (2004)
Ahmed M. Ayad, Jeffrey F. Naughton
We define a framework for static optimization of sliding window conjunctive queries over infinite streams. When computational resources are sufficient, we propose that the goal of optimization should...
Efficient XML-to-SQL Query Translation: Where to Add the Intelligence (2004)
Rajasekar Krishnamurthy, Raghav Kaushik, Jeffrey F Naughton
We consider the efficiency of queries generated by XML to SQL translation. We first show that published XML-to-SQL query translation algorithms are suboptimal in that they often translate simple path...
Toward a progress indicator for database queries (2004)
Gang Luo, Jeffrey F. Naughton, Curt J. Ellmann, Michael W. Watzke
Many modern software systems provide progress indicators for long-running tasks. These progress indicators make systems more user-friendly by helping the user quickly estimate how much of the task...
Efficient XML-to-SQL Query Translation: Where to Add the Intelligence (2004)
Rajasekar Krishnamurthy, Raghav Kaushik, Jeffrey F Naughton
We consider the efficiency of queries generated by XML to SQL translation. We first show that published XML-to-SQL query translation algorithms are suboptimal in that they often translate simple path...
Efficient XML-to-SQL Query Translation: Where to Add the Intelligence (2004)
Rajasekar Krishnamurthy, Raghav Kaushik, Jeffrey F Naughton
We consider the efficiency of queries generated by XML to SQL translation. We first show that published XML-to-SQL query translation algorithms are suboptimal in that they often translate simple path...
Efficient XML-to-SQL Query Translation: Where to Add the Intelligence (2004)
Rajasekar Krishnamurthy, Raghav Kaushik, Jeffrey F. Naughton
Exporting XML views of relational data gives rise to the problem of translating XML queries into SQL. To date, the focus of most of the work in the published literature [9, 14, 20] has been
Rajasekar Krishnamurthy, Venkatesan T. Chakaravarthy, Raghav Kaushik, Jeffrey F. Naughton
We consider the problem of translating XML queries into SQL when XML documents have been stored in an RDBMS using a schema-based relational decomposition. Surprisingly, there is no published...
Unraveling the Duplicate-Elimination Problem in XML-to-SQL Query Translation (2004)
Rajasekar Krishnamurthy, Raghav Kaushik, Jeffrey F Naughton
We consider the scenario where existing relational data is exported as XML. In this context, we look at the problem of translating XML queries into SQL. XML query languages have two di#erent notions...
Toward a progress indicator for database queries (2004)
Gang Luo, Jeffrey F. Naughton, Curt J. Ellmann, Michael W. Watzke
Many modern software systems provide progress indicators for long-running tasks. These progress indicators make systems more user-friendly by helping the user quickly estimate how much of the task...
On the Integration of Structure Indexes and Inverted Lists (2004)
Raghav Kaushik, Rajasekar Krishnamurthy, Jeffrey F Naughton, Raghu Ramakrishnan
Recently, there has been a great deal of interest in the development of techniques to evaluate path expressions over collections of XML documents. In general, these path expressions contain both...
On the Integration of Structure Indexes and Inverted Lists (2004)
Raghav Kaushik, Rajasekar Krishnamurthy, Jeffrey F Naughton, Raghu Ramakrishnan
Several methods have been proposed to evaluate queries over a native XML DBMS, where the queries specify both path and keyword constraints. These broadly consist of graph traversal approaches,...
Towards building XML statistics for the hidden web (2003)
Ashraf Aboulnaga, Jeffrey F. Naughton
There is currently a lot of interest in developing Internet query processors that can pose elaborate queries on XML data on the Web. Such query processors can query data sources that have static XML...
On Schema Matching with Opaque Column Names and Data Values (2003)
Jaewoo Kang, Jeffrey F. Naughton
Most previous solutions to the schema matching problem rely in some fashion upon identifying "similar " column names in the schemas to be matched, or by recognizing common domains...
Rajasekar Krishnamurthy, Venkatesan T. Chakaravarthy, Jeffrey F. Naughton
Abstract. A key problem that arises in the context of storing XML documents in relational databases is that of finding an optimal relational decomposition for a given set of XML documents and a given...
XML-to-SQL Query Translation Literature: The State of the Art and Open Problems (2003)
Rajasekar Krishnamurthy, Raghav Kaushik, Jeffrey F. Naughton
Abstract. Recently, the database research literature has seen an explosion of publications with the goal of using an RDBMS to store and/or query XML data. The problems addressed and solved in this...
Mixed mode xml query processing (2003)
Alan Halverson, Josef Burger, Leonidas Galanis, Ameet Kini, Rajasekar Krishnamurthy, Ajith Nagaraja Rao, ...
Querying XML documents typically involves both tree-based navigation and pattern matching similar to that used in structured information retrieval domains. In this paper, we show that for good...
On Relational Support for XML Publishing: Beyond Sorting and Tagging (2003)
Surajit Chaudhuri, Raghav Kaushik, Jeffrey F. Naughton
In this paper, we study whether the need for efficient XML publishing brings any new requirements for relational query engines, or if sorting query results in the relational engine and tagging them...
Evaluating Window Joins over Unbounded Streams (2003)
Jaewoo Kang Jeffrey, Jeffrey F. Naughton, Stratis D. Viglas
We investigate algorithms for evaluating sliding window joins over pairs of unbounded streams. We introduce a unittime -basis cost model to analyze the expected performance of these algorithms. Using...
Maximizing the output rate of multi-way join queries over streaming information sources (2003)
Stratis D. Viglas, Jeffrey F. Naughton, Josef Burger
Recently there has been a growing interest in join query evaluation for scenarios in which inputs arrive at highly variable and unpredictable rates. In such scenarios, the focus shifts from...
Evaluating Window Joins over Unbounded Streams (2003)
Jaewoo Kang Jeffrey, Jeffrey F. Naughton, Stratis D. Viglas
We investigate algorithms for evaluating moving window joins over pairs of unbounded streams. We introduce a unit-time-basis cost model to analyze the expected performance of these algorithms. Using...
Locking Protocols for Materialized Aggregate Join Views (2003)
Gang Luo, Jeffrey F. Naughton, Curt J. Ellmann, Michael W. Watzke
The maintenance of materialized aggregate join views is a well-studied problem. However, to date the published literature has largely ignored the issue of concurrency control. Clearly immediate...
Locking Protocols for Materialized Aggregate Join Views (2003)
Gang Luo, Jeffrey F. Naughton, Curt J. Ellmann, Michael W. Watzke
The maintenance of materialized aggregate join views is a well-studied problem. However, to date the published literature has largely ignored the issue of concurrency control. Clearly immediate...
Building XML Statistics for the Hidden Web (2003)
Ashraf Aboulnaga, Jeffrey F. Naughton
There is currently a lot of interest in developing Internet query processors that can pose elaborate queries on XML data on the Web. Such query processors can query data sources that have static XML...
Locking Protocols for Materialized Aggregate Join Views (2003)
Gang Luo, Jeffrey F. Naughton, Curt J. Ellmann, Michael W. Watzke
The maintenance of materialized aggregate join views is a well-studied problem. However, to date the published literature has largely ignored the issue of concurrency control. Clearly immediate...
Locking Protocols for Materialized Aggregate Join Views (2003)
Gang Luo, Jeffrey F. Naughton, Curt J. Ellmann, Michael W. Watzke
Abstract—The maintenance of materialized aggregate join views is a well-studied problem. However, to date the published literature has largely ignored the issue of concurrency control. Clearly,...
On Schema Matching with Opaque Column Names and Data Values (2003)
Jaewoo Kang, Jeffrey F. Naughton
Most previous solutions to the schema matching problem rely in some fashion upon identifying "similar " column names in the schemas to be matched, or by recognizing common domains...
Rajasekar Krishnamurthy, Venkatesan T. Chakaravarthy, Jeffrey F. Naughton
Abstract. A key problem that arises in the context of storing XML documents in relational databases is that of finding an optimal relational decomposition for a given set of XML documents and a given...
Rajasekar Krishnamurthy, Raghav Kaushik, Jeffrey F. Naughton
Recently, there has been a lot of work on evaluating XML queries over data stored in rela-tional database systems. The vast majority of this work has focused on the cases where either the relational...
A Scalable Hash Ripple Join Algorithm (2002)
Gang Luo, Curt J. Eiimann, Peter J. Haas, Jeffrey F. Naughton
Recently, Haas and Hellerstein proposed the hash ripple join algorithm in the context of online aggregation. Although the algorithm rapidly gives a good estimate for many join-aggregate problem...
Rate-Based Query Optimization for Streaming Information Sources (2002)
Stratis D. Viglas, Jeffrey F. Naughton
Relational query optimizers have traditionally relied upon table cardinalities when estimating the cost of the query plans they consider. While this approach has been and continues to be successful,...
Rate-Based Query Optimization for Streaming Information Sources (2002)
Stratis D. Viglas, Jeffrey F. Naughton
Relational query optimizers have traditionally relied upon table cardinalities when estimating the cost of the query plans they consider. While this approach has been and continues to be successful,...
Updates for structure indexes (2002)
Raghav Kaushik, Philip Bohannon, Jeffrey F Naughton, Pradeep Shenoy
The problem of indexing path queries in semistructured/XML databases has received considerable attention recently, and several proposals have advocated the use of structure indexes as supporting data...
Rate-Based Query Optimization for Streaming Information Sources (2002)
Efstratios Viglas, Efstratios Viglas, Efstratios Viglas, Jeffrey F. Naughton, Jeffrey F. Naughton
Query optimizers typically attempt to minimize response time. While this approach has been and continues to be very successful in traditional environments, in the presence of information sources of...
Jianjun Chen, David J. DeWitt, Jeffrey F. Naughton
selection placement strategies for optimizing a very large number of continuous queries in an Internet environment. Two grouping strategies, PushDown and PullUp, in which selections are either pushed...
Covering Indexes for Branching Path Queries (2002)
Raghav Kaushik, Philip Bohannon, Jeffrey F Naughton, Henry F Korth
In this paper, we ask if the traditional relational query acceleration techniques of summary tables and covering indexes have analogs for branching path expression queries over tree- or...
A Non-Blocking Parallel Spatial Join Algorithm (2002)
Gang Luo, Jeffrey F. Naughton, Curt J. Ellmann
Interest in incremental and adaptive query processing has led to the investigation of equijoin evaluation algorithms that are non-blocking. This investigation has yielded a number of algorithms,...
A Scalable Hash Ripple Join Algorithm (2002)
Gang Luo, Curt J. Ellmann, Peter J. Haas, Jeffrey F. Naughton
Recently, Haas and Hellerstein proposed the hash ripple join algorithm in the context of online aggregation. Although the algorithm rapidly gives a good estimate for many join-aggregate problem...
Estimating the Selectivity of XML Path Expressions for Internet Scale Applications (2001)
Ashraf Aboulnaga, Alaa R. Alameldeen, Jeffrey F. Naughton
Data on the Internet is increasingly presented in XML format. This enables novel applications that pose queries over “all the XML data on the Internet.” Queries over XML data use path expressions...
Generating Synthetic Complex-structured XML Data (2001)
Ashraf Aboulnaga, Jeffrey F. Naughton, Chun Zhang
Synthetically generated data has always been important for evaluating and understanding new ideas in database research. In this paper, we describe a data generator for generating synthetic...
Estimating the Selectivity of XML Path Expressions for Internet Scale Applications (2001)
Ashraf Aboulnaga, Alaa R. Alameldeen, Jeffrey F. Naughton
Data on the Internet is increasingly presented in XML format. This enables novel applications that pose queries over “all the XML data on the Internet.” Queries over XML data use path expressions...
Generating Synthetic Complex-structured XML Data (2001)
Ashraf Aboulnaga, Jeffrey F. Naughton, Chun Zhang
Synthetically generated data has always been important for evaluating and understanding new ideas in database research. In this paper, we describe a data generator for generating synthetic...
Estimating the Selectivity of XML Path Expressions for Internet Scale Applications (2001)
Ashraf Aboulnaga, Alaa R. Alameldeen, Jeffrey F. Naughton
Data on the Internet is increasingly presented in XML format. This enables novel applications that pose queries over “all the XML data on the Internet.” Queries over XML data use path expressions...
Active query caching for database web servers (2000)
Qiong Luo, Jeffrey F. Naughton, Rajasekar Krishnamurthy, Pei Cao, Yunrui Li
Abstract. A substantial portion of web traffic consists of queries to database web servers. Unfortunately, a common technique to improve web scalability, proxy caching, is ineffective for database...
Active query caching for database web servers (2000)
Qiong Luo, Rajasekar Krishnamurthy, Yunrui Li, Pei Cao, Jeffrey F. Naughton
Database web servers are an important class of dynamic content providers on the Internet. Unfortunately, like most dynamic content providers, their form-based queries and responses cannot be cached...
Materialized view selection for multi-cube data models (2000)
Amit Shukla, Prasad M. Deshp, Jeffrey F. Naughton
Abstract. OLAP applications use precomputation of aggregate data to improve query response time. While this problem has been well-studied in the recent database literature, to our knowledge all...
Set containment joins: The good, the bad and the ugly (2000)
Karthikeyan Ramasamy, Raghav Kaushik, Jeffrey F Naughton
naughtoncs. wisc. edu Efficient support for set-valued attributes is likely to grow in importance as object-relational database systems, which either support set-valued attributes or propose to do so...
Active query caching for database web servers (2000)
Qiong Luo, Jeffrey F. Naughton, Rajasekar Krishnamurthy, Pei Cao, Yunrui Li
A substantial portion of web traffic consists of queries to database web servers. Unfortunately, a common technique to improve web scalability, proxy caching, is ineffective for database web servers...
Accurate Estimation of the Cost of Spatial Selections (2000)
Ashraf Aboulnaga Jeffrey, Jeffrey F. Naughton
Optimizing queries that involve operations on spatial data requires estimating the selectivity and cost of these operations. In this paper, we focus on estimating the cost of spatial selections, or...
Accurate Estimation of the Cost of Spatial Selections (2000)
Ashraf Aboulnaga, Jeffrey F. Naughton
Optimizing queries that involve operations on spatial data requires estimating the selectivity and cost of these operations. In this paper, we focus on estimating the cost of spatial selections, or...
Active Query Caching for Database Web Servers (1999)
Qiong Luo, Rajasekar Krishnamurthy, Yunrui Li, Pei Cao, Jeffrey F. Naughton
Database web servers are an important class of dynamic content providers on the Internet. Unfortunately, like most dynamic content providers, their form-based queries and responses cannot be cached...
Active Query Caching for Database Web Servers (1999)
Qiong Luo, Jeffrey F. Naughton, Rajesekar Krishnamurthy, Pei Cao, Yunrui Li
A substantial portion of web traffic consists of queries to database web servers. Unfortunately, a common technique to improve web scalability, proxy caching, is ineffective for database web servers...
Array-Based Evaluation of Multi-Dimensional Queries (1998)
Yihong Zhao, Karthikeyan Ramasamy, Kristin Tufte, Jeffrey F. Naughton
Since multi-dimensional arrays are a natural data structure for supporting multi-dimensional queries, and object-relational database systems support multi-dimensional array ADTs, it is natural to ask...
Simultaneous Optimization and Evaluation of Multiple Dimensional Queries (1998)
Yihong Zhao, Prasad M. Deshpande, Jeffrey F. Naughton, Amit Shukla
Database researchers have made significant progress on several research issues related to multidimensional data analysis, including the development of fast cubing algorithms, efficient schemes for...
Caching Multidimensional Queries Using Chunks (1998)
Prasad Deshpande, Karthikeyan Ramasamy, Amit Shukla, Jeffrey F. Naughton
Caching has been proposed (and implemented) by OLAP systems in order to reduce response times for multidimensional queries. Previous work on such caching has considered table level caching and query...
Caching Multidimensional Queries Using Chunks (1998)
Prasad Deshpande, Karthikeyan Ramasamy, Amit Shukla, Jeffrey F. Naughton
Caching has been proposed (and implemented) by OLAP systems in order to reduce response times for multidimensional queries. Previous work on such caching has considered table level caching and query...
Remote Load-Sensitive Caching for Multi-Server Database Systems (1998)
Shivakumar Venkataraman, Jeffrey F. Naughton, Miron Livny
The recent dramatic improvements in the performance of commodity hardware has made clusters of workstations or PCs an attractive and economical platform upon which to build scalable database servers....
Array-Based Evaluation of Multi-Dimensional Queries in Object-Relational Database Systems (1998)
Yihong Zhao, Karthikeyan Ramasamy, Kristin Tufte, Jeffrey F. Naughton
Since multi-dimensional arrays are a natural data structure for supporting multi-dimensional queries, and object-relational database systems support multi-dimensional array ADTs, it is natural to ask...
Caching Multidimensional Queries Using Chunks (1998)
Prasad M. Deshpande, Karthikeyan Ramasamy, Amit Shukla, Jeffrey F. Naughton
Paper Number 213 Caching has been proposed (and implemented) by OLAP systems in order to reduce response times for multidimensional queries. Previous work on such caching has considered table level...
Materialized view selection for multidimensional datasets (1998)
Amit Shukla, Prasad M. Deshpande, Jeffrey F. Naughton
To fulfill the requirement of fast interactive multidimensional data analysis, database sys-tems precompute aggregate views on some sub-sets of dimensions and their corresponding hi-erarchies....
Declarative information extraction using Datalog with embedded extraction predicates (1997)
Warren Shen, Anhai Doan, Jeffrey F. Naughton, Raghu Ramakrishnan
In this paper we argue that developing information extraction (IE) programs using Datalog with embedded procedural extraction predicates is a good way to proceed. First, compared to current ad-hoc...
The BUCKY Object-Relational Benchmark (1997)
Michael Carey David, David J. Dewitt, Jeffrey F. Naughton, Mohammad Asgarian, Paul Brown, Johannes E. Gehrke, ...
According to various trade journals and corporate marketing machines, we are now on the verge of a revolution--- the object-relational database revolution. Since we believe that no one should face a...
The BUCKY Object-Relational Benchmark (1997)
Michael J. Carey, David J. DeWitt, Jeffrey F. Naughton, Mohammad Asgarian, Paul Brown, Johannes E. Gehrke, ...
According to various trade journals and corporate marketing machines, we are now on the verge of a revolution -- the object-relational database revolution. Since we believe that no one should face a...
An Array-Based Algorithm for Simultaneous Multidimensional Aggregates (1997)
Yihong Zhao, Prasad M. Deshpande, Jeffrey F. Naughton
Computing multiple related group-bys and aggregates is one of the core operations of On-Line Analytical Processing (OLAP) applications. Recently, Gray et al. [GBLP95] proposed the "Cube"...
An Array-Based Algorithm for Simultaneous Multidimensional Aggregates (1997)
Yihong Zhao, Prasad M. Deshpande, Jeffrey F. Naughton
Computing multiple related group-bys and aggregates is one of the core operations of On-Line Analytical Processing (OLAP) applications. Recently, Gray et al. [GBLP95] proposed the "Cube"...
Declarative information extraction using datalog with embedded extraction predicates (1997)
Warren Shen, Anhai Doan, Jeffrey F. Naughton, Raghu Ramakrishnan
In this paper we argue that developing information extraction (IE) programs using Datalog with embedded procedural extraction predicates is a good way to proceed. First, compared to current ad-hoc...
Storage estimation for multidimensional aggregates in the presence of hierarchies (1996)
Amit Shukla, Prasad M. Deshpande, Jeffrey F. Naughton, Karthikeyan Ramasamy
To speed up multidimensional data analysis, database systems frequently precompute ag-gregates on some subsets of dimensions and their corresponding hierarchies. This improves query response time....
These patents were applied for when working in Oracle Corporation. (1996)
Advisor Prof, Jeffrey F. Naughton, Jiansheng Huang, Ting Chen, Anhai Doan, ...
emphases on techniques for interpreting the correctness and completeness of imprecise query results and on generalpurpose user-driven information extraction and integration systems for answering...
These patents were applied for when working in Oracle Corporation. (1996)
Advisor Prof, Jeffrey F. Naughton, Jiansheng Huang, Ting Chen, Anhai Doan, ...
emphases on techniques for interpreting the correctness and completeness of imprecise query results and on generalpurpose user-driven information extraction and integration systems for answering...
On the Performance of an Array-Based ADT for OLAP Workloads (1996)
Yihong Zhao, Kristin Tufte, Jeffrey F. Naughton
There is currently a debate among OLAP vendors on the best way to provide OLAP functionality: Relational OLAP (ROLAP) vendors advocate using sophisticated front ends to provide a multidimensional...
Query Execution Techniques for Caching Expensive Methods (1996)
Joseph M. Hellerstein, Jeffrey F. Naughton
Abstract. Object-Relational and Object-Oriented DBMSs allow users to invoke time-consuming ("expensive") methods in their queries. When queries containing these expensive methods...
On the Computation of Multidimensional Aggregates (1996)
Sameet Agarwal, Rakesh Agrawal, Prasad M. Deshpande, Ashish Gupta, Jeffrey F. Naughton, Raghu Ramakrishnan, ...
At the heart of all OLAP or multidimensional data analysis applications is the ability to simultaneously aggregate across many sets of dimensions. Computing multidimensional aggregates is a...
Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies (1996)
Amit Shukla, Prasad M. Deshpande, Jeffrey F. Naughton, Karthikeyan Ramasamy
To speed up multidimensional data analysis, database systems frequently precompute aggregates on some subsets of dimensions and their corresponding hierarchies. This improves query response time....
Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies (1996)
Amit Shukla Prasad, Prasad M. Deshpande, Jeffrey F. Naughton, Karthikeyan Ramasamy
To speed up multidimensional data analysis, database systems frequently precompute aggregates on some subsets of dimensions and their corresponding hierarchies. This improves query response time....
Incremental Loading of Object Databases (1996)
Janet L. Wiener, Jeffrey F. Naughton
Object-oriented and object-relational databases (OODB) need to be able to load the vast quantities of data that OODB users bring to them. Loading OODB data is significantly more complicated than...
On the Performance of an Array-Based ADT for OLAP Workloads (1996)
Yihong Zhao, Kristin Tufte, Jeffrey F. Naughton
There is currently a raging debate among OLAP vendors on the best way to provide OLAP functionality: Relational OLAP (ROLAP) vendors advocate using sophisticated front ends to provide a...
Parallelizing OODBMS traversals: a performance evaluation (1996)
David Dewitt, Jeffrey F. Naughton, John C. Shafer, Shivakumar Venkataraman
.<F3.733e+05> In this paper we describe the design and implementation of<F3.963e+05><F3.733e+05> ParSets, a means of exploiting parallelism in the SHORE OODBMS. We used ParSets to...
On the Computation of Multidimensional Aggregates (1996)
Sameet Agarwal, Rakesh Agrawal, Prasad M. Deshpande, Ashish Gupta, Jeffrey F. Naughton, Raghu Ramakrishnan, ...
At the heart of all OLAP or multidimensional data analysis applications is the ability to simultaneously aggregate across many sets of dimensions. Computing multidimensional aggregates is a...
Hash Join Processing on Shared Memory Multiprocessors (1996)
Ambuj Shatdal, Jeffrey F. Naughton
While most scalable database systems are designed for a shared nothing architecture, advances in hardware technology suggest that in the near future shared memory multiprocessors (SMPs) will be...
Query Execution Techniques for Caching Expensive Methods (1996)
Joseph M. Hellerstein, Jeffrey F. Naughton
Object-Relational and Object-Oriented DBMSs allow users to invoke time-consuming ("expensive ") methods in their queries. When queries containing these expensive methods are run on data...
On the computation of multidimensional aggregates (1996)
E Ashish Gupta, Jeffrey F. Naughton, Raghu Ramakrishnan, Sunita Sarawagi
At the heart of all OLAP or multidimensional data analysis applications is the ability to si-multaneously aggregate across many sets of dimensions. Computing multidimensional ag-gregates is a...
Generalized Search Trees for Database Systems (1995)
Joseph Hellerstein, Jeffrey F. Naughton, Avi Pfeffer
This paper introduces the Generalized Search Tree (GiST), an index structure supporting an extensible set of queries and data types. The GiST allows new data types to be indexed in a manner...
Generalized Search Trees for Database Systems (1995)
Extend Ed, Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer
) Joseph M. Hellerstein University of Wisconsin, Madison jmh@cs.berkeley.edu Jeffrey F. Naughton University of Wisconsin, Madison naughton@cs.wisc.edu Avi Pfeffer University of California, Berkeley...
OODB Bulk Loading Revisited: The Partitioned-List Approach (1995)
Janet L. Wiener, Jeffrey F. Naughton
Object-oriented and object-relational databases (OODB) need to be able to load the vast quantities of data that OODB users bring to them. Loading OODB data is significantly more complicated than...
Generalized Search Trees for Database Systems (1995)
Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer
This paper introduces the Generalized Search Tree (GiST), an index structure supporting an extensible set of queries and data types. The GiST allows new data types to be indexed in a manner...
Space Optimization in Deductive Databases (1995)
Divesh Srivastava, S. Sudarshan, Raghu Ramakrishnan, Jeffrey F. Naughton
In the bottom-up evaluation of logic programs and recursively defined views on databases, all generated facts are usually assumed to be stored until the end of the evaluation. Discarding facts during...
Adaptive Parallel Aggregation Algorithms (1995)
Ambuj Shatdal, Jeffrey F. Naughton
Aggregation and duplicate removal are common in SQL queries. However, in the parallel query processing literature, aggregate processing has received surprisingly little attention; furthermore, for...
Michael J. Carey, David J. DeWitt, Jeffrey F. Naughton
The OO7 Benchmark represents a comprehensive test of OODBMS performance. In this report we describe the benchmark and present performance results from its implementation in four OODB systems. It is...
A Status Report on the OO7 OODBMS Benchmarking Effort (1994)
Michael Carey David, David J. Dewitt, Chander Kant, Jeffrey F. Naughton
The OO7 Benchmark was first published in 1993, and has since found a home in the marketing literature of various object-oriented database management system (OODBMS) vendors. The OO7 Benchmark (as...
Bulk Loading into an OODB: A Performance Study (1994)
Janet Wiener, Jeffrey F. Naughton
As object-oriented databases (OODB) attract an increasingly large community of users, these users bring with them large quantities of legacy data (hundreds and thousands of megabytes, and sometimes...
Bulk Loading into an OODB: A Performance Study (1994)
Janet Wiener, Jeffrey F. Naughton
Object-oriented database (OODB) users bring with them large quantities of legacy data (megabytes and even gigabytes). In addition, scientific OODB users continually generate new data. All this data...
Storage Reclamation and Reorganization in Client-Server Persistent Object Stores (1994)
Voon-fee Yong, Jeffrey F. Naughton, Jie-bing Yu
In this paper we develop and evaluate a number of storage reclamation algorithms for client-server persistent object stores. Experience with a detailed simulation and a prototype implementation in...
Paradise Version 0.1 Reference Manual (1994)
This document describes Paradise [DKLPY94], a database system designed for handling GIS (Geographical Information Systems) type applications which is under development at the University of Wisconsin...
Cache Conscious Algorithms for Relational Query Processing (1994)
Ambuj Shatdal, Chander Kant, Jeffrey F. Naughton
The current main memory (DRAM) access speeds lag far behind CPU speeds. Cache memory, made of static RAM, is being used in today's architectures to bridge this gap. It provides access latencies...
Processing Aggregates in Parallel Database Systems (1994)
Ambuj Shatdal, Jeffrey F. Naughton
Aggregates are rife in real life SQL queries. However, in the parallel query processing literature aggregate processing has received surprisingly little attention; furthermore, the way current...
Cache conscious algorithms for relational query processing (1994)
Ambuj Shatdal, Chander Kant, Jeffrey F. Naughton
The current main memory (DRAM) access speeds lag far behind CPU speeds. Cache memory, made of static RAM, is being used in today’s architectures to bridge this gap. It provides access latencies of...
David J. DeWitt, Jeffrey F. Naughton, Joseph Burger
The research community has considered hash-based parallel join algorithms the algorithms of choice for almost a decade. However, almost none of the commercial parallel database systems use...
Using Shared Virtual Memory for Parallel Join Processing (1993)
Ambuj Shatdal, Jeffrey F. Naughton
In this paper, we show that shared virtual memory, in a shared-nothing multiprocessor, facilitates the design and implementation of parallel join processing algorithms that perform significantly...
Parallel Sorting on a Shared-Nothing Architecture using Probabilistic Splitting (1992)
David J. DeWitt, Jeffrey F. Naughton, Donovan A. Schneider
We consider the problem of external sorting in a shared-nothing multiprocessor. A critical step in the algorithms we consider is to determine the range of sort keys to be handled by each processor....
Practical Skew Handling in Parallel Joins (1992)
David J. DeWitt, Jeffrey F. Naughton, Donovan A. Schneider, S. Seshadri
We present an approach to dealing with skew in parallel joins in database systems. Our approach is easily implementable within current parallel DBMS, and performs well on skewed data without...
An Efficient Checkpointing Method for Multicomputers with Wormhole Routing (1992)
Kai Li, Jeffrey F. Naughton, James S. Plank
Efficient checkpointing and resumption of multicomputer applications is essential if multicomputers are to support time-sharing and the automatic resumption of jobs after a system failure. We present...
On the Expected Size of Recursive Datalog Queries (1991)
S. Seshadri, Jeffrey F. Naughton
We present asymptotically exact expressions for the expected sizes of relations defined by three well-studied Datalog recursions, namely the "transitive closure", "same generation...
An Evaluation of Non-Equijoin Algorithms (1991)
David J. DeWitt, Jeffrey F. Naughton, Donovan A. Schneider
A non-equijoin of relations R and S is a band join if the join predicate requires values in the join attribute of R to fall within a specified band about the values in the join attribute of S. We...
Space Optimization in the Bottom-Up Evaluation of Logic Programs (1990)
S. Sudarshan, Divesh Srivastava, Raghu Ramakrishnan, Jeffrey F. Naughton
In the bottom-up evaluation of a logic program, all generated facts are usually assumed to be stored until the end of the evaluation. Considerable gains can be achieved by instead discarding facts...
Practical Selectivity Estimation through Adaptive Sampling (1990)
Richard J. Lipton, Jeffrey F. Naughton, Donovan A. Schneider
Recently we have proposed an adaptive, random sampling algorithm for general query size estimation. In earlier work we analyzed the asymptotic efficiency and accuracy of the algorithm; in this paper...
A comparison of c-store and row-store in a common framework (1566)
Alan Halverson, Jennifer L. Beckmann, Jeffrey F. Naughton, David J. Dewitt
Recently, a “column store ” system called C-Store has shown significant performance benefits by utilizing storage optimizations for a read-mostly query workload. The authors of the C-Store paper...
On the Performance of Object Clustering Techniques
Manolis Tsangaris, Jeffrey F. Naughton
We investigate the performance of some of the best-known object clustering algorithms on four different workloads based upon the Tektronix benchmark. For all four workloads, stochastic clustering...