Complex join queries are expensive to process on big data. Providing fast and accurate approximations to join queries with common aggregate functions can bring tremendous benefits in many fields such as data management, data mining, and machine learning. The state-of-the-art methods mainly focus on generating non-reusable samples during query time which can be costly for big data applications. In this research, we develop a scalable sample-based synopsis, called Scalable Join Correlated Sample Synopsis (or CS*), which can be pre-computed and doesn’t rely on any index structure. CS* only needs to be generated once and can be used to answer all future queries on the same database. It efficiently maintains join relationships between sampled tuples thanks to the introduced scheme of scalable join correlated sampling and a unique numerical value called join ratio (or JR). We further introduce two novel data structures, namely count trace and join correlated histogram, to optimize the calculation of JR values in map-reduce. For query estimations, multiple unbiased estimators are developed on CS* to provide fast and accurate approximations for join queries with common aggregate functions, acyclic or cyclic join graphs, and dangling tuples. The experimental study on large datasets demonstrates that CS* can be efficiently generated and provides accurate join query estimations with small sampling fractions.

Fast and accurate estimations for complex queries are profoundly beneficial for large databases with heavy workloads. In this research, we propose a statistical summary for a database, called CS2 (Correlated Sample Synopsis), to provide rapid and accurate result size estimations for all queries with joins and arbitrary selections. Unlike the state-of-the-art techniques, CS2 does not completely rely on simple random samples, but mainly consists of correlated sample tuples that retain join relationships with less storage. We introduce a statistical technique, called reverse sample, and design a powerful estimator, called reverse estimator, to fully utilize correlated sample tuples for query estimation. We prove both theoretically and empirically that the reverse estimator is unbiased and accurate using CS2. Extensive experiments on multiple datasets show that CS2 is fast to construct and derives more accurate estimations than existing methods with the same space budget.

Twig pattern matching is a critical operation for XML query processing, and the holistic computing approach has shown superior performance over other methods. Since Bruno et al. introduced the first holistic twig join algorithm, TwigStack, numerous so-called holistic twig join algorithms have been proposed. Yet practical XML queries often require support for more general twig patterns, such as the ones that allow arbitrary occurrences of an arbitrary number of logical connectives (AND, OR, and NOT); such types of twigs are referred to as B-twigs (i.e., Boolean-Twigs) or AND/OR/NOT-twigs. We have seen interesting work on generalizing the holistic twig join approach to AND/OR-twigs and AND/NOT-twigs, but have not seen any further effort addressing the problem of AND/OR/NOT-Twigs at the full scale, which therefore forms the main theme of this paper. In this paper, we investigate novel mechanisms for efficient B-twig pattern matching. In particular, we introduce “B-twig normalization” as an important first-step in our approach toward eventually conquering the complexity of B-twigs, and then present BTwigMerge-the first holistic twig join algorithm designed for B-twigs. Both analytical and experimental results show that BTwigMerge is optimal for B-twig patterns with AD (Ancestor-Descendant) edges and/or PC (Parent-Child) edges.

Although the notion of time-constrained query was first introduced two decades ago to address the problem of long running SQL queries, none of the commercial database systems support such a feature. This is rather surprising given the fact that database systems are beginning to accommodate large datasets in the order of terabytes to petabytes. Thus, the long running SQL query problem needs to be addressed. Recently, at Oracle we investigated and proposed a mechanism of supporting time-constrained quenes to provide quick approximate answers by use of sampling for such long running SQL quenes. This we followed up by coming up with error estimates as a measure of goodness for the approximation. To further validate our time-constrained query work, in this paper we present an experimental study conducted on our time-constrained query prototype built on the Oracle Database. It is our hope that this work will revive interest in time-constrained queries.

As the Extensible Markup Language (XML) rapidly establishes itself as the de facto standard for presenting, storing, and exchanging data on the Internet, large volume of XML data and their supporting facilities start to surface. A fast and accurate selectivity estimation mechanism is of practical importance because selectivity estimation plays a fundamental role in XML query optimization. Recently proposed techniques are all based on some forms of structure synopses that could be time-consuming to build and not effective for summarizing complex structure relationships. In this research, we propose an innovative sampling method that can capture the tree structures and intricate relationships among nodes in a simple and effective way. The derived sample tree is stored as a synopsis for selectivity estimation. Extensive experimental results show that, in comparison with the state-of-the-art structure synopses, specifically the TreeSketch and Xseed synopses, our sample tree synopsis applies to a broader range of query types, requires several orders of magnitude less construction time, and generates estimates with considerably better precision for complex datasets.

In this article; the authors propose to use the grid file to store multi-dimensional data cubes and answer angesum queries. The grid file is enhanced with a dynamic splitting mechanism to accommodate insertions of data. It overcomes the drawback of the traditional grid file in storing uneven data while enjoying its advantages of simplicity and efficiency. The space requirement grows linearly with the dimension of the data cube; compared with the exponential growth of conventional methods that store pre-computed aggregate values for range-sum queries. The update cost is O (1); much faster than the pre-computed data cube approaches; which generally have exponential update cost. The grid file structure can also respond to range queries quickly. They compare it with an approach that uses the R*-tree structure to store the data cube. The experimental results show that the proposed method performs favorably in file size; update speed; construction time; and query response time for both evenly and unevenly distributed data.

In view of the inefficiency of the traditional two-phase Twig-Stack algorithm, we propose a single-phase holistic twig pattern matching method based on the TwigStack algorithm by applying a novel stack structure.

Load shedding techniques generate approximate sliding window join results when memory constraints prevent exact computation. The previously proposed random load shedding method drops input tuples without consideration for the number of outputs created, while the recently proposed semantic load shedding technique aims to produce the largest possible result set. We consider a new model in which data stream tuples contain numerical importance values relevant to the query source and seek to maximize the importance of the approximate join result. We show that both random load shedding and semantic load shedding are sub-optimal in this situation, while the techniques presented in this paper satisfy the objective function by considering both tuple importance and join attribute distributions. We extend the existing offline semantic approximation technique to make it compatible with our objective function and show that it is less space and time efficient than our new optimal offline algorithm for small and large join memory allotments. We also introduce four efficient online algorithms, which are quite promising in maximizing the importance of the approximate join result without foreknowledge of input streams.

XML structural joins, which evaluate the containment (ancestor-descendant) relationships between XML elements, are important operations of XML query processing. Estimating structural join size accurately and quickly is thus crucial to the success of XML query plan selection and the query optimization. XML structural joins are essentially complex unequal joins, which render well-known estimation techniques, such as cosine transform, wavelet transform, and sketch, not directly applicable. In this paper, we propose a relation model to capture the structural information of XML data such that the original complex unequal joins are converted to equal joins and those well-known estimation techniques become directly applicable to structural join size estimation. Theoretical analyses and extensive experiments have been performed on these estimation methods. It is shown that the cosine transform requires the least memory and yields the best estimates.

This paper provides a general overview of two innovative applications of Cosine series in XML joins and data stream joins.

Caching can reduce expensive data transfers and improve the performance of mobile computing. In order to reuse caches after short disconnections, invalidation reports are broadcast to clients to identify outdated items. Detailed reports may not be desirable because they can consume too much bandwidth. On the other hand, false invalidations may set in if the accurate timing of updates is not provided. In this research, we aim to reduce the false invalidation rates of cached items. Based on our analysis, false invalidation rates are closely related to clients' reconnection patterns (i.e., the distribution of the time spans between disconnections and reconnections). We show that in theory for any given reconnection pattern, a report with a minimal false invalidation rate can be derived. For practical uses, we propose to capture the reconnection pattern by sampling and develop a method to compose a near-optimal invalidation report. This method is simple and fast. Experimental results have confirmed that our method is indeed more effective in reducing the false invalidation rate than others.

Selectivity estimation is an integral part of query optimization. In this paper, we propose a novel approach to approximate data density functions of relations and use them to estimate selectivities. A data density function here is approximated by a partial sum of an orthogonal series. Such approximate density functions can be derived easily, stored efficiently, and maintained dynamically. Experimental results show that our approach yields comparable or better estimation accuracy than the Wavelet and DCT methods, especially in the high dimensional spaces.

Mobile computing is characterized by frequent disconnection, limited communication capability, narrow bandwidth, etc. Caching can play a vital role in mobile computing by reducing the amount of data transferred. In order to reuse caches after short disconnections, invalidation reports are broadcasted to clients to help update/invalidate their caches. Detailed reports may not be desirable because they can be very long and consume large bandwidth. On the other hand, false invalidations may set in if detailed timing information of updates is not provided in the report. In this research, we aim to reduce the false invalidation rates of the reports. It is found that false invalidation rates are closely related to clients' reconnection patterns (i.e., the distribution of the time spans between disconnections and reconnections). By using Newton's method, we show how a report with a minimal false invalidation rate can be constructed for any given disconnection pattern.

Presents a framework for statistical data mining using summary tables. A set of operators is proposed for common data mining tasks, such as summarization, association, classification and clustering, as well as for basic statistical analysis, such as hypothesis testing, estimation and regression, which can help explore knowledge. The operators enable users to explore a variety of knowledge effectively and yet require users to have little statistical knowledge. Summary tables, which store basic information about groups of tuples of the underlying relations, are constructed to speed up the data mining process. The summary tables are incrementally updatable and are able to support a variety of data mining and statistical analysis tasks. The operators, together with the uses of the summary tables, can make interactive data mining flexible, effective, and perhaps instantaneous.

Discusses the modeling and extraction of statistical relationships among attributes. Different methods are used for the extraction of different types of relationships. A complete methodology for extraction is developed by integrating widely-accepted statistical methods. Statistical relationships manifest the embedded relationships in data, and thus lend themselves naturally to estimating unknown attribute values and detecting unlikely values. We carefully examine these applications and evaluate the usefulness of statistical relationships in these applications using a real-life database.

In this paper, we introduce a new type of integrity constraint, which we call a statistical constraint, and discuss its applicability to enhancing database correctness. Statistical constraints manifest embedded relationships among current attribute values in the database and are characterized by their probabilistic nature. They can be used to detect potential errors not easily detected by the conventional constraints. Methods for extracting statistical constraints from a relation and enforcement of such constraints are described. Preliminary performance evaluation of enforcing statistical constraints on a real life database is also presented.

CASE-DB is a real-time, single-user, relational prototype DBMS that permits the specification of strict time constraints for relational algebra queries. Given a time constrained nonaggregate relational algebra query and a "fragment chain" for each relation involved in the query, CASE-DB initially obtains a response to a modified version of the query and then uses an "iterative query evaluation" technique to successively improve and evaluate the modified version of the query, CASE-DB controls the risk of overspending the time quota at each step using a "risk control technique".

Article Statistical inference of unknown attribute values in databases Share on Authors: Wen-Chi Hou Department of Computer Science, Southern Illinois University at Carbondale, IL Department of Computer Science, Southern Illinois University at Carbondale, ILView Profile , Zhongyang Zhang Department of Computer Science, Southern Illinois University, at Carbondale, IL Department of Computer Science, Southern Illinois University, at Carbondale, ILView Profile , Nong Zhou Department of Computer Science, New Mexico Tech, Socorro, NM Department of Computer Science, New Mexico Tech, Socorro, NMView Profile Authors Info & Claims CIKM '93: Proceedings of the second international conference on Information and knowledge managementDecember 1993 Pages 21–30https://doi.org/10.1145/170088.170097Online:01 December 1993Publication History 5citation302DownloadsMetricsTotal Citations5Total Downloads302Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In this paper, we present an algorithm to strictly control the time to process an estimator for an aggregate relational query. The algorithm implemented in a prototype database management system, called CASE-DB, iteratively samples from input relations, and evaluates the associated estimator until the time quota expires. In order to estimate the time cost of a query, CASE-DB uses adaptive time cost formulas. The formulas are adaptive in that the parameters of the formulas can be adjusted at runtime to better fit the characteristics of a query. To control the use of time quota, CASE-DB adopts the one-at-a-time-interval time control strategy to make a tradeoff between the risks of overspending and the overhead, finally, experimental evaluation of the methodology is presented.

The problem of time-constrained query evaluation in a single-user database management system (DBMS) is considered. CASE-DB is a real-time, single user, relational prototype DBMS that uses the relational algebra as its query language. Given a nonaggregate query and a fragment chain for each input relation of the query. CASE-DB uses iterative query evaluation techniques to obtain a response first to a modified version of the query, and then to successively improved versions of the query. CASE-DB controls the risk of overspending the time quota at each step using a risk control technique. For periodically occurring queries, CASE-DB uses incremental query evaluation techniques that make sure that each operator in the query has at least one operand relation which contains the changes in the last period, and is expected to be very small compared to the actual database relation.>

article Free Access Share on Statistical estimators for aggregate relational algebra queries Authors: Wen-Chi Hou Case Western Reserve Univ., Cleveland, OH Case Western Reserve Univ., Cleveland, OHView Profile , Gultekin Ozsoyoglu Case Western Reserve Univ., Cleveland, OH Case Western Reserve Univ., Cleveland, OHView Profile Authors Info & Claims ACM Transactions on Database SystemsVolume 16Issue 4pp 600–654https://doi.org/10.1145/115302.115300Published:01 December 1991Publication History 44citation559DownloadsMetricsTotal Citations44Total Downloads559Last 12 Months24Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Present database systems process all the data related to a query before giving out responses. As a result, the size of the data to be processed becomes excessive for real-time/time-constrained environments. A new methodology is needed to cut down systematically the time to process the data involved in processing the query. To this end, we propose to use data samples and construct an approximate synthetic response to a given query.