Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries (2009)
Marios Hadjieleftheriou, Xiaohui Yu, Nick Koudas, Divesh Srivastava
We study selectivity estimation techniques for set similarity queries. A wide variety of similarity measures for sets have been proposed in the past. In this work we concentrate on the class of...
CPM: Adaptive Video-on-Demand with Cooperative Peer Assists and Multicast (2009)
Vijay Gopalakrishnan, Bobby Bhattacharjee, K. K. Ramakrishnan, Rittwik Jana, Divesh Srivastava
Abstract—We present CPM, a unified approach that exploits server multicast, assisted by peer downloads, to provide efficient video-on-demand (VoD) in a service provider environment. We describe our...
Laure Berti-equille, Amélie Marian, Anish Das Sarma, Divesh Srivastava, Xin Luna Dong
The Web has enabled the availability of a huge amount of useful information, but has also eased the ability to spread false information and rumors across multiple sources, making it hard to...
Berti-Equille, Laure, Sarma, Anish Das, Marian, Amelie, Srivastava, Divesh
The Web has enabled the availability of a huge amount of useful information, but has also eased the ability to spread false information and rumors across multiple sources, making it hard to...
Anonymizing Bipartite Graph Data using Safe Groupings ABSTRACT (2009)
Graham Cormode, Divesh Srivastava
Private data often comes in the form of associations between entities, such as customers and products bought from a pharmacy, which are naturally represented in the form of a large, sparse bipartite...
H. V. Jagadish, Nick Koudas, Divesh Srivastava, Ting Yu, N. Koudas, D. Srivastava, ...
or classroom use provided that the copies are not made or distributed for pro t or commercial advantage, the ACM copyright/server notice, the title of the publication, and its date appear, and notice...
Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries ABSTRACT (2009)
Marios Hadjieleftheriou, Xiaohui Yu, Nick Koudas, Divesh Srivastava
We study selectivity estimation techniques for set similarity queries. A wide variety of similarity measures for sets have been proposed in the past. In this work we concentrate on the class of...
Anonymizing Bipartite Graph Data using Safe Groupings ABSTRACT (2009)
Graham Cormode, Divesh Srivastava
Private data often comes in the form of associations between entities, such as customers and products bought from a pharmacy, which are naturally represented in the form of a large, sparse bipartite...
ABSTRACT On Generating Near-Optimal Tableaux for Conditional Functional Dependencies (2009)
Lukasz Golab, Divesh Srivastava
Conditional functional dependencies (CFDs) have recently been proposed as a useful integrity constraint to summarize data semantics and identify data inconsistencies. A CFD augments a functional...
Randomized Synopses for Query Assurance on Data Streams (2008)
Ke Yi, Feifei Li, Marios Hadjieleftheriou, George Kollios, Divesh Srivastava
Abstract — The overwhelming flow of information in many data stream applications forces many companies to outsource to a third-party the deployment of a Data Stream Management System (DSMS) for...
Randomized Synopses for Query Assurance on Data Streams (2008)
Ke Yi, Feifei Li, Marios Hadjieleftheriou, Divesh Srivastava, George Kollios
Due to the overwhelming flow of information in many data stream applications, many companies may not be willing to acquire the necessary resources for deploying a Data Stream Management System...
ABSTRACT Approximate XML Joins (2008)
Sudipto Guha, Divesh Srivastava
XML is widely recognized as the data interchange standard for tomorrow, because of its ability to represent data from a wide variety of sources. Hence, XML is likely to be the format through which...
Fast Indexes and Algorithms for Set Similarity Selection Queries (2008)
Marios Hadjieleftheriou, Amit Ch, Nick Koudas, Divesh Srivastava
Abstract — Data collections often have inconsistencies that arise due to a variety of reasons, and it is desirable to be able to identify and resolve them efficiently. Set similarity queries are...
Exploring a Few Good Tuples From a Text Database (2008)
Jain, Alpa, Srivastava, Divesh
Information extraction from text databases is a useful paradigm to populate relational tables and unlock the considerable value hidden in plain-text documents. However, information extraction can be...
Divesh Srivastava, Data Streams What
! A data stream is a (potentially unbounded) sequence of tuples! Transactional data streams: log interactions between entities! Credit card: purchases by consumers from merchants! Telecommunications:...
Abstract Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs (2008)
Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshant
Logic programs can be evaluated bottom-up by repeat-edly applying alI rules, in “iterations”, until the fixpoint is reached. However, it is often desirable- and in some cases, e.g. programs with...
Fast Computation of Sparse Datacubes Abstract (2008)
Kenneth A. Ross, Divesh Srivastava
Datacube queries compute aggregates over database relations at a variety of granularities, and they constitute an important class of decision support queries. Real-world data is frequently sparse,...
Vagelis Hristidis, Yannis Papakonstantinou, Nick Koudas, Divesh Srivastava
Recent works have shown the benefits of keyword proximity search in querying XML doc-uments in addition to text documents. For example, given query keywords over Shakespeare’s plays in XML, the...
ABSTRACT Approximate XML Joins (2008)
Sudipto Guha, Divesh Srivastava
XML is widely recognized as the data interchange standard for tomorrow, because of its ability to represent data from a wide variety of sources. Hence, XML is likely to be the format through which...
Rapid Identification of Column Heterogeneity (2008)
Bing Tian Dai, Divesh Srivastava, Nick Koudas, Suresh Venkatasubramanian, Beng Chin Ooi
Data quality is a serious concern in every data management application, and a variety of quality measures have been proposed, e.g., accuracy, freshness and completeness, to capture common sources of...
Nick Koudas, Divesh Srivastava, Data Streams What
� A data stream is a (potentially unbounded) sequence of tuples � Transactional data streams: log interactions between entities � Credit card: purchases by consumers from merchants �...
How are Such Problems Created? (2008)
Divesh Srivastava, Human Factors
� Pervasive problem in large databases � Inconsistency with reality: 2 % of records obsolete in customer files in 1 month (deaths, name changes) [DWI02] � Pricing anomalies: UA tickets selling...
Nick Koudas, Divesh Srivastava, Data Streams What
� A data stream is a (potentially unbounded) sequence of tuples � Transactional data streams: log interactions between entities � Credit card: purchases by consumers from merchants �...
Abstract Answering Queries with Aggregation Using Views (2008)
We present novel algorithms for the problem of using materialized views to compute answers to SQL queries with grouping and aggregation, in the presence of multiset tables. In addition to its obvious...
Andrey Balmin, Divesh Srivastava, Yannis Papakonstantinou, Nick Koudas
Keyword proximity search is a user-friendly information discovery technique that has been extensively studied for text documents. In extending this technique to structured databases, recent works [6,...
Sihem Amer-yahia, Divesh Srivastava
XML repositories are usually queried both on structure and content. Due to structural heterogeneity of XML, queries are often interpreted approximately and their answers are returned ranked by...
Abstract Semantic Data Caching and Replacement (2008)
Shaul Dar, Michael J. Franklin, Divesh Srivastava
We propose a semantic model for client-side caching and replacement in a client-server database system and compare this approach to page caching and tuple caching strategies. Our caching model is...
Masaru Kitsuregawa, Betty Salzberg, Gonzalo Navarro, Ricardo Baeza-yates, Erkki Sutinen, Jorma Tarhio, ...
IntegratingDiverseInformationManagementSystems:ABriefSurvey..................................
Luis Gravano, Panagiotis G. Ipeirotis, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Divesh Srivastava
String data is ubiquitous, and its management has taken on particular importance in the past few years. Approximate queries are very important on string data especially for more complex queries...
Luis Gravano, Panagiotis G. Ipeirotis, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Divesh Srivastava
String data is ubiquitous, and its management has taken on particular importance in the past few years. Approximate queries are very important on string data especially for more complex queries...
Benchmarking Declarative Approximate Selection Predicates (2008)
Amit Ch, Oktie Hassanzadeh, Nick Koudas, Mohammad Sadoghi, Divesh Srivastava
Declarative data quality has been an active research topic. The fundamental principle behind a declarative approach to data quality is the use of declarative statements to realize data quality...
REPRESENTING AND QUERYING COMPLEX INFORMATION IN THE CORAL DEDUCTIVE DATABASE SYSTEM (2008)
The development of deductive databases was aimed at providing a declarative, potentially complete query language based on Datalog. However, Datalog lacks features such as aggregation and negation,...
Randomized Synopses for Query Assurance on Data Streams (2008)
Ke Yi, Feifei Li, Marios Hadjieleftheriou, George Kollios, Divesh Srivastava
Abstract — The overwhelming flow of information in many data stream applications forces many companies to outsource to a third-party the deployment of a Data Stream Management System (DSMS) for...
Bing Tian Dai, Divesh Srivastava
Data quality is a serious concern in every data management application, and a variety of quality measures have been proposed, including accuracy, freshness and completeness, to capture the common...
08111 Report -- Ranked XML Querying (2008)
Amer-Yahia, Sihem, Hiemstra, Djoerd, Roelleke, Thomas, Srivastava, Divesh, Weikum, Gerhard
This paper is based on a five-day workshop on "Ranked XML Querying" that took place in Schloss Dagstuhl in Germany in March 2008 and was attended by 27 people from three different research...
08111 Abstracts Collection -- Ranked XML Querying (2008)
Amer-Yahia, Sihem, Srivastava, Divesh, Weikum, Gerhard
From 09.03. to 14.03.08, the Dagstuhl Seminar 08111 ``Ranked XML Querying'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several...
H. V. Jagadish, Divesh Srivastava
SUMMARY Much of the data we deal with every day is organized hierarchically: le systems, library classication schemes and yellow page categories are salient examples. Business data too, benets from a...
Reasoning with Aggregation Constraints in Views (2007)
Shaul Dar, H. V. Jagadish, Alon Y. Levy, Divesh Srivastava
We investigate the problem of using materialized views to compute answers to SQL queries with grouping and aggregation, in the presence of multiset tables. This problem is important in many...
A Visual Language for Interactive Data Exploration (2007)
Peter G. Selfridge, Divesh Srivastava
Introduction Analyzing vast amounts of data to extract "knowledge" is now a business imperative. Typically, attention is focused on learning and data mining algorithms (see, e.g., [AIS93,...
A Visual Language for Interactive Data Exploration and Analysis (2007)
Peter Selfridge, Divesh Srivastava
The analysis of large amounts of data to extract generalizations, exceptions, trends, and hidden relationships is a common activity in the business and scientific communities. While some kinds of...
Sagivz Divesh, Alon Y. Levy, Alberto O. Mendelzony, Yehoshua Sagivz, Divesh Srivastava
We consider the problem of computing answers to queries by using materialized views. Aside from its potential in optimizing query evaluation, the problem also arises in applications such as Global...
Semantics and Optimization of Constraint Queries in Databases (2007)
Raghu Ramakrishnan, Divesh Srivastava
Introduction Our research focuses on the use of constraints to represent and query information in a database. We have worked on two main issues, semantics and query optimization. 2 Optimization of...
Rohit Ananthakrishna, Abhinandan Das, S. Muthukrishnan, Johannes Gehrke, Divesh Srivastava
In many applications such as IP network management, data arrives in streams, and queries over those streams need to be processed online using limited storage. Correlated-sum (CS) aggregates are a...
ABSTRACT Text Joins in an RDBMS for Web Data Integration (2007)
Luis Gravano, Panagiotis G. Ipeirotis, Nick Koudas, Divesh Srivastava
The integration of data produced and collected across autonomous, heterogeneous web services is an increasingly important and challenging problem. Due to the lack of global identifiers, the same...
Using Õ-grams in a DBMS for Approximate String Processing (2007)
Luis Gravano, Panagiotis G. Ipeirotis, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Lauri Pietarinen, ...
String data is ubiquitous, and its management has taken on particular importance in the past few years. Approximate queries are very important on string data. This is due, for example, to the...
Sihem Amer-yahia, Divesh Srivastava
XML permits the interleaving of text with structural and semantic markup in documents. Markup is added to a document by tagging a portion of the text or by augmenting the text with annotations. The...
muthuresearch. art. com (2007)
Flipsresearch Art Com, S. Muthukrishnan, Divesh Srivastava
Reverse Nearest Neighbor (RNN) queries have been studied for finite, stored data sets and are of interest for decision support. However, in many applications such as fixed wireless telephony access...
Luis Gravano, Panagiotis G. Ipeirotis, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Divesh Srivastava
String data is ubiquitous, and its management has taken on particular importance in the past few years. Approximate queries are very important on string data especially for more complex queries...
Flip Korn AT&T Labs--Research (2007)
Zhiyuan Chen, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Raymond Ng, Divesh Srivastava
We describe efficient algorithms for accurately estimating the number of matches of a small node-labeled tree, i.e., a twig, in a large node-labeled tree, using a summary data structure. This problem...
Interaction of Query Evaluation and Buffer Management for Information Retrieval (2007)
Michael J. Franklin, Divesh Srivastava
The proliferation of the World Wide Web has brought information retrieval (IR) techniques to the forefront of search technology. To the average computer user, "searching " now means...
Raghu Ramakrishnan, William G. Roth, Praveen Seshadri, Divesh Srivastava, S. Sudarshan
CORAL [4, 5] is a deductive database system that supports a powerful declarative query language. The language supports general Horn clause logic programs, extended with SQL-style
H. V. Jagadish, Divesh Srivastava
SUMMARY Much of the data we deal with every day is organized hierarchically: file systems, library classification schemes and yellow page categories are salient examples. Business data too, benefits...
Tree Pattern Query Minimization (2007)
Sihem Amer-yahia, Sungran Cho, Divesh Srivastava
Tree patterns form a natural basis to query treestructured data such as XML and LDAP. To improve the efficiency of tree pattern matching, it is essential to quickly identify and eliminate redundant...
LockX: A System for Efficiently Querying Secure XML (2007)
Sungran Cho Stevens, Divesh Srivastava
ommercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific...
INVITED PAPER Special Issue on New Generation Database Technologies (2007)
Revisiting The Hierarchical, H. V. Jagadish, Divesh Srivastava
this paper, we develop a framework for a modern hierarchical data model, substantially improved from the original version by taking advantage of the lessons learned in the relational database...
Intensional Associations Between Data and Metadata (2007)
There is a growing need to associate a variety of metadata with the underlying data, but a simple, elegant approach to uniformly model and query both the data and the metadata has been elusive. In...
Efficient processing of top-k queries on uncertain databases (2007)
Ke Yi, Feifei Li, George Kollios, Divesh Srivastava
Abstract — This work introduces novel polynomial-time algorithms for processing top-k queries in uncertain databases, under the generally adopted model of x-relations. An x-relation consists of a...
Aggregate query answering on anonymized tables (2007)
Qing Zhang, Nick Koudas, Divesh Srivastava, Ting Yu
Privacy is a serious concern when microdata need to be released for ad hoc analyses. The privacy goals of existing privacy protection approaches (e.g., k-anonymity and ℓ-diversity) are suitable...
Aggregate query answering on anonymized tables (2007)
Qing Zhang, Nick Koudas, Divesh Srivastava, Ting Yu
Privacy is a serious concern when microdata need to be released for ad hoc analyses. The privacy goals of existing privacy protection approaches (e.g., �-anonymity and �-diversity) are suitable...
Efficient processing of top-k queries in uncertain databases (2007)
Ke Yi, Feifei Li, George Kollios, Divesh Srivastava
Abstract—This work introduces novel polynomial algorithms for processing top-k queries in uncertain databases under the generally adopted model of x-relations. An x-relation consists of a number of...
Keyword proximity search in XML trees (2006)
Vagelis Hristidis, Nick Koudas, Yannis Papakonstantinou, Divesh Srivastava
Abstract—Recent works have shown the benefits of keyword proximity search in querying XML documents in addition to text documents. For example, given query keywords over Shakespeare’s plays in...
XTreeNet: Scalable Overlay Networks for XML Content Dissemination and Querying (2005)
William Fenner, Divesh Srivastava
Information is increasingly being created, exchanged and stored in the eXtensible Markup Language (XML). To alleviate the problems of “who to ask ” and “who to tell” when connecting XML...
Answering Order-Based Queries Over XML Data (2005)
Zografoula Vagena, Nick Koudas, Divesh Srivastava, Vassilis J. Tsotras
Order-based queries over XML data include XPath navigation axes such as following-sibling and following. In this paper, we present holistic algorithms that evaluate such order-based queries. An...
Structure and Content Scoring for XML (2005)
Sihem Amer-yahia, Divesh Srivastava
XML repositories are usually queried both on structure and content. Due to structural heterogeneity of XML, queries are often interpreted approximately and their answers are returned ranked by...
Streams, Security and Scalability (2005)
Theodore Johnson Muthukrishnan, Theodore Johnson, S. Muthukrishnan, Oliver Spatscheck, Divesh Srivastava
Network-based attacks, such as DDoS attacks and worms, are threatening the continued utility of the Internet. As the variety and the sophistication of attacks grow, early detection of potential...
Structure and Content Scoring for XML (2005)
Sihem Amer-yahia, Divesh Srivastava
XML repositories are usually queried both on structure and content. Due to structural heterogeneity of XML, queries are often interpreted approximately and their answers are returned ranked by...
Efficient Handling of Positional Predicates within XML Query Processing (2005)
Zografoula Vagena, Nick Koudas, Divesh Srivastava, Vassilis J. Tsotras
The inherent order within the XML document-centric data model is typically exposed through positional predicates defined over the XPath navigation axes. Although processing algorithms for each axis...
Multiple Aggregations Over Data Streams (2005)
Rui Zhang Nick, Rui Zhang, Nick Koudas, Beng Chin Ooi, Divesh Srivastava
application for data stream management systems. The need for exploratory IP traffic data analysis naturally leads to posing related aggregation queries on data streams, that differ only in the choice...
XTreeNet: Scalable Overlay Networks for XML Content Dissemination and Querying (Synopsis) (2005)
William Fenner, Michael Rabinovich, K. K. Ramakrishnan, Divesh Srivastava
XML is becoming a ubiquitous format for information exchange on the Internet. To alleviate the problems of "whom to ask" and "whom to tell" when connecting XML information...
Answering Order-Based Queries Over XML Data (2005)
Zografoula Vagena Nick, Nick Koudas, Divesh Srivastava, Vassilis J. Tsotras
Order-based queries over XML data include XPath navigation axes such as following-sibling and following. In this paper, we present holistic algorithms that evaluate such order-based queries. An...
XTreeNet: Scalable Overlay Networks for XML Content Dissemination and Querying (2005)
William Fenner, Divesh Srivastava
XML is becoming a ubiquitous format for information exchange on the Internet. To alleviate the problems of “whom to ask ” and “whom to tell ” when connecting XML information producers with...
Index Structures for Matching XML Twigs Using Relational Query Processors (2004)
Chen, Zhiyuan, Gehrke, Johannes, Korn, Flip, Koudas, Nick, Shanmugasundaram, Jayavel, Srivastava, Divesh
Various index structures have been proposed to speed up the evaluation of XML path expressions. However, existing XML path indices suffer from at least one of three limitations: they focus only on...
Index Structures for Matching XML Twigs Using Relational Query Processors (2004)
Chen, Zhiyuan, Gehrke, Johannes, Korn, Flip, Koudas, Nick, Shanmugasundaram, Jayavel, Srivastava, Divesh
Various index structures have been proposed to speed up the evaluation of XML path expressions. However, existing XML path indices suffer from at least one of three limitations: they focus only on...
Flexible string matching against large databases in practice (2004)
Nick Koudas, Amit Marathe, Divesh Srivastava
Data Cleaning is an important process that has been at the center of research interest in recent years. Poor data quality is the result of a variety of reasons, including data entry errors and...
Merging the Results of Approximate Match Operations (2004)
Sudipto Guha, Nick Koudas, Amit Marathe, Divesh Srivastava
Data Cleaning is an important process that has been at the center of research interest in recent years. An important end goal of effective data cleaning is to identify the relational tuple or tuples...
Teaching Relational Optimizers about XML Processing (2004)
Sihem Amer-yahia, Yannis Kotidis, Divesh Srivastava
Due to their numerous benefits, relational systems play a major role in storing XML documents. XML also benefits relational systems by providing a means to publish legacy relational data....
Teaching Relational Optimizers about XML Processing (2004)
Sihem Amer-yahia, Yannis Kotidis, Divesh Srivastava
Due to their numerous benefits, relational systems play a major role in storing XML documents. XML also benefits relational systems by providing a means to publish legacy relational data....
Flexible String Matching Against Large Databases in Practice (2004)
Nick Koudas Amit, Amit Marathe, Divesh Srivastava
Data Cleaning is an important process that has been at the center of research interest in recent years. Poor data quality is the result of a variety of reasons, including data entry errors and...
Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data (2004)
Graham Cormode, Flip Korn, S. Muthukrishnan, Divesh Srivastava
Data items archived in data warehouses or those that arrive online as streams typically have attributes which take values from multiple hierarchies (e.g., time and geographic location; source and...
Colorful XML: One hierarchy isn’t enough (2004)
H. V. Jagadish, Divesh Srivastava
XML has a tree-structured data model, which is used to uniformly represent structured as well as semi-structured data, and also enable concise query specification in XQuery, via the use of its XPath...
Colorful XML: One hierarchy isn’t enough (2004)
H. V. Jagadish, Divesh Srivastava
XML has a tree-structured data model, which is used to uniformly represent structured as well as semi-structured data, and also enable concise query specification in XQuery, via the use of its XPath...
Approximate String Joins in a Database (Almost) for Free -- Erratum (2003)
Gravano, Luis, G., Panagiotis, Srivastava, Divesh
No Abstract
Text Joins in an RDBMS for Web Data Integration (2003)
Gravano, Luis, Ipeirotis, Panagiotis G., Koudas, Nick, Srivastava, Divesh
The integration of data produced and collected across autonomous, heterogeneous web services is an increasingly important and challenging problem. Due to the lack of global identifiers, the same...
Efficient approximation of optimization queries under parametric aggregation constraints (2003)
Sudipto Guha, Divesh Srivastava
We introduce and study a new class of queries that we refer to as OPAC (optimization under parametric aggregation constraints) queries. Such queries aim to identify sets of database tuples that...
Panayiotis Tsaparas, Themistoklis Palpanas, Yannis Kotidis, Nick Koudas, Divesh Srivastava
A plethora of data sources contain data entities that could be ordered according to a variety of attributes associated with the entities. Such orderings result effectively in a ranking of the...
Timber: A native system for querying XML (2003)
Stelios Paparizos, Shurug Al-khalifa, Adriane Chapman, Jignesh M. Patel, Divesh Srivastava, Nuwee Wiwatwattana, ...
XML has become ubiquitous, and XML data has to be managed in databases. The current industry standard is to map XML data into relational tables and store this information in a relational database....
Timber: A native system for querying XML (2003)
Stelios Paparizos, Shurug Al-khalifa, Adriane Chapman, Jignesh M. Patel, Divesh Srivastava, Nuwee Wiwatwattana, ...
XML has become ubiquitous, and XML data has to be managed in databases. The current industry standard is to map XML data into relational tables and store this information in a relational database....
Efficient approximation of optimization queries under parametric aggregation constraints (2003)
Sudipto Guha, Dimitrios Gunopulos, Nick Koudas, Divesh Srivastava, Michail Vlachos
We introduce and study a new class of queries that we refer to as OPAC (optimization under parametric aggregation constraints) queries. Such queries aim to identify sets of database tuples that...
Text Joins for Data Cleansing and Integration in an RDBMS (2003)
Luis Gravano, Panagiotis G. Ipeirotis, Nick Koudas, Divesh Srivastava
An organization’s data records are often noisy because of transcription errors, incomplete information, lack of standard formats for textual data or combinations thereof. A fundamental task in a...
Approximate String Joins in a Database (Almost) for Free (2003)
Erratum Luis Gravano, Luis Gravano, Panagiotis G. Ipeirotis, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, ...
case the result returned by the Figure 1 query is incomplete and su#ers from "false negatives," in contrast to our claim to the contrary in [GIJ 01b]. In general, the string pairs that are...
Efficient Approximation of Optimization Queries Under Parametric (2003)
Aggregation Constraints Sudipto, Sudipto Guha, Divesh Srivastava
We introduce and study a new class of queries that we refer to as OPAC (optimization under parametric aggregation constraints) queries. Such queries aim to identify sets of database tuples that...
PIX: A System for Phrase Matching in XML Documents: A Demonstration (2003)
We present a system that enables flexible and efficient phrase matching in XML documents. Since XML allows structured and unstructured information to be interleaved, phrase matching in XML raises new...
Efficient Approximation of Optimization Queries Under Parametric (2003)
Aggregation Constraints Sudipto, Sudipto Guha, Divesh Srivastava
We introduce and study a new class of queries that we refer to as OPAC (optimization under parametric aggregation constraints) queries. Such queries aim to identify sets of database tuples that...
LockX: A System for Efficiently Querying Secure XML (2003)
Sungran Cho Stevens, Divesh Srivastava
ommercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific...
Nick Koudas And, Nick Koudas, Divesh Srivastava, Data Streams What
logical/physical streams and signatures Express I/O and CPU efficient signature programs cleanly Lesson: Essential to consider I/O issues for data streams AT&T Labs-Research 7 Hancock: Data...
PIX: Exact and Approximate Phrase Matching in XML (2003)
Sihem Amer-yahia, Divesh Srivastava
INTRODUCTION XML permits the interleaving of text with structural and semantic markup in documents. Markup is added to a document by tagging a portion of the text or by augmenting the text with...
Distributed Evaluation of Network Directory Queries (2003)
Sihem Amer-Yahia, Divesh Srivastava, Ieee Computer Society, Dan Suciu
This paper describes novel efficient techniques for the distributed evaluation of hierarchical aggregate selection queries over LDAP directory data, distributed across multiple autonomous directory...
Mary Fernández, Divesh Srivastava
Phrase matching is a common IR technique to search text and identify relevant documents in a document collection. Phrase matching in XML presents new challenges as text may be interleaved with...
Navigation- vs. Index-Based XML Multi-Query Processing (2003)
Nicolas Bruno Luis, Luis Gravano, Nick Koudas, Divesh Srivastava
XML path queries form the basis of complex filtering of XML data. Most current XML path query processing techniques can be divided in two groups. Navigation-based algorithms compute results by...
Finding hierarchical heavy hitters in data streams (2003)
Graham Cormode, S. Muthukrishnan, Divesh Srivastava
Aggregation along hierarchies is a critical summary technique in a large variety of online applications including decision support, and network management (e.g., IP clustering, denial-of-service...
Holistic Twig Joins: Optimal XML Pattern Matching (2002)
Bruno, Nicolas, Koudas, Nick, Srivastava, Divesh
XML employs a tree-structured data model, and, naturally, XML queries specify patterns of selection predicates on multiple elements related by a tree structure. Finding all occurrences of such a twig...
Efficient OLAP query processing in distributed data warehouses (2002)
Michael O. Akinde, Michael H. Böhlen, Theodore Johnson, Laks V. S, Divesh Srivastava
Abstract. The success of Internet applications has led to an explosive growth in the demand for bandwidth from ISPs. Managing an IP network requires collecting and analyzing network data, such as...
Counting Relaxed Twig Matches in a Tree (2002)
Dongwon Lee, Divesh Srivastava
Abstract. We consider the problem of accurately estimating the number of approximate XML answers for a given query, and propose an efficient method that (1) accurately computes selectivity estimates...
TIMBER: A Native XML Database (2002)
H. V. Jagadish, Shurug Al-khalifa, Adriane Chapman, Andrew Nierman, Stelios Paparizos, ...
Abstract. This paper describes the overall design and architecture of the Timber XML database system currently being implemented at the University of Michigan. The system is based upon a bulk algebra...
Compressed Accessibility Map: Efficient Access Control for XML (2002)
Ting Yu, Divesh Srivastava, H. V. Jagadish
XML is widely regm'ded as a promising memm for data representation integq'ation, md exchmge. As compmfies trmmact business over the Internet, the sensitive nature of the information mmdates...
Optimizing the secure evaluation of twig queries (2002)
Sungran Cho, Sihem Amer-yahia, Divesh Srivastava
The rapid emergence of XML as a standard for data exchange over the Web has led to considerable interest in the problem of securing XML documents. In this context, query eva]-uation engines need to...
TIMBER: A Native XML Database (2002)
H. V. Jagadish, Shurug Al-khalifa, Adriane Chapman, Andrew Nierman, Stelios Paparizos, ...
The date of receipt and acceptance will be inserted by the editor Abstract This paper describes the overall design and architecture of the Timber XML database system currently being implemented at...
Stelios Paparizos, Shurug Al-khalifa, H. V. Jagadish, Laks Lakshmanan, Andrew Nierman, Divesh Srivastava, ...
Abstract. XML permits repeated and missing sub-elements, and missing attributes. We discuss the consequent implications on grouping, both with respect to specification and with respect to...
Structural joins: a primitive for efficient XML query pattern matching (2002)
Shurug Al-khalifa, H. V. Jagadish, Nick Koudas, Jignesh M. Patel, Divesh Srivastava, Yuqing Wu
XML queries typically specify patterns of selection predicates on multiple elements that have some specified tree structured relationships. The primitive tree structured relationships are...
Efficient OLAP Query Processing in Distributed Data Warehouses (2002)
Michael Akinde Strategy, Michael Akinde, Michael Böhlen, Theodore Johnson, Divesh Srivastava
sets of the detail data. Skalla generates distributed query evaluation plans (for the coordinator architecture) as a sequence of rounds, where a round consists of: (i) each local site performing some...
Sudipto Guha, Divesh Srivastava
XML is widely recognized as the data interchange standard for tomorrow, because of its ability to represent data from a wide variety of sources. Hence, XML is likely to be the format through which...
TIMBER: A Native XML Database (2002)
H. V. Jagadish, Adriane Chapman, Andrew Nierman, Stelios Paparizos, ...
This paper describes the overall design and architecture of the Timber XML database system currently being implemented at the University of Michigan. The system is based upon a bulk algebra for...
Efficient OLAP Query Processing in Distributed Data Warehouses (2002)
Michael O. Akinde, Michael H. Böhlen, Theodore Johnson, Laks V. S, Divesh Srivastava
The success of Internet applications has led to an explosive growth in the demand for bandwidth from ISPs. Managing an IP network requires collecting and analyzing network data, such as flow-level...
Fast Algorithms for Hierarchical Range Histogram Construction (2002)
Sudipto Guha, Nick Koudas, Divesh Srivastava
Data Warehousing and OLAP applications typically view data as having multiple logical dimensions (e.g., product, location) with natural hierarchies defined on each dimension. OLAP queries usually...
Efficient OLAP query processing in distributed data warehouses (2002)
Michael Akinde, Michael Böhlen, Theodore Johnson, Divesh Srivastava
The success of Internet applications has led to an explosive growth in the demand for bandwidth from ISPs. Managing an IP network includes complex data analysis (see, e.g., [1]) that can often be...
A Mapping Schema and Interface for XML Stores (2002)
Most XML storage efforts have focused on mapping documents to relational databases. Mapping choices range from storing documents verbatim to shredding documents into relations in various ways. These...
Tree Pattern Relaxation (2002)
Sihem Amer-yahia, Sungran Cho, Divesh Srivastava
Tree patterns are fundamental to querying tree-structured data like XML. Because of the heterogeneity of XML data, it is often more appropriate to permit approximate query matching and return ranked...
Tree Pattern Relaxation (2002)
Sungran Cho, Divesh Srivastava
Tree patterns are fundamental to querying tree-structured data like XML. Because of the heterogeneity of XML data, it is often more appropriate to permit approximate query matching and return ranked...
Structural Joins: A Primitive for Efficient XML Query Pattern Matching (2002)
H. V. Jagadish, Nick Koudas, Jignesh M. Patel, Divesh Srivastava, Yuqing Wu
XML queries typically specify patterns of selection predicates on multiple elements that have some specified tree structured relationships. The primitive tree structured relationships are...
Logical and Physical Support for Heterogeneous Data (2002)
Mary Fern, Rick Greer, Divesh Srivastava
Heterogeneity arises naturally in virtually all real-world data. This paper presents evolutionary extensions to a relational database system for supporting three classes of data heterogeneity:...
Stelios Paparizos Shurug, Stelios Paparizos, Shurug Al-khalifa, H. V. Jagadish, Laks Lakshmanan, Andrew Nierman, ...
XML permits repeated and missing sub-elements, and missing attributes. We discuss the consequent implications on grouping, both with respect to specification and with respect to implementation. The...
Tree pattern relaxation (2002)
Sungran Cho, Divesh Srivastava
Tree patterns are fundamental to querying tree-structured data like XML. Because of the heterogeneity of XML data, it is often more appropriate to permit approximate query matching and return ranked...
Approximate string joins in a database (almost) for free (2001)
Luis Gravano, Panagiotis G. Ipeirotis, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Divesh Srivastava
In [GIJ + 01a, GIJ + 01b] we described how to use q-grams in an RDBMS to perform approximate string joins. We also showed how to implement the approximate join using plain SQL queries. Specifically,...
Using q-grams in a DBMS for Approximate String Processing (2001)
Luis Gravano, Panagiotis G. Ipeirotis, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Lauri Pietarinen, ...
String data is ubiquitous, and its management has taken on particular importance in the past few years. Approximate queries are very important on string data. This is due, for example, to the...
TAX: A tree algebra for XML (2001)
H. V. Jagadish, Divesh Srivastava, Keith Thompson
Querying XML has been the subject of much recent investigation. A formal bulk algebra is essential for applying database-style optimization to XML queries. We develop such an algebra, called TAX...
Minimization of tree pattern queries (2001)
Sihem Amer-yahia, Sungran Cho, Divesh Srivastava
Tree patterns form a natural basis to query tree-structured data such as XML and LDAP. Since the efficiency of tree pattern matching against a tree-structured database depends on the size of the...
Approximate string joins in a database (almost) for free (2001)
Luis Gravano, Panagiotis G. Ipeirotis, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Divesh Srivastava
String data is ubiquitous, and its management has taken on particular importance in the past few years. Approximate queries are very important on string data especially for more complex queries...
Minimization of Tree Pattern Queries (2001)
Sihem Amer-Yahia, Sungran Cho, Divesh Srivastava
Tree patterns form a natural basis to query tree-structured data such as XML and LDAP. Since the efficiency of tree pattern matching against a tree-structured database depends on the size of the...
Using q-grams in a DBMS for Approximate String Processing (2001)
Luis Gravano, Panagiotis G. Ipeirotis, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Lauri Pietarinen, ...
String data is ubiquitous, and its management has taken on particular importance in the past few years. Approximate queries are very important on string data. This is due, for example, to the...
One-dimensional and multi-dimensional substring selectivity estimation (2000)
Kapitskaia, Olga, Srivastava, Divesh, Jagadish, H.V., Ng, Raymond T.
With the increasing importance of XML, LDAP directories, and text-based information sources on the Internet, there is an ever-greater need to evaluate queries involving (sub)string matching. In many...
On bounding-schemas for LDAP directories (2000)
Sihem Amer-yahia, H. V. Jagadish, Divesh Srivastava
As our world gets more networked, ever increasing amounts of information---e.g., about people, network resources, and policies---are being stored in directories, in particular, in X.500 style...
Evolution and Revolutions in LDAP Directory Caches (2000)
Olga Kapitskaia Raymond, Raymond T. Ng, Divesh Srivastava
. LDAP directories have recently proliferated with the growth of the Internet, and are being used in a wide variety of network-based applications. In this paper, we propose the use of generalized...
On Effective Multi-Dimensional Indexing for Strings (2000)
H. V. Jagadish, Nick Koudas, Divesh Srivastava
As databases have expanded in scope from storing purely business data to include XML documents, product catalogs, e-mail messages, and directory data, it has become increasingly important to search...
Optimal Histograms for Hierarchical Range Queries (Extended Abstract) (2000)
Nick Koudas, S. Muthukrishnan, Divesh Srivastava
) Nick Koudas AT&T Labs--Research koudas@research.att.com S. Muthukrishnan AT&T Labs--Research muthu@research.att.com Divesh Srivastava AT&T Labs--Research divesh@research.att.com 1...
On Bounding-Schemas for LDAP Directories (2000)
Sihem Amer-yahia, H. V. Jagadish, Divesh Srivastava
As our world gets more networked, ever increasing amounts of information---e.g., about people, network resources, and policies---are being stored in directories, in particular, in X.500 style...
Querying network directories (1999)
H. V. Jagadish, Tova Milo, Divesh Srivastava, Dimitra Vista
Hierarchically structured directories have recently proliferated with the growth of the Internet, and are being used to store not only address books and contact information for people, but also...
Using LDAP Directory Caches (1999)
Sophie Cluet, Inria Rocquencourt, Olga Kapitskaia, Divesh Srivastava
LDAP (Lightweight Directory Access Protocol) directories have recently proliferated with the growth of the Internet, and are being used in a wide variety of network-based applications to store data...
The Data Warehouse of Newsgroups (1999)
Himanshu Gupta, Divesh Srivastava
. Electronic newsgroups are one of the primary means for the dissemination, exchange and sharing of information. We argue that the current newsgroup model is unsatisfactory, especially when posted...
On Bounding-Schemas for LDAP Directories (1999)
Sihem Amer-yahia, H. V. Jagadish, Divesh Srivastava
. As our world gets more networked, ever increasing amounts of information are being stored in LDAP directories. While LDAP directories have considerable flexibility in the modeling and retrieval of...
Using LDAP Directory Caches (1999)
Sophie Cluet, Inria Rocquencourt, Olga Kapitskaia, Divesh Srivastava
this paper, we consider the problem of reusing cached LDAP directory entries for answering (declarative) LDAP queries. We develop a suite of query transformations that capture the semantics of LDAP...
What can Hierarchies do for Data Warehouses? (1999)
H. V. Jagadish, Divesh Srivastava
Data in a warehouse typically has multiple dimensions of interest, such as location, time, and product. It is well-recognized that these dimensions have hierarchies defined on them, such as...
Multi-Dimensional Substring Selectivity Estimation (1999)
H. V. Jagadish, Olga Kapitskaia, Raymond T. Ng, Divesh Srivastava
With the explosion of the Internet, LDAP directories and XML, there is an ever greater need to evaluate queries involving (sub)string matching. In many cases, matches need to be on multiple...
Snakes and Sandwiches: Optimal Clustering Strategies for a Data Warehouse (1999)
H. V. Jagadish, Jagadish Of Illinois, Divesh Srivastava
Physical layout of data is a crucial determinant of performance in a data warehouse. The optimal clustering of data on disk, for minimizing expected I/O, depends on the query workload. In practice,...
What can Hierarchies do for Data Warehouses? (1999)
Jagadish Of Michigan, H. V. Jagadish, Divesh Srivastava
Data in a warehouse typically has multiple dimensions of interest, such as location, time, and product. It is well-recognized that these dimensions have hierarchies defined on them, such as...
Querying Network Directories (1999)
H. V. Jagadish, Jagadish Of Illinois, Tova Milo, Divesh Srivastava, Dimitra Vista
Hierarchically structured directories have recently proliferated with the growth of the Internet, and are being used to store not only address books and contact information for people, but also...
Snakes and Sandwiches: Optimal Clustering Strategies for a Data Warehouse (1999)
H. V. Jagadish, U Of Illinois, Divesh Srivastava
Physical layout of data is a crucial determinant of performance in a data warehouse. The optimal clustering of data on disk, for minimizing expected I/O, depends on the query workload. In practice,...
The Data Warehouse of Newsgroups (1999)
Himanshu Gupta, Divesh Srivastava
. Electronic newsgroups are one of the primary means for the dissemination, exchange and sharing of information. We argue that the current newsgroup model is unsatisfactory, especially when posted...
Substring Selectivity Estimation (1999)
H. V. Jagadish, U Of Illinois, Raymond T. Ng, Divesh Srivastava
With the explosion of the Internet, LDAP directories and XML, there is an ever greater need to evaluate queries involving (sub)string matching. Effective query optimization in this context requires...
Querying Network Directories (1999)
H. V. Jagadish, U Of Illinois, Tova Milo, Divesh Srivastava, Dimitra Vista
Hierarchically structured directories have recently proliferated with the growth of the Internet, and are being used to store not only address books and contact information for people, but also...
Using LDAP Directory Caches (1999)
Sophie Cluet, Inria Rocquencourt, Olga Kapitskaia, Divesh Srivastava
this paper, we consider the problem of reusing cached LDAP directory entries for answering (declarative) LDAP queries. We develop a suite of query transformations that capture the semantics of LDAP...
Snakes and sandwiches: Optimal clustering strategies for a data warehouse (1999)
H. V. Jagadish, Divesh Srivastava
Physical layout of data is a crucial determinant of performance in a data warehouse. The optimal clustering of data on disk, for minimizing expected I/O, depends on the query workload. In practice,...
The Data Warehouse of Newsgroups (1999)
Himanshu Gupta, Divesh Srivastava
Abstract. Electronic newsgroups are one of the primary means for the dissemination, exchange and sharing of information. We argue that the current newsgroup model is unsatisfactory, especially when...
Querying network directories (1999)
H. V. Jagadish, Divesh Srivastava, Dimitra Vista
Hierarchically structured directories have recently proliferated with the growth of the Internet, and are being used to store not only address books and contact information for people, but also...
Generating Advanced Query Interfaces (1998)
Dongwon Lee, Divesh Srivastava, Dimitra Vista
With the increasing popularity oftheWorld Wide Web, the number of information sources providing access to various types of data has increased considerably. While simple data retrieval queries are...
Evaluating Answer Quality/Efficiency Tradeoffs (1998)
Ugur Cetintemel, Bjorn T. J'onsson, Michael J. Franklin, C. Lee Giles, Divesh Srivastava
For many emerging applications and environments, information systems designers and implementers must consider the tradeoffs between efficiency and the quality of query answers. This flexibility,...
Interaction of Query Evaluation and Buffer Management for Information Retrieval (1998)
Bj Orn, Michael J. Franklin, Divesh Srivastava
The proliferation of the World Wide Web has brought information retrieval (IR) techniques to the forefront of search technology. To the average computer user, "searching" now means using...
Focusing Search in Hierarchical Structures with Directory Sets (1998)
Guy Jacobson, Balachander Krishnamurthy, Divesh Srivastava, Dan Suciu
Keyword-based searches on the World Wide Web are often of limited use, because they return too many uninteresting matches. We propose here a novel mechanism that permits the user to specify directory...
Generating Advanced Query Interfaces (1998)
Dongwon Lee Divesh, Dongwon Lee, Divesh Srivastava, Dimitra Vista
With the increasing popularity of the World Wide Web, the number of information sources providing access to various types of data has increased considerably. While simple data retrieval queries are...
Complex Aggregation at Multiple Granularities (1998)
Kenneth Ross, Divesh Srivastava, Damianos Chatziantoniou
. Datacube queries compute simple aggregates at multiple granularities. In this paper we examine the more general and useful problem of computing a complex subquery involving multiple dependent...
Generating Advanced Query Interfaces (1998)
Dongwon Lee, Divesh Srivastava, Dimitra Vista, Rm B
g the burden from users of having to know the interface and query language specifics of the individual information sources. The tool accepts as input a high-level specification of the interface and...
Complex Aggregation at Multiple Granularities (1998)
Kenneth Ross Divesh, Kenneth A. Ross, Divesh Srivastava, Damianos Chatziantoniou
. Datacube queries compute simple aggregates at multiple granularities. In this paper we examine the more general and useful problem of computing a complex subquery involving multiple dependent...
Evaluating Answer Quality/Efficiency Tradeoffs (1998)
Ugur Cetintemel, Björn T. Jónsson, Michael J. Franklin, C. Lee Giles, Divesh Srivastava
For many emerging applications and environments, information systems designers and implementors must consider the tradeoffs between efficiency and the quality of query answers. This flexibility,...
Focusing Search in Hierarchical Structures with Directory Sets (1998)
Guy Jacobson, Balachander Krishnamurthy, Divesh Srivastava, Dan Suciu
Keyword-based searches on the World Wide Web are often of limited use, because they return too many uninteresting matches. We propose here a novel mechanism that permits the user to specify directory...
Evaluating Answer Quality/Efficiency Tradeoffs (1998)
Ugur Cetintemel, Bjorn T. J'onsson, Michael J. Franklin, C. Lee Giles, Divesh Srivastava
For many emerging applications and environments, information systems designers and implementers must consider the tradeoffs between efficiency and the quality of query answers. This flexibility,...
Flexible List Management in a Directory (1998)
Jagadish Att, H. V. Jagadish, Mark A. Jones, Divesh Srivastava
Lists of entities must often be specified in many real-world applications such as customer lists, electronic distribution lists and access control lists. These lists are typically specified through...
Interaction of Query Evaluation and Buffer Management for Information Retrieval (1998)
Björn T. Jónsson, Michael J. Franklin, Divesh Srivastava
The proliferation of the World Wide Web has brought information retrieval (IR) techniques to the forefront of search technology. To the average computer user, "searching" now means using...
Fast Computation of Sparse Datacubes (1997)
Kenneth A. Ross, Divesh Srivastava
Datacube queries compute aggregates over database relations at a variety of granularities, and they constitute an important class of decision support queries. Real-world data is frequently sparse,...
Fast Computation of Sparse Datacubes (1997)
Kenneth Ross, Divesh Srivastava
Datacube queries compute aggregates over database relations at a variety of granularities, and they constitute an important class of decision support queries. Real-world data is frequently sparse,...
Selecting and Maintaining Materialized Views for Message Management (1997)
Himanshu Gupta, Divesh Srivastava
Electronic messaging has become one of the primary means for the dissemination, exchange and sharing of information. This is facilitated, especially within an organization, by the use of shared...
Materialized view maintenance and integrity constraint checking: Trading space for time (1996)
Kenneth A. Ross, Divesh Srivastava
Abstract We investigate the problem of incremental maintenance of an SQL view in the face of database updates, and show that it is possible to reduce the total time cost of view maintenance by...
Chasing Constrained Tuple-Generating Dependencies (1996)
Michael J. Maher, Divesh Srivastava
We investigate the implication problem for constrained tuple-generating dependencies (CTGDs), the extension of tuple- and equality-generating dependencies that permits expression of semantic...
Cost-based optimization for magic: algebra and implementation (1996)
Praveen Seshadri, Joseph M. Hellerstein, Hamid Pirahesh, Raghu Ramakrishnan, Divesh Srivastava, ...
Magic sets rewriting is a well-known optimization heuristic for complex decision-support queries. There can be many variants of this rewriting even for a single query, which differ greatly in...
Chasing Constrained Tuple-Generating Dependencies (1996)
Michael J. Maher, Divesh Srivastava
We investigate the implication problem for constrained tuple-generating dependencies (CTGDs), the extension of tuple- and equality-generating dependencies that permits expression of semantic...
Semantic Data Caching and Replacement (1996)
Shaul Dar, Michael J. Franklin, Björn T. Jónsson, Divesh Srivastava, Michael Tan
We propose a semantic model for client-side caching and replacement in a client-server database system and compare this approach to page caching and tuple caching strategies. Our caching model is...
Semantic Data Caching and Replacement (1996)
Shaul Dar Michael, Michael J. Franklin, Bjorn T. Jonsson, Divesh Srivastava, Michael Tan
We propose a semantic model for client-side caching and replacement in a client-server database system and compare this approach to page caching and tuple caching strategies. Our caching model is...
Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time (1996)
Kenneth Ross, Divesh Srivastava, S. Sudarshan
We investigate the problem of incremental maintenance of an SQL view in the face of database updates, and show that it is possible to reduce the total time cost of view maintenance by materializing...
Semantic Data Caching and Replacement (1996)
Shaul Dar, Michael J. Franklin, Bjorn T. Jonsson, Divesh Srivastava, Michael Tan
We propose a semantic model for client-side caching and replacement in a client-server database system and compare this approach to page caching and tuple caching strategies. Our caching model is...
Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time (1996)
Kenneth Ross, Divesh Srivastava, S. Sudarshan
We investigate the problem of incremental maintenance of an SQL view in the face of database updates, and show that it is possible to reduce the total time cost of view maintenance by materializing...
Answering Queries with Aggregation Using Views (1996)
Divesh Srivastava, Shaul Dar, H. V. Jagadish, Alon Y. Levy
We present novel algorithms for the problem of using materialized views to compute answers to SQL queries with grouping and aggregation, in the presence of multiset tables. In addition to its obvious...
IDEA: Interactive Data Exploration and Analysis (1996)
Peter G. Selfridge, Divesh Srivastava, Lynn O. Wilson
The analysis of business data is often an ill-defined task characterized by large amounts of noisy data. Because of this, business data analysis must combine two kinds of intertwined tasks:...
Chasing Constrained Tuple-Generating Dependencies (1996)
Michael J. Maher, Divesh Srivastava
We investigate the implication problem for constrained tuple-generating dependencies (CTGDs), the extension of tuple- and equality-generating dependencies that permits expression of semantic...
Cost-based optimization for magic: algebra and implementation (1996)
Praveen Seshadri, Raghu Ramakrishnan, Joseph M. Hellerstein, Divesh Srivastava
Magic sets rewriting is a well-known optimization heuristic for complex decision-support queries. There can be many variants of this rewriting even for a single query, which differ greatly in...
Answering queries with aggregation using views (1996)
Divesh Srivastava, Shaul Dar, H. K Jagadish, Alon Y. Levy
We present novel algorithms for the problem of using materialized views to compute answers to SQL queries with grouping and aggregation, in the presence of multiset tables. ln addition to its obvious...
Bottom-up Evaluation and Query Optimization of Well-Founded Models (1995)
David B. Kemp, Divesh Srivastava, Peter J. Stuckey
We present a bottom-up operational procedure for computing well-founded models of allowed programs with negation. This procedure provides a practical method of handling programs that involve...
Bottom-up Evaluation and Query Optimization of Well-Founded Models (1995)
David Kemp, Divesh Srivastava, Peter J. Stuckey
We present a bottom-up operational procedure for computing well-founded models of allowed programs with negation. This procedure provides a practical method of handling programs that involve...
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...
Answering Queries Using Views (1995)
Extend Ed, Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava
) Alon Y. Levy AT&T Bell Laboratories levy@research.att.com Alberto O. Mendelzon University of Toronto mendel@db.toronto.edu Yehoshua Sagiv y Hebrew University, Jerusalem sagiv@cs.huji.ac.il...
Answering Queries Using Views (1995)
Alon Levy, Alberto Mendelzon, Yehoshua Sagiv, Divesh Srivastava
) Alon Y. Levy AT&T Bell Laboratories levy@research.att.com Alberto O. Mendelzon University of Toronto mendel@db.toronto.edu Yehoshua Sagiv y Hebrew University, Jerusalem sagiv@cs.huji.ac.il...
The CORAL Deductive System (1994)
Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan, Praveen Seshadri
CORAL is a deductive system which supports a rich declarative language, and an interface to C++ which allows for a combination of declarative and imperative programming. The declarative query...
Towards Efficient Information Gathering Agents (1994)
Alon Levy, Yehoshua Sagiv, Divesh Srivastava
Information gathering agents are required in many software agent applications to answer queries, posed by other agents, using a variety of available information sources. We formally consider the...
Foundations of Aggregation Constraints (1994)
Kenneth Ross, Divesh Srivastava, Peter J. Stuckey, S. Sudarshan
We introduce a new constraint domain, aggregation constraints, that is useful in database query languages, and in constraint logic programming languages that incorporate aggregate functions. We...
The CORAL Deductive System (1994)
Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan, Praveen Seshadri
CORAL is a deductive system which supports a rich declarative language, and an interface to C++ which allows for a combination of declarative and imperative programming. The declarative query...
Efficient Incremental Evaluation of Queries with Aggregation (1994)
Raghu Ramakrishnan, Kenneth A. Ross, Divesh Srivastava, S. Sudarshan
We present a technique for efficiently evaluating queries on programs with monotonic aggregation, a class of programs defined by Ross and Sagiv. Our technique consists of the following components:...
The Valid Model Semantics for Logic Programs (1994)
Catriel Beeri, Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan
We present the valid model semantics, a new approach to providing semantics for logic programs with negation, setterms and grouping. The valid model semantics is a threevalued semantics, and is...
Divesh Srivastava, Raghu Ramakrishnan, Peter Z. Revesz
. We describe the Constraint Object Data Model (CODM), which enhances an object-based data model with existential constraints to naturally represent partially specified information. We present the...
Foundations of Aggregation Constraints (1994)
Kenneth A. Ross, Divesh Srivastava, Peter J. Stuckey, S. Sudarshan
. We introduce a new constraint domain, aggregation constraints, which is useful in database query languages, and in constraint logic programming languages that incorporate aggregate functions. We...
Foundations of Aggregation Constraints (1994)
Kenneth A. Ross, Divesh Srivastava, Peter J. Stuckey, S. Sudarshan
We introduce a new constraint domain, aggregation constraints, that is useful in database query languages, and in constraint logic programming languages that incorporate aggregate functions. We...
Efficient Incremental Evaluation of Queries with Aggregation (1994)
Raghu Ramakrishnan, Kenneth A. Ross, Divesh Srivastava, S. Sudarshan
We present a technique for efficiently evaluating queries on programs with monotonic aggregation, a class of programs defined by Ross and Sagiv. Our technique consists of the following components:...
Towards Efficient Information Gathering Agents (1994)
Alon Levy, Yehoshua Sagiv, Divesh Srivastava
Information gathering agents are required in many software agent applications to answer queries, posed by other agents, using a variety of available information sources. We formally consider the...
The CORAL Deductive System (1994)
Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan, Praveen Seshadri
Abstract. CORAL is a deductive system that supports a rich declarative language, and an interface to C+ +, which allows for a combination of declarative and imperative programming. A CORAL...
Typescript.
Explaining program execution in deductive systems (1993)
Tarun Arora, Raghu Ramakrishnan, William G. Roth, Praveen Seshadri, Divesh Srivastava
Abstract. Programs in deductive database and programming systems have a natural meaning that is based upon their mathematical reading as logical rules. High-level `explanations ' of a program...
Implementation of the CORAL deductive database system (1993)
Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan, Praveen Seshadri
CORAL is a deductive database system that supports a rich declarative language, provides a wide range of evaluation methods, and allows a combination of declarative and imperative programming. The...
Coral++: Adding object-orientation to a logic database language (1993)
Divesh Srivastava, Raghu Ramakrishnan, Praveen Seshadri, S. Sudarshan
Coral++ is a database programming language that integrates Coral [23] with the C++ type system. The data model allows arbitrary C++ objects in database facts, and the declarative query language...
Extending the Well-Founded and Valid Semantics for Aggregation (1993)
S. Sudarshan, Divesh Srivastava, Raghu Ramakrishnan
We present a very general technique for defining semantics for programs that use aggregation. We use the technique to extend the well-founded semantics and the valid semantics, both of which were...
Extending the Well-Founded and Valid Semantics for Aggregation (1993)
S. Sudarshan, Divesh Srivastava, Raghu Ramakrishnan, Catriel Beeri
We present a very general technique for defining semantics for programs that use aggregation. We use the technique to extend the well-founded semantics and the valid semantics, both of which were...
Subsumption and Indexing in Constraint Query Languages with Linear Arithmetic Constraints (1993)
Bottom-up evaluation of a program-query pair in a constraint query language (CQL) starts with the facts in the database and repeatedly applies the rules of the program, in iterations, to compute new...
Explaining Program Execution in Deductive Systems (1993)
Tarun Arora, Raghu Ramakrishnan, William G. Roth, Praveen Seshadri, Divesh Srivastava
. Programs in deductive database and programming systems have a natural meaning that is based upon their mathematical reading as logical rules. High-level `explanations' of a program...
Explaining Program Execution in Deductive Systems (1993)
Tarun Arora, Raghu Ramakrishnan, William G. Roth, Praveen Seshadri, Divesh Srivastava
this paper, we describe Explain, a menu-driven graphical tool for visualizing fact derivations in a logic programming/deductive database language. It is designed to operate in conjunction with the...
Implementation of the CORAL Deductive Database System (1993)
Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan, Praveen Seshadri
CORAL is a deductive database system that supports a rich declarative language, provides a wide range of evaluation methods, and allows a combination of declarative and imperative programming. The...
Coral++: Adding Object-Orientation to a Logic Database Language (1993)
Divesh Srivastava, Raghu Ramakrishnan, Praveen Seshadri, S. Sudarshan
Coral++ is a database programming language that integrates Coral [23] with the C++ type system. The data model allows arbitrary C++ objects in database facts, and the declarative query language...
Adding object-orientation to a logic database language (1993)
Divesh Srivastava, Praveen Seshadri, Raghu Ramakrishnan, S. Sudarshant
Coral++ is a database programming language that integrates Coral [23] with the C++ type system. The data model allows arbitrary C++ objects in database facts, and the declarative query language...
Efficient Bottom-up Evaluation of Logic Programs (1992)
Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan
Abstract. In recent years, much work has been directed towards evaluating logic programs and queries on deductive databases by using an iterative bottom-up fixpoint computation. The resulting...
CORAL---Control, Relations and Logic (1992)
Raghu Ramakrishnan Divesh, Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan
CORAL is a modular declarative query language/programming language that supports general Horn clauses with complex terms, set-grouping, aggregation, negation, and relations with tuples that contain...
Query Restricted Bottom-up Evaluation of Normal Logic Programs (1992)
David Kemp, Peter J. Stuckey, Divesh Srivastava
Several program transformations---magic sets, envelopes, NRSU transformations and context transformations, among others---have been proposed for efficiently computing the answers to a query while...
Pushing Constraint Selections (1992)
Divesh Srivastava, Raghu Ramakrishnan
this paper, we present a procedure that generates and propagates minimum QRP-constraints (if it terminates), based on the definition and uses of program predicates (Section 4). By propagating minimum...
CORAL-Control, Relations and Logic (1992)
Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan
CORAL is a modular declarative query language/programming language that supports general Horn clauses with complex terms, set-grouping, aggregation, negation, and relations with tuples that contain...
Controlling the Search in Bottom-Up Evaluation (1992)
Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan
Bottom-up evaluation of queries on deductive databases has many advantages over an evaluation scheme such as Prolog. It is sound and complete with respect to the declarative semantics of least...
Efficient Bottom-Up Evaluation Of Logic Programs (1992)
Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan
. In recent years, much work has been directed towards evaluating logic programs and queries on deductive databases by using an iterative bottom-up fixpoint computation. The resulting techniques...
CORAL{control, relations and logic (1992)
Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan
CORAL is a modular declarative query language/prog-ramming language that supports general Horn clauses with complex terms, set-grouping, aggregation, negation, and relations with tuples that contain...
Data Model and Query Evaluation in Global Information Systems (1991)
Alon Y. Levy, Divesh Srivastava, Thomas Kirk
. Global information systems involve a large number of information sources distributed over computer networks. The variety of information sources and disparity of interfaces makes the task of easily...
Magic Sets and Bottom-up Evaluation of Well-Founded Models (1991)
David B. Kemp, Peter J. Stuckey, Divesh Srivastava
We present a bottom-up operational procedure for computing well-founded models of allowed DATALOG programs with negation. This procedure provides a practical method of handling programs that involve...
Rule ordering in bottom-up fixpoint evaluation of logic programs (1990)
Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan
Abstract Logic programs can be evaluated bottom-up by repeatedly applying all rules, in "iterations", until the fixpoint is reached. However, it is often desirable--and in some...
Rule ordering in bottom-up fixpoint evaluation of logic programs (1990)
Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan
Logic programs can be evaluated bottom-up by repeatedly applying all rules, in "iterations", until the fixpoint is reached. However, it is often desirable--- and in some cases, e.g....
Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs (1990)
Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan
Logic programs can be evaluated bottom-up by repeatedly applying all rules, in "iterations", until the fixpoint is reached. However, it is often desirable --- and in some cases, e.g....
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...
Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs (1990)
Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan
Logic programs can be evaluated bottom-up by repeatedly applying all rules, in "iterations ", until the fixpoint is reached. However, it is often desirable---and in some cases, e.g....
Thomas Kirk, Alon Y. Levy, Yehoshua Sagiv, Divesh Srivastava
We describe the Information Manifold (IM), a system for browsing and querying of multiple networked information sources. As a first contribution, the system demonstrates the viability of knowledge...
Thomas Kirk, Alon Y. Levy, Yehoshua Sagiv, Divesh Srivastava
We describe the Information Manifold (IM), a system for browsing and querying of multiple networked information sources. As a first contribution, the system demonstrates the viability of knowledge...
Thomas Kirk, Alon Y. Levy, Yehoshua Sagiv, Divesh Srivastava
We describe the Information Manifold (IM), a system for browsing and querying of multiple networked information sources. As a first contribution, the system demonstrates the viability of knowledge...