Relational databases (RDBs) are widely used by corporations and governments to store multiple related tables. Their relational schemas pose unique challenges to synthetic data generation for privacy-preserving data sharing, e.g., for collaborative analytical and data mining tasks, as well as software testing at various scales. Relational schemas typically include a set of primary and foreign key constraints to specify the intra-and inter-table entity relations, which also imply crucial intra-and inter-table data correlations in the RDBs. Existing synthetic RDB generation approaches often focus on the relatively simple and basic parent-child relations, failing to address the ubiquitous real-world complexities in relational schemas in key constraints like composite keys, intra-table correlations like sequential correlation, and inter-table data correlations like indirectly connected tables. In this paper, we introduce incremental relational generator (IRG), a modular framework designed to handle these real-world challenges. In IRG, each table is generated by learning context from a depth-first traversal of relational connections to capture indirect inter-table relationships and constructs different parts of a table through several classical generative and predictive modules to preserve complex key constraints and data correlations. Compared to 3 prior art algorithms across 10 real-world RDB datasets, IRG successfully handles the relational schemas and captures critical data relationships for all datasets while prior works are incapable of. The generated synthetic data also demonstrates better fidelity and utility than prior works, implying its higher potential as a replacement for the basis of analytical tasks and data mining applications. Code is available at: https://github.com/li-jiayu-ljy/irg.

Stack distance characterizes temporal locality of workloads and plays a vital role in cache analysis since the 1970s. However, exact stack distance calculation is too costly, and impractical for online use. Hence, much work was done to optimize the exact computation, or approximate it through sampling or modeling.

Researchers and developers use benchmarks to compare their algorithms and products. A database benchmark must have a dataset. To be application-specific, this dataset should be empirical. However, the dataset may be too small, or too large, for the benchmarking experiments. The dataset must, therefore, be scaled to the desired size. To ensure the scaled dataset is similar to the original dataset, previous work typically specifies or extracts a fixed set of properties from the original dataset, then uses these properties to generate synthetic data for the scaled dataset. However, this approach becomes increasingly intractable as the property set gets larger, so a new solution is necessary. This paper proposes ASPECT, which adopts a different approach, for relational datasets. The user first selects a sizescaler to synthetically scale the empirical dataset to a desired size, then uses a tool to tweak the scaled dataset to enforce each target property. ASPECT provides the interface for these tools to collaborate in this tweaking process. Extensive experiments on real datasets show that ASPECT can efficiently and effectively enforce similarity in such a generated dataset.

In any caching system, the admission and eviction policies determine which contents are added and removed from a cache when a miss occurs. Usually, these policies are devised so as to mitigate staleness and increase the hit probability. Nonetheless, the utility of having a high hit probability can vary across contents. This occurs, for instance, when service level agreements must be met, or if certain contents are more difficult to obtain than others. In this paper, we propose utility-driven caching, where we associate with each content a utility, which is a function of the corresponding content hit probability. We formulate optimization problems where the objectives are to maximize the sum of utilities over all contents. These problems differ according to the stringency of the cache capacity constraint. Our framework enables us to reverse engineer classical replacement policies such as LRU and FIFO, by computing the utility functions that they maximize. We also develop online algorithms that can be used by service providers to implement various caching policies based on arbitrary utility functions.

Quality of control is a critical concern in Cyber-Physical Systems (CPS) which are comprised of multiple intercommunicating control applications. Due to complex timing behaviour of these systems, poor quality of control can lead to catastrophe. Recent studies showed that, conflict miss increment in the processor cache memory shared by concurrently running control applications can degrade control quality in CPS significantly. Increasing cache associativity can help to reduce conflict misses. However, the existing reconfigurable cache architectures that allow runtime modification of cache associativity are not capable to guaranty a newly chosen associativity's suitability for the forthcoming control quality requirement. Moreover, they have timing and energy related overheads. In this regard, this paper presents a novel, self-reconfiguring cache memory architecture "SeReMo". When conflict misses increase significantly, SeReMo reconfigures its associativity to better suit the current as well as future control quality demand. To trigger reconfiguration, a low overhead, non-strictly inclusive cache hierarchy-specific approach is used. Configurations with different associativity are generated using modules made of 4 cache lines and 7 special bits. Special replacement policy and indexing scheme are used to suit modular reconfiguration. SPEC CPU 2006 benchmark trace-driven simulation reveals that SeReMo reduces average number of conflict misses per line to 1/12951 of the state-of-the-art reconfigurable cache architecture at maximum (to 1/830 on average). As a result, execution time and energy consumption reduce by 48 hours at maximum (by 2/3 on average) and by 2907 Joules at maximum (86% on average) respectively.

Researchers and developers use benchmarks to compare their algorithms and products. For database systems, a benchmark must have a dataset D. To be application-specific, this dataset D should be empirical. However, a real D may be too small, or too large, for the benchmarking experiments. Therefore, D must first be scaled to the desired size. Previous related work typically extracts a set of properties Π = { π 1 , . . . , π n } from D, then use Π to generate the synthetic D~. Π may thus ensure D~ is similar to D. This approach of having some monolithic software enforce properties π 1 , . . . , π n becomes increasingly intractable as n increases. Our demonstration will present ASPECT, a framework that takes a different approach. With ASPECT, there is a tool So to first scale the dataset size. The resulting D~ can then be tweaked by tools T 1 , . . . , T n , where T k enforces π k in D~. At the demonstration, a visitor has a choice of (i) D , (ii) size scaler S 0 , (iii) the subset of properties to enforce, and (iv) the order of applying the tools for the chosen properties. The visitor can then see the enforcement error for each π k and the running time for each T k . A video of the demonstration is presented here: http://scaler.d2.comp.nus.edu.sg/

Enterprises and researchers often have datasets that can be represented as graphs (e.g. social networks). The owner of a large graph may want to scale it down to a similar but smaller version, e.g. for application development. On the other hand, the owner of a small graph may want to scale it up to a similar but larger version, e.g. to test system scalability. GSCALER is a recently developed tool for such scaling. This demonstration presents GSCALERCloud, a web-based service for access to GSCALER. A user can specify, via a browser, an example or empirical graph G, and a target size for the scaled version eG. The demonstration has two stages. In Stage I, the visitor can experiment with small graphs and check the similarity between input G and scaled eG. In Stage II, the visitor can test GSCALER with large graphs, and visually check for similarity using aggregate metrics and statistical distributions generated by GSCALERCloud's tools.

For many years now, enterprises and cloud providers have been using virtualization to run their workloads. Until recently, this means running an application in a virtual machine (hardware virtualization). However, virtual machines are increasingly replaced by containers (operating system virtualization), as evidenced by the rapid rise of Docker. A containerized software environment can generate a large amount of metadata. If properly managed, these metadata can greatly facilitate the management of containers themselves. This demonstration introduces ConHub, a PostgreSQL-based container metadata management system. Visitors will see that (1) ConHub has a language CQL that supports Docker commands; (2) it has a user-friendly interface for querying and visualizing container relationships; and (3) they can use CQL to formulate sophisticated queries to facilitate container management.

Enterprises and researchers often have datasets that can be represented as graphs (e.g. social networks). The owner of a large graph may want to scale it down to a smaller version, e.g. for application development. On the other hand, the owner of a small graph may want to scale it up to a larger version, e.g. to test system scalability. This paper investigates the Graph Scaling Problem (GSP): Given a directed graph G and positive integers n and m, generate a similar directed graph G with n nodes and m edges. This paper presents a graph scaling algorithm Gscaler for GSP. Analogous to DNA shotgun sequencing, Gscaler, decomposes G into small pieces, scales them, then uses the scaled pieces to construct G. This construction is based on the indegree/outdegree correlation of nodes and edges. Extensive tests with real graphs show that Gscaler is scalable and, for many graph properties, it generates a G that has greater similarity to G than other state-of-the-art solutions, like Stochastic Kronecker Graph and UpSizeR.

In any caching system, the admission and eviction policies determine which contents are added and removed from a cache when a miss occurs. Usually, these policies are devised so as to mitigate staleness and increase the hit probability. Nonetheless, the utility of having a high hit probability can vary across contents. This occurs, for instance, when service level agreements must be met, or if certain contents are more difficult to obtain than others. In this paper, we propose utility-driven caching, where we associate with each content a utility, which is a function of the corresponding content hit probability. We formulate optimization problems where the objectives are to maximize the sum of utilities over all contents. These problems differ according to the stringency of the cache capacity constraint. Our framework enables us to reverse engineer classical replacement policies such as LRU and FIFO, by computing the utility functions that they maximize. We also develop online algorithms that can be used by service providers to implement various caching policies based on arbitrary utility functions.

The Dataset Scaling Problem (DSP) defined in previous work states: Given an empirical set of relational tables D and a scale factor s, generate a database state D that is similar to D but s times its size . A DSP solution is useful for application development ( s < 1), scalability testing ( s > 1) and anonymization ( s = 1). Current solutions assume all table sizes scale by the same ratio s . However, a real database tends to have tables that grow at different rates. This paper therefore considers non-uniform scaling (nuDSP), a DSP generalization where, instead of a single scale factor s , tables can scale by different factors. D scaler is the first solution for nuDSP. It follows previous work in achieving similarity by reproducing correlation among the primary and foreign keys. However, it introduces the concept of a correlation database that captures fine-grained, per-tuple correlation. Experiments with well-known real and synthetic datasets D show that D scaler produces D with greater similarity to D than state-of-the-art techniques. Here, similarity is measured by number of tuples, frequency distribution of foreign key references, and multi-join aggregate queries.

The old virtualization idea and the new multicore technology now make it possible to consolidate multiple workloads on one physical host. This helps reduce the amount of idle resources. In particular, transcendent memory is a recent idea to gather idle memory into a pool that is shared by virtual machines (VMs). It can be viewed as a new level in the memory hierarchy, between main memory and disks. Cleancache is the part of transcendent memory that is used for caching the VMs' clean pages. This paper shows that a Cache Miss Equation can accurately capture observed cleancache behavior, despite its unusual design. The equation can be used to dynamically size and partition cleancache for the VMs. Experiments with a variety of workloads show that this equation-based allocation can help to drastically reduce disk reads and fairly allocate cleancache space.

With the extraordinary growth of cores and threads in today's multithreaded machines, analyzing and tuning the performance of such platforms becomes a challenging task. In this paper, we propose an intuitive and visualizable model for analyzing the performance of contemporary highly concurrent multithreaded machines. Based on flow balancing between service demand and service supply of the memory system, the model draws an intuitive figure to characterize machine state, identify bottlenecks and determine optimization directions. The tractability of the model is highlighted as it only requires two parameters from the workload. Our model achieves 90% and 83% prediction accuracy for computation throughput on Fermi and Kepler GPUs over the 16 applications from Rodinia benchmark.

Many proposals for information-centric networking (ICN) share the idea of in-network caching. This idea has four issues: (1) Memory capacity can be wasted through caching redundant copies and unpopular content. (2) Memory latency is high because the caches must be large. (3) Traffic filtering can result in high miss rates in the core and load imbalance. (4) Performance coupling among caches makes modeling their behavior intractable. CCndnS is a caching strategy for Named Data Networking that segments each file and spreads them among the caches, thus addressing the above issues: (1) It reduces redundant copies and cache pollution by unpopular content. (2) It reduces the number of futile checks on caches, thus reducing the delay from memory accesses. (3) It increases hit rates in the core without reducing hit rates at the edge (thus improving overall hit rates) and balances the load among caches. (4) It decouples the caches, so there is a simple analytical performance model for the network of caches. The efficacy of CCndnS and the accuracy of the model are validated with simulations using an Abilene-like topology.

Resource allocation is fundamental to cloud computing, where the memory hierarchy is deep. Space allocation in this hierarchy calls for a model to determine how provisioning at one level affects performance at a lower level. This paper presents a 3-level model that relates the Miss Ratio Curves for two caches at adjacent levels. The model is tested with NEXTmem, which is a transcendent memory used by a Xen hypervisor to cache pages for virtual machines. NEXTmem has a DRAM level and a nonvolatile memory level. The test runs DaCapo benchmarks and shows that the model can be used to enforce fairness at one level, and latency bounds at another level.

Social networks are driven by social interaction and therefore dynamic. When modeled as a graph, nodes and links are continually added and deleted, and there is considerable interest in social network analysis on predicting link formation. Current work has not adequately addressed three issues:

Network virtualization can potentially overcome Internet ossification. This technology lets multiple virtual networks run on a shared physical infrastructure. A key step lies in mapping a virtual network request to a resource allocation in the network substrate. Previous approaches to this network embedding problem assumed the request will ask for specific resources, such as network capacity or computing power. However, the end-user is more interested in performance. This paper therefore considers a different request format, namely a request will ask for a certain quality of service (QoS). The infrastructure provider must then determine the resource allocation necessary for this QoS. In particular, the provider must take into account user reaction to perceived performance and adjust the allocation dynamically. To this end, we propose an estimation mechanism that is based on analyzing the interaction between user behavior and network performance. This approach can dynamically adjust resource estimations when QoS requirements change. Our simulation-based experiments demonstrate that the proposed approach can satisfy user performance requirements through appropriate resource estimation. Moreover, our approach can adjust resource estimations efficiently and accurately.

Community wireless networks (CWNs) have been proposed to spread broadband network access to underprivileged, underprovisioned, and remote areas. Research has focused on optimizing network performance through intelligent routing and scheduling, borrowing solutions from mesh networks. Surprisingly, however, there has been no work on how to make efficient use of multiple channels in CWNs in the presence of multiple gateways and a single radio per device. In fact, today's deployments in underprivileged areas are primarily single-radio and do operate on a single channel. Frequency selection in such CWNs is very complex because it does not only determine the nodes' channel of operation, but also the gateway and the routing tree to the gateway-a rather computationally intensive task. In this paper, we propose, design, implement, and evaluate SWARM, a practical system that allows a CWN to make effective use of the available wireless channels in order to offer globally optimal performance. SWARM improves performance versus current single-channel protocols by up to 7.7 × in our experiments. Moreover, while we should be expecting performance gains due to channel diversity, we clearly demonstrate that up to 3.7 × improvement is attributed to the network organization into efficient traffic distribution structures.

Random writes significantly limit the application of flash-based Solid State Drive (SSD) in enterprise environment due to its poor latency, negative impact on SSD lifetime and high garbage collection overhead. To release above limitations, we propose a locality-aware cooperative buffer scheme referred to as FlashCoop (Flash Cooperation), which leverages free memory of neighboring storage server to buffer writes over high speed network. Both temporal and sequential localities of access pattern are exploited in the design of cooperative buffer management. Leveraging the filtering effect of the cooperative buffer, FlashCoop can efficiently shape the I/O request stream and improve the sequentiality of the write accesses passed to the SSD. FlashCoop has been extensively evaluated under various enterprise workloads. Our benchmark results conclusively demonstrate that FlashCoop can achieve 52.3% performance improvement and 56.5% garbage collection overhead reduction compared to the system without FlashCoop.

Community wireless networks (CWNs) have been proposed to spread broadband network access to underprivileged, under-provisioned and remote areas. Research has focused on optimizing network performance through intelligent routing and scheduling, borrowing solutions from mesh networks. Surprisingly, however, there has been no work on how to make efficient use of multiple channels in CWNs in the presence of multiple gateways, and a single radio per device. In fact, today's deployments in under-privileged areas are primarily single radio and do operate on a single channel [20]. Frequency selection in such CWNs is very complex because it does not only determine the nodes' channel of operation but also the gateway and the routing tree to the gateway - a rather computationally intensive task. In this paper, we propose, design, implement, and evaluate SWARM, a practical system that allows a CWN to make effective use of the available wireless channels in order to offer globally optimal performance. SWARM improves performance versus current single channel protocols by up to 7.7× in our experiments. Moreover, while we should be expecting performance gains due to channel diversity, we clearly demonstrate that up to 3.7 x improvement is attributed to the network organization into efficient traffic distribution structures.

As peer-to-peer (P2P) networks become more familiar to the database community, intense interest has built up in using their scalability and resilience properties to scale database applications. Indexing methods are adapted on top of P2P networks and querying methods are developed to handle the data distribution on different nodes. These procedures largely depend on how nodes are connected to each other. So far, limited attempts have been made to compare all these systems in a generalized framework. This is because the systems are quite different from each other, and there are so many of them that brute force comparison is practically impossible. Fortunately, it has recently been observed that a large subset of the most important P2P networks share a common algebraic and combinatorial base, in the form of Cayley graphs.

A large number of peer-to-peer (P2P) networks have been introduced in the literature since their popular advent in the late 1990s. In particular, structured P2P overlays have gained much attention since 2001. They are noted mainly for their theoretical properties such as balancing of communication, storage and processing load, as well as elegance of design.

Current businesses rely heavily on efficient access to their databases. Manual tuning of these database systems by performance experts is increasingly infeasible: For small companies, hiring an expert may be too expensive; for large enterprises, even an expert may not fully understand the interaction between a large system and its multiple changing workloads. This trend has led major vendors to offer tools that automatically and dynamically tune a database system. Many database tuning knobs concern the buffer pool for caching data and disk pages. Specifically, these knobs control the buffer allocation and thus the cache miss probability, which has direct impact on performance. Previous methods for automatic buffer tuning are based on simulation, black-box control, gradient descent, and empirical equations. This article presents a new approach, using calculations with an analytically-derived equation that relates miss probability to buffer allocation; this equation fits four buffer replacement policies, as well as twelve datasets from mainframes running commercial databases in large corporations. The equation identifies a buffer-size limit that is useful for buffer tuning and powering down idle buffers. It can also replace simulation in predicting I/O costs. Experiments with PostgreSQL illustrate how the equation can help optimize online buffer partitioning, ensure fairness in buffer reclamation, and dynamically retune the allocation when workloads change. It is also used, in conjunction with DB2's interface for retrieving miss data, for tuning DB2 buffer allocation to achieve targets for differentiated service.

Community wireless networks have been proposed as a powerful technique to spread broadband network access to underprivileged, under-provisioned and remote areas. These networks consist of a few Internet gateways which are reached by homes using multi-hop wireless links between wireless routers. The benefits of such networks include low costs for deployment due to reduced wiring needs, low maintenance and increased flexibility. Current practice in routing protocols for such networks (e.g. LQSR, OLSR and SrcRR) is for routing protocols to obtain information about the link quality (via some metric such as ETT, ETX) and select a gateway to whom a route minimizes the cost of the metric. All nodes operate on the same known frequency to maintain connectivity.

Admission control has been shown to be a preferred alternative to TCP-friendly congestion control for inelastic flows in heterogeneous networks shared by elastic and inelastic traffic [1]. However, it is possible for an inelastic flow to adopt different level of aggressiveness in implementing the admission control. How these different levels of aggressiveness affect the system performance remains an open issue. In this paper, we evaluate a full spectrum of (abstract) admission control algorithms in terms of their aggressiveness towards elastic flows. A totally aggressive version would admit an inelastic flow even if this means elastic flows' fair bandwidth share is reduced to close to zero. In the other extreme, a TCP-friendly version would only admit an inelastic flow if its desired rate is no higher than what the elastic flows will receive after its arrival. We show that the performance of inelastic flows is asymptotically insensitive to their aggressiveness without strong assumptions about flow file size or holding time distributions. This makes a strong case for adopting a less aggressive, yet TCP-friendly admission control in a heterogeneous network. Extensive simulations are carried out to validate the performance, stability and asymptotic behavior the the proposed TCP-friendly admission control policy.

MOTIVATION: A one-to-one correspondence between the sets of genes in the two genomes being compared is necessary for the notions of breakpoint and reversal distances. To compare genomes where there are paralogous genes, Sankoff formulated the exemplar distance problem as a general version of the genome rearrangement problem. Unfortunately, the problem is NP-hard even for the breakpoint distance. RESULTS: This paper proposes a divide-and-conquer approach for calculating the exemplar breakpoint distance between two genomes with multiple gene families. The combination of our approach and Sankoff's branch-and-bound technique leads to a practical program to answer this question. Tests with both simulated and real datasets show that our program is much more efficient than the existing program that is based only on the branch-and-bound technique. AVAILABILITY: Code for the program is available from the authors.

Recent research in sensor networks, wireless location systems, and power-saving in ad hoc networks suggests that some applications' wireless traffic be modeled as an event-driven workload: a workload where many nodes send traffic at the time of an event, not all reports of the event are needed by higher level protocols and applications, and events occur infrequently relative to the time needed to deliver all required event reports. We identify several applications that motivate the event-driven workload and propose a protocol that is optimal for this workload. Our proposed protocol, named CSMA/p/sup */, is nonpersistent carrier sense multiple access (CSMA) with a carefully chosen nonuniform probability distribution p/sup */ that nodes use to randomly select contention slots. We show that CSMA/p/sup */ is optimal in the sense that p/sup */ is the unique probability distribution that minimizes collisions between contending stations. CSMA/p/sup */ has knowledge of N. We conclude with an exploration of how p/sup */ could be used to build a more practical medium access control protocol via a probability distribution with no knowledge of N that approximates p/sup */.

Service providers have begun to offer multimedia-on-demand services to residential estates by installing isolated, small-scale multimedia servers at individual estates. Such an arrangement allows the service providers to operate without relying on a highspeed, large-capacity metropolitan area network, which is still not available in many countries. Unfortunately, installing isolated servers can incur very high server costs, as each server requires spare bandwidth to cope with fluctuations in user demand. The authors explore the feasibility of linking up several small multimedia servers to a (limited-capacity) network, and allowing servers with idle retrieval bandwidth to help out servers that are temporarily overloaded; the goal is to minimize the waiting time for service to begin. We identify four characteristics of load sharing in a distributed multimedia system that differentiate it from load balancing in a conventional distributed system. We then introduce a GWQ load sharing algorithm that fits and exploits these characteristics; it puts all servers' pending requests in a global queue, from which a server with idle capacity obtains additional jobs. The performance of the algorithm is captured by an analytical model, which we validate through simulations. Both the analytical and simulation models show that the algorithm vastly reduces wait times at the servers. The analytical model also provides guidelines for capacity planning. Finally, we propose an enhanced GWQ+L algorithm that allows a server to reclaim active local requests that are being serviced remotely. Simulation experiments indicate that the scheduling decisions of GWQ+L are optimal, i.e., it enables the distributed servers to approximate the performance of a large centralized server.

Article BROOM: buffer replacement using online optimization by mining Share on Authors: Anthony K. H. Tung Dept. of Computer Science, National Univ. of Singapore Dept. of Computer Science, National Univ. of SingaporeView Profile , Y. C. Tay Dept. of Mathematics, National Univ. of Singapore Dept. of Mathematics, National Univ. of SingaporeView Profile , Hongjun Lu Dept. of Computer Science, National Univ. of Singapore Dept. of Computer Science, National Univ. of SingaporeView Profile Authors Info & Claims CIKM '98: Proceedings of the seventh international conference on Information and knowledge managementNovember 1998 Pages 185–192https://doi.org/10.1145/288627.288656Online:01 November 1998Publication History 5citation261DownloadsMetricsTotal Citations5Total Downloads261Last 12 Months5Last 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

We present a performance model for transactions with firm deadlines on a database system that uses locking, but without priority scheduling. Such a system may be a legacy, or bought off-the-shelf. Excluding priority scheduling is also a way of determining how resource and data contention affect deadline misses. The model is used to (a) define a workload number that helps the evaluation of a system design by predicting the stress on it; (b) show that performance is proportional to the cube of transaction length, so transactions should request a minimal number of locks; (c) examine how deadlines should vary with transaction length, thus demonstrating the crucial role of resource contention; and (d) show that execution times and multiprogramming levels can cause a bias only though priority scheduling. We also offer an interpretation of "missed deadlines must be rare" in terms of abort cost.

10.1145/174147.174151

Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

Article Attribute agreement Share on Author: Y. C. Tay Department of Mathematics, National University of Singapore, Kent Ridge 0511, Republic of Singapore Department of Mathematics, National University of Singapore, Kent Ridge 0511, Republic of SingaporeView Profile Authors Info & Claims PODS '89: Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsMarch 1989 Pages 110–119https://doi.org/10.1145/73721.73732Online:29 March 1989Publication History 0citation174DownloadsMetricsTotal Citations0Total Downloads174Last 12 Months1Last 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

A new performance model for dynamic locking is proposed. It is based on a flow diagram and uses only the steady state average values of the variables. It is general enough to handle nonuniform access, shared locks, static locking, multiple transaction classes, and transactions of indeterminate length. The analysis is restricted to the case in which all conflicts are resolved by restarts. It has been shown elsewhere that, under certain conditions, this pure restart policy is as good as, if not better than, a policy that uses both blocking and restarts. The analysis is straightforward, and the computational complexity of the solution, given some nonrestrictive approximations, does not depend on the input parameters. The solution is also well defined and well behaved. The model's predictions agree well with simulation results. The model shows that data contention can cause the throughput to thrash, and gives a limit on the workload that will prevent this. It also shows that systems with a particular kind of nonuniform access and systems in which transactions share locks are equivalent to systems in which there is uniform access and only exclusive locking. Static locking has higher throughput, but longer response time, than dynamic locking. Replacing updates by queries in a multiprogramming mix may degrade performance if the queries are longer than the updates.

Analytic models based on closed queuing networks (CQNS) are widely used for performance prediction in practical systems. In using such models, there is always a prediction error, that is, a difference between the predicted performance and the actual outcome. This prediction error is due both to modeling errors and estimation errors, the latter being the difference between the estimated values of the CQN parameters and the actual outcomes. This paper considers the second class of errors; in particular, it studies the effect of small estimation errors and provides bounds on prediction errors based on bounds on estimation errors. Estimation errors may be divided into two types: (1) the difference between the estimated value and the average value of the outcome, and (2) the deviation of the actual value from its average. The analysis first studies the sum of both types of errors, then the second type alone. The results are illustrated with three examples.

An analytic model is used to study the performance of dynamic locking. The analysis uses only the steady-state average values of the variables. The solution to the model is given by a cubic, which has exactly one valid root for the range of parametric values that is of interest. The model's predictions agree well with simulation results for transactions that require up to twenty locks. The model separates data contention from resource contention, thus facilitating an analysis of their separate effects and their interaction. It shows that systems with a particular form of nonuniform access, or with shared locks, are equivalent to systems with uniform access and only exclusive locks. Blocking due to conflicts is found to impose an upper bound on transaction throughput; this fact leads to a rule of thumb on how much data contention should be permitted in a system. Throughput can exceed this bound if a transaction is restarted whenever it encounters a conflict, provided restart costs and resource contention are low. It can also be exceeded by making transactions predeclare their locks. Raising the multiprogramming level to increase throughput also raises the number of restarts per completion. Transactions should minimize their lock requests, because data contention is proportional to the square of the number of requests. The choice of how much data to lock at a time depends on which part of a general granularity curve the system sees.

An earlier paper introduced a simple performance model for studying the behaviour of locking. That paper treats a highly simplified form of locking, called the no waiting case, in which transactions restart when they request locks that are already held by others. This analysis is now extended to the more realistic waiting case, in which transactions are allowed to wait for conflicting locks, and restart only if there is a deadlock. The analysis begins with a system that has uniform access and exclusive locks only. The model's predictions for this base system agree well with simulation results. Next, a system with nonuniform access and another with shareable locks are each shown to be reducible to the base system. A comparison of the waiting and no waiting cases yields a surprising result: the throughput for the no waiting case is often better than for the waiting case, and never much worse.

Many different algorithms have been proposed for database concurrency control, and many more can be synthesized by combining locking and timestamping. The correctness of these algorithms is already well understood, their performance is not. We need a model to help us understand, compare and control the behavior of locking and timestamping we present here a model which we hope will eventually play such a role, but which we believe is simple to understand and use.

Database schemas may be partitioned into two sub-classes tree schemas and cyclic schemas. The analysis of tree vs cyclic schemas introduced the concepts of GYO reductions, canonical connections and tree projections. This paper investigates the intricate relationships among these concepts in the context of universal relation databases.