NDLI: Query evaluation using overlapping views: completeness and efficiency

Please wait, while we are loading the content...

Speeding up search in peer-to-peer networks with a multi-way tree structure

Query evaluation using overlapping views: completeness and efficiency

MauveDB: supporting model-based user views in database systems

Forensic analysis of database tampering

Contour map matching for event detection in sensor networks

Modeling skew in data streams

Injecting utility into anonymized datasets

Interactive query formulation over web service-accessed sources

Communication-efficient distributed monitoring of thresholded counts

GPUTeraSort: high performance graphics co-processor sorting for large database management

Boolean + ranking: querying a database by k-constrained optimization

High-performance complex event processing over streams

Rewriting nested XML queries using nested views

Refreshing the sky: the compressed skycube with efficient support for frequent updates

Provenance management in curated databases

On the database/network interface in large-scale publish/subscribe systems

On-the-fly sharing for streamed aggregation

DADA: a data cube for dominant relationship analysis

Data delivery in a service-oriented world: the BEA aquaLogic data services platform

Documentum ECI self-repairing wrappers: performance analysis

Trends in high performance analytics

Using the oracle database as a declarative RSS hub

Data management projects at Google

PADS: an end-to-end system for processing ad hoc data

Generic similarity detection in ontologies with the SOQA-SimPack toolkit

MAXENT: consistent cardinality estimation in action

Managing information extraction: state of the art and research directions

Programming for XML

Record linkage: similarity measures and algorithms

Accessing the web: from search to integration

Adaptive query processing: why, how, when, what next

Reconciling while tolerating disagreement in collaborative data sharing

User-defined aggregate functions: bridging theory and practice

Database support for matching: limitations and opportunities

Dynamic authenticated index structures for outsourced databases

Constraint chaining: on energy-efficient continuous monitoring in sensor networks

Fast range-summable random variables for efficient aggregate estimation

Personalized privacy preservation

To search or to crawl?: towards a query optimizer for text-centric tasks

A geometric approach to monitoring threshold functions over distributed data streams

Recovery from "bad" user transactions

Ranking objects based on relationships

Quality-aware dstributed data delivery for continuous query services

Meta-data indexing for XPath location steps

Finding k-dominant skylines in high dimensional space

Efficient query processing on unstructured tetrahedral meshes

Relaxed-currency serializability for middle-tier caching and replication

Continuous monitoring of top-k queries over sliding windows

Integrating compression and execution in column-oriented database systems

LINQ: reconciling object, relations and XML in the .NET framework

Identity resolution: 23 years of practical experience and observations at scale

VizQL: a language for query, analysis and visualization

Windows and RSS: beyond blogging

Data management in the CarTel mobile sensor computing system

Searching in time

InMAF: indexing music databases via multiple acoustic features

Approximately detecting duplicates for streaming data using stable bloom filters

Supporting ad-hoc ranking aggregates

Declarative networking: language, execution and optimization

Redundancy and information leakage in fine-grained access control

Energy-efficient monitoring of extreme values in sensor networks

Graph-based synopses for relational selectivity estimation

Simultaneous scalability and security for data-intensive web applications

Efficient query processing in geographic web search engines

Continuous query processing in data streams using duality of data and queries

Run-time operator state spilling for memory intensive long-running queries

Context-sensitive ranking

Design, implementation, and evaluation of the linear road bnchmark on the stream processing core

Locking-aware structural join operators for XML query processing

Efficient reverse k-nearest neighbor search in arbitrary metric spaces

Effective keyword search in relational databases

Extensible optimization in overlay dissemination trees

Optimal multi-scale patterns in time series streams

Automatic physical design tuning: workload as a sequence

PHP: supporting the new paradigm of situational and composite web applications

Using SPIDER: an experience report

Fast approximate computation of statistics on views

VGM: visual graph mining

Derby/S: a DBMS for sample-based query answering

Quark: an efficient XQuery full-text implementation

Ordering the attributes of query results

MonetDB/XQuery: a fast XQuery processor powered by a relational engine

A non-linear dimensionality-reduction technique for fast similarity search in large databases

Flexible and efficient XML search with complex full-text predicates

Data integration through transform reuse in the Morpheus project

Automatic client-server partitioning of data-driven web applications

aAqua: a database-backended multilingual, multimedia community forum

Testing database applications

Paper-based mobile access to databases

CS cache engine: data access accelerator for location-based service in mobile environments

The BEA AquaLogic data services platform (Demo)

Proactive identification of performance problems

Avatar semantic search: a database approach to information retrieval

VisTrails: visualization meets data management

XPORT: extensible profile-driven overlay routing trees

COLT: continuous on-line tuning

OMCAT: optimal maintenance of continuous queries' answers for trajectories

A system for specification and verification of interactive, data-driven web applications

ObjectRank: a system for authority-based search on databases

Query evaluation using overlapping views: completeness and efficiency

Content Provider	ACM Digital Library
Author	Kormilitsin, Maxim Gou, Gang Chirkova, Rada
Abstract	We study the problem of finding efficient equivalent view-based rewritings of relational queries, focusing on query optimization using materialized views under the assumption that base relations cannot contain duplicate tuples. A lot of work in the literature addresses the problems of answering queries using views and query optimization. However, most of it proposes solutions for special cases, such as for conjunctive queries (CQs) or for aggregate queries only. In addition, most of it addresses the problems separately under set or bag-set semantics for query evaluation, and some of it proposes heuristics without formal proofs for completeness or soundness. In this paper we look at the two problems by considering CQ/A queries - that is, both pure conjunctive and aggregate queries, with aggregation functions SUM, COUNT, MIN, and MAX; the DISTINCT keyword in (SQL versions of) our queries is also allowed. We build on past work to provide algorithms that handle this general setting. This is possible because recent results on rewritings of CQ/A queries [1, 8] show that there are sound and complete algorithms based on containment tests of CQs.Our focus is that our algorithms are efficient as well as sound and complete. Besides the contribution we make in putting and addressing the problems in this general setting, we make two additional contributions for bag-set and set semantics. First, we propose efficient sound and complete tests for equivalence of CQ/A queries to rewritings that use overlapping views (the algorithms are complete with respect to the language of rewritings). These results apply not only to query optimization, but to all areas where the goal is to obtain efficient equivalent view-based query rewritings. Second, based on these results we propose two sound algorithms, BDPV and CDPV, that find efficient execution plans for CQ/A queries in terms of materialized views. Both algorithms extend the cost-based query-optimization approach of System R [19]. The efficient sound algorithm BDPV is also complete in some cases, whereas CDPV is sound and complete for all CQ/A queries we consider. We present a study of the completeness-efficiency tradeoff in the algorithms, and provide experimental results that show the viability of our approach and test the limits of query optimization using overlapping views.
Starting Page	37
Ending Page	48
Page Count	12
File Format	PDF
ISBN	1595934340
DOI	10.1145/1142473.1142479
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2006-06-27
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Materialized views Rewriting queries using views Query optimization
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in