8383873
Fast Computation of Sparse Datacubes
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, and hence efficiently computing datacubes over large sparse relations is important. We show that current techniques for computing datacubes over sparse relations do not scale well with the number of CUBE BY attributes, especially when the relation is much larger than main memory. We propose a novel algorithm for the fast computation of datacubes over sparse relations, and demonstrate the efficiency of our algorithm using synthetic, benchmark and real-world data sets. When the relation fits in memory, our technique performs multiple in-memory sorts, and does not incur any I/O beyond the input of the relation and the output of the datacube itself. When the relation does not fit in memory, a divideand-conquer strategy divides the problem of computing the datacube into several simpler computations of sub-datacubes. Often, all but one of the sub-datacubes can be computed in memory and our in-memory solution applies. In that case, the total I/O overhead is linear in the number of CUBE BY attributes. We demonstrate with an implementation that the CPU cost of our algorithm is dominated by the I/O cost for sparse relations. ‘The research of Kenneth A.
16656102
Groupwise Processing of Relational Queries
In this paper, we define and examine a particular class of queries called group queries. Group queries are natural queries in many decisionsupport applications. The main characteristic of a group query is that it can be executed in a groupby-group fashion. In other words, the underlying relation(s) can be partitioned (based on some set of attributes) into disjoint groups, and each group can be processed separately. We give a syntactic criterion to identify these queries and prove its sufficiency. We also prove the strong result that every group query has an equivalent formulation that satisfies our syntactic criterion. We describe a general evaluation technique for group queries, and demonstrate how an optimizer can determine this plan. We then consider more complex queries whose components are group queries with potentially different partitioning attributes. We give two methods to identify group query components within such a query. We also give some performance results for group queries expressed in standard SQL, comparing a commercial database system with our optimized plan on top of the same commercial system. These results indicate that there are significant potential performance improvements.
31185043
Inferring negative information from disjunctive databases
We propose criteria that any rule for inferring negative information from disjunctive databases should satisfy, and examine existing rules from this viewpoint. We then present a new inference rule, the ‘disjunctive database rule’ (DDR), and compare it to the existing rules with respect to the criteria. In particular, the DDR is equivalent to the CWA for definite databases, it infers no more negative information than the GCWA, and it interprets disjunction inclusively rather than exclusively. We generalize the DDR to a class of layered databases, describe an implementation of the DDR, ‘negation as positive failure’, and study its soundness and completeness properties.
7567374
Foundations of Aggregation Constraints
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 study the fundamental problem of checking if a conjunction of aggregation constraints is solvable, and present undecidability results for many different classes of aggregation constraints. We describe a complete and minimal axiomatization of the class of aggregation constraints over finite multisets of reals, which permits a natural reduction from the class of aggregation constraints to the class of mixed integer/real, non-linear arithmetic constraints. We then present a polynomial-time algorithm that directly checks for solvability of a useful class of aggregation constraints, where the reduction-based approach does not lead to efficient checks for solvability.
9401708
Complex Aggregation at Multiple Granularities
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 aggregates at multiple granularities. We call such queries multi-feature cubes. An example is Broken down by all combinations of month and customer, find the fraction of the total sales in 1996 of a particular item due to suppliers supplying within 10% of the minimum price (within the group), showing all subtotals across each dimension. We classify multi-feature cubes based on the extent to which fine granularity results can be used to compute coarse granularity results; this classification includes distributive, algebraic and holistic multi-feature cubes. We provide syntactic sufficient conditions to determine when a multi-feature cube is either distributive or algebraic. This distinction is important because, as we show, existing datacube evaluation algorithms can be used to compute multi-feature cubes that are distributive or algebraic, without any increase in I/O complexity. We evaluate the CPU performance of computing multi-feature cubes using the datacube evaluation algorithm of Ross and Srivastava. Using a variety of synthetic, benchmark and real-world data sets, we demonstrate that the CPU cost of evaluating distributive multi-feature cubes is comparable to that of evaluating simple datacubes. We also show that a variety of holistic multi-feature cubes can be evaluated with a manageable overhead compared to the distributive case.
38852147
On Negation in HiLog
Abstract The logic HiLog of Chen, Kifer, and Warren has a second order syntax, while its semantics is first order. HiLog programs with negative literals in the body are considered. A stable-model semantics and a well-founded semantics for this class of program are defined, and it is shown that these semantics generalize the stable-model semantics and the well-founded semantics, respectively, for range-restricted normal programs. A second order property called preservation under extensions is proposed and investigated. Preservation under extensions ensures that the semantics of a program is not changed when rules having no symbols in common with the program are appended to the program. It is shown that for normal programs, domain independence and preservation under extensions are equivalent, while for HiLog programs, preservation under extensions is strictly stronger. Range restrictedness is generalized to HiLog programs in two ways, and it is shown that range restricted HiLog programs are preserved under extensions with respect to the well-founded semantics. Conditions under which the well-founded semantics is two-valued are investigated, and the class of modularly stratified programs is generalized to HiLog. An extension of magic-set techniques to modularly stratified HiLog programs is described.
1908016
Optimal peer selection for P2P downloading and streaming
In a P2P system, a client peer may select one or more server peers to download a specific file. In a P2P resource economy, the server peers charge the client for the downloading. A server peer's price would naturally depend on the specific object being downloaded, the duration of the download, and the rate at which the download is to occur. The optimal peer selection problem is to select, from the set of peers that have the desired object, the subset of peers and download rates that minimizes cost. In this paper we examine a number of natural peer selection problems for both P2P downloading and P2P streaming. For downloading, we obtain the optimal solution for minimizing the download delay subject to a budget constraint, as well as the corresponding Nash equilibrium. For the streaming problem, we obtain a solution that minimizes cost subject to continuous playback while allowing for one or more server peers to fail during the streaming process. The methodologies developed in this paper are applicable to a variety of P2P resource economy problems.
403771
Packet multiplexers with adversarial regulated traffic
We consider a finite-buffer packet multiplexer to which traffic arrives from several independent sources. The traffic from each of the sources is regulated, i.e. the amount of traffic that can enter the multiplexer is constrained by known regulator constraints. The regulator constraints depend on the source and are more general than those resulting from cascaded leaky buckets. We assume that the traffic is adversarial to the extent permitted by the regulators. For lossless multiplexing, we show that if the original multiplexer is lossless it is possible to allocate bandwidth and buffer to the sources so that the resulting segregated systems are lossless. For lossy multiplexing, we use our results for lossless multiplexing to estimate the loss probability of the multiplexer. Our estimate involves transforming the original system into two independent resource systems, and using adversarial sources for the two independent resources to obtain a bound on the loss probability of the transformed system. We show that the adversarial sources are not extremal on-off sources, even when the regulator consists of a peak rate controller in series with a leaky bucket. We explicitly characterize the form of the adversarial source for the transformed problem. We also provide numerical results for the case of the simple regulator.
10455339
Pollution in P2P file sharing systems
One way to combat P2P file sharing of copyrighted content is to deposit into the file sharing systems large volumes of polluted files. Without taking sides in the file sharing debate, in this paper we undertake a measurement study of the nature and magnitude of pollution in the FastTrack P2P network, currently the most popular P2P file sharing system. We develop a crawling platform which crawls the majority of the FastTrack Network's 20,000+ supernodes in less than 60 minutes. From the raw data gathered by the crawler for popular audio content, we obtain statistics on the number of unique versions and copies available in a 24-hour period. We develop an automated procedure to detect whether a given version is polluted or not, and we show that the probabilities of false positives and negatives of the detection procedure are very small. We use the data from the crawler and our pollution detection algorithm to determine the fraction of versions and fraction of copies that are polluted for several recent and old songs. We observe that pollution is pervasive for recent popular songs. We also identify and describe a number of anti-pollution mechanisms.
8733679
Stochastic Fluid Theory for P2P Streaming Systems
We develop a simple stochastic fluid model that seeks to expose the fundamental characteristics and limitations of P2P streaming systems. This model accounts for many of the essential features of a P2P streaming system, including the peers' realtime demand for content, peer churn (peers joining and leaving), peers with heterogeneous upload capacity, limited infrastructure capacity, and peer buffering and playback delay. The model is tractable, providing closed-form expressions which can be used to shed insight on the fundamental behavior of P2P streaming systems. The model shows that performance is largely determined by a critical value. When the system is of moderate-to-large size, if a certain ratio of traffic loads exceeds the critical value, the system performs well; otherwise, the system performs poorly. Furthermore, large systems have better performance than small systems since they are more resilient to bandwidth fluctuations caused by peer churn. Finally, buffering can dramatically improve performance in the critical region, for both small and large systems. In particular, buffering can bring more improvement than can additional infrastructure bandwidth.
32291503
On Nonblocking Multirate Interconnection Networks
In a recent paper, Melen and Turner [SIAM J. Comput., 18 (1989), pp. 301–313] determined sufficient conditions for multirate interconnection networks to be strictly nonblocking and rearrangeable. They considered the continuous bandwidth case, which permits the bandwidth of a connection to take an arbitrary value in a given closed interval. In this paper, simple necessary and sufficient conditions for multirate interconnection networks to be strictly nonblocking for both discrete and continuous bandwidth cases are determined. New results for rearrangeable multirate networks with discrete bandwidth requirements are also given.