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.
2792911
The New Jersey Data Reduction Report
An arrangement is shown for controlling transmission of blocks of information to and from a plurality of major components of a digital computer system interconnected by common buses. The disclosed arrangement operates so that any component of the system may normally seize, on a nonpriority basis, one of the buses at the beginning of any time slot defined by two successive clock pulses generated by a single source and applied to all components simultaneously; however, if a special instruction is encountered during execution of a program, any component may retain a bus for more than one time slot. The disclosed arrangement also permits error checking of transmitted information from a given major component without interfering with transmission from any other major component and automatically causes retransmission of any block of information found to be improperly transmitted originally. Still further, the disclosed arrangement permits buses to be dedicated during execution of a program or, if desired, any complete major component to be replaced without affecting any other major component.
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.
16955834
Querying Multiple Features of Groups in Relational Databases
Some aggregate and grouping queries are conceptually simple, but difficult to express in SQL. This difficulty causes both conceptual and implementation problems for the SQLbased database system. Complicated queries and views are hard to understand and maintain. Further, the code produced is sometimes unnecessarily inefficient, as we demonstrate experimentally using a commercial database system. In this paper, we examine a class of queries involving (potentially repeated) selection, grouping and aggregation over the same groups, and propose an extension of SQL syntax that allows the succinct representation of these queries. We propose a new relational algebra operation that represents several levels of aggregation over the same groups in an operand relation. We demonstrate that the extended relational operator can be evaluated using efficient algorithms. We describe a translation from the extended SQL language into our algebraic language. We have implemented a preprocessor that evaluates our extended language on top of a commercial l This research was supported by a grant from the AT&T Foundation, by a David and Lucile Packard Foundation Fellowship in Science and Engineering, by a Sloan Foundation Fellowship, by NSF grants IRI-9209029, CDA-90-24735, and by an NSF Young Investigator award. Permission to copy without fee all or part of this material is gmnted provided that the wpier are not made or distributed for direct commercial advantage, the VLDB wpyrinht notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment. Proceedings of the 22nd VLDB Conference Mumbai(Bombay), India, 1996 database system. We demonstrate that on a variety of examples, our implementation improves performance over standard SQL representations of the same examples by orders of magnitude.
27538683
Academic dishonesty and the Internet
The Internet provides new opportunities for cheating on computer science class projects.
36647845
An Architecture for Declarative Object-Oriented Databases
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.
22940589
Asynchronous voice: a personal account
Asynchronous voice is the interactive communication process of people leaving voice messages for other people and the other people responding with their voice messages. A primitive form of asynchronous voice is a kind of telephone tag in which people use voice mail to have an interactive conversation. The author gives a personal account of his work with asynchronous voice and asynchronous learning.
31310473
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 probabilities for 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.
15587034
Packet Scheduling Across Networks of Switches
Recent developments in computer and communication networks require scheduling decisions to be made under increasingly complex system dynamics. We model and analyze the problem of packet transmissions through an arbitrary network of buffered queues, and provide a framework for describing routing and migration. This paper introduces an intuitive geometric description of stability for these networks and describes some simple algorithms which lead to maximal throughput. We show how coordination over sequential timeslots by algorithms such as those based on a round robin can provide considerable advantages over a randomized scheme.