Scaling In-Memory databases on multicores

Current computer systems have evolved from featuring only a single processing unit and limited RAM, in the order of kilobytes or few megabytes, to include several multicore processors, o↵ering in the order of several tens of concurrent execution contexts, and have main memory in the order of several tens to hundreds of gigabytes. This allows to keep all data of many applications in the main memory, leading to the development of inmemory databases. Compared to disk-backed databases, in-memory databases (IMDBs) are expected to provide better performance by incurring in less I/O overhead. In this dissertation, we present a scalability study of two general purpose IMDBs on multicore systems. The results show that current general purpose IMDBs do not scale on multicores, due to contention among threads running concurrent transactions. In this work, we explore di↵erent direction to overcome the scalability issues of IMDBs in multicores, while enforcing strong isolation semantics. First, we present a solution that requires no modification to either database systems or to the applications, called MacroDB. MacroDB replicates the database among several engines, using a master-slave replication scheme, where update transactions execute on the master, while read-only transactions execute on slaves. This reduces contention, allowing MacroDB to o↵er scalable performance under read-only workloads, while updateintensive workloads su↵er from performance loss, when compared to the standalone engine. Second, we delve into the database engine and identify the concurrency control mechanism used by the storage sub-component as a scalability bottleneck. We then propose a new locking scheme that allows the removal of such mechanisms from the storage sub-component. This modification o↵ers performance improvement under all workloads, when compared to the standalone engine, while scalability is limited to read-only workloads. Next we addressed the scalability limitations for update-intensive workloads, and propose the reduction of locking granularity from the table level to the attribute level. This further improved performance for intensive and moderate update workloads, at a slight cost for read-only workloads. Scalability is limited to intensive-read and read-only workloads. Finally, we investigate the impact applications have on the performance of database systems, by studying how operation order inside transactions influences the database performance. We then propose a Read before Write (RbW) interaction pattern, under which transaction perform all read operations before executing write operations. The RbW pattern allowed TPC-C to achieve scalable performance on our modified engine for all workloads. Additionally, the RbW pattern allowed our modified engine to achieve scalable performance on multicores, almost up to the total number of cores, while enforcing strong isolation.

In-memory business process management

In-memory databases have become a mainstay of enterprise computing offering significant performance and scalability boosts for online analytical and (to a lesser extent) transactional processing as well as improved prospects for integration across different applications through an efficient shared database layer. Significant research and development has been undertaken over several years concerning data management considerations of in-memory databases. However, limited insights are available on the impacts of applications and their supportive middleware platforms and how they need to evolve to fully function through, and leverage, in-memory database capabilities. This paper provides a first, comprehensive exposition into how in-memory databases impact Business Pro- cess Management, as a mission-critical and exemplary model-driven integration and orchestration middleware. Through it, we argue that in-memory databases will render some prevalent uses of legacy BPM middleware obsolete, but also open up exciting possibilities for tighter application integration, better process automation performance and some entirely new BPM capabilities such as process-based application customization. To validate the feasibility of an in-memory BPM, we develop a surprisingly simple BPM runtime embedded into SAP HANA and providing for BPMN-based process automation capabilities.

WIQ:Work-intensive query scheduling for in-memory database systems

We propose a novel admission control policy for database queries. Our methodology uses system measurements of CPU utilization and query backlogs to determine interference between queries in execution on the same database server. Query interference may arise due to the concurrent access of hardware and software resources and can affect performance in positive and negative ways. Specifically our admission control considers the mix of jobs in service and prioritizes the query classes consuming CPU resources more efficiently. The policy ignores I/O subsystems and is therefore highly appropriate for in-memory databases. We validate our approach in trace-driven simulation and show performance increases of query slowdowns and throughputs compared to first-come first-served and shortest expected processing time first scheduling. Simulation experiments are parameterized from system traces of a SAP HANA in-memory database installation with TPC-H type workloads. © 2012 IEEE.

Managed Acceleration for In-Memory Database Analytic Workloads

In-Memory Databases (IMDBs), such as SAP HANA, enable new levels of database performance by removing the disk bottleneck and by compressing data in memory. The consequence of this improved performance means that reports and analytic queries can now be processed on demand. Therefore, the goal is now to provide near real-time responses to compute and data intensive analytic queries. To facilitate this, much work has investigated the use of acceleration technologies within the database context. While current research into the application of these technologies has yielded positive results, they have tended to focus on single database tasks or on isolated single user requests. This paper uses SHEPARD, a framework for managing accelerated tasks across shared heterogeneous resources, to introduce acceleration into an IMDB. Results show how, using SHEPARD, multiple simultaneous user queries all receive speed-up by using a shared pool of accelerators. Results also show that offloading analytic tasks onto accelerators can have indirect benefits for other database workloads by reducing contention for CPU resources.

On trip planning queries in spatial databases

In this paper we discuss a new type of query in Spatial Databases, called Trip Planning Query (TPQ). Given a set of points P in space, where each point belongs to a category, and given two points s and e, TPQ asks for the best trip that starts at s, passes through exactly one point from each category, and ends at e. An example of a TPQ is when a user wants to visit a set of different places and at the same time minimize the total travelling cost, e.g. what is the shortest travelling plan for me to visit an automobile shop, a CVS pharmacy outlet, and a Best Buy shop along my trip from A to B? The trip planning query is an extension of the well-known TSP problem and therefore is NP-hard. The difficulty of this query lies in the existence of multiple choices for each category. In this paper, we first study fast approximation algorithms for the trip planning query in a metric space, assuming that the data set fits in main memory, and give the theory analysis of their approximation bounds. Then, the trip planning query is examined for data sets that do not fit in main memory and must be stored on disk. For the disk-resident data, we consider two cases. In one case, we assume that the points are located in Euclidean space and indexed with an Rtree. In the other case, we consider the problem of points that lie on the edges of a spatial network (e.g. road network) and the distance between two points is defined using the shortest distance over the network. Finally, we give an experimental evaluation of the proposed algorithms using synthetic data sets generated on real road networks.

Multi-relational algorithm for mining association rules in large databases

Multi-relational data mining enables pattern mining from multiple tables. The existing multi-relational mining association rules algorithms are not able to process large volumes of data, because the amount of memory required exceeds the amount available. The proposed algorithm MRRadix presents a framework that promotes the optimization of memory usage. It also uses the concept of partitioning to handle large volumes of data. The original contribution of this proposal is enable a superior performance when compared to other related algorithms and moreover successfully concludes the task of mining association rules in large databases, bypass the problem of available memory. One of the tests showed that the MR-Radix presents fourteen times less memory usage than the GFP-growth. © 2011 IEEE.

Sponsorship-linked marketing: The role of articulation in memory

Corporate sponsorship of events contributes significantly to marketing aims, including brand awareness as measured by recall and recognition of sponsor‐event pairings. Unfortunately, resultant advantages accrue disproportionately to brands having a natural or congruent fit with the available sponsorship properties. In three cued‐recall experiments, the effect of articulation of sponsorship fit on memory for sponsor‐event pairings is examined. While congruent sponsors have a natural memory advantage, results demonstrate that memory improvements via articulation are possible for incongruent sponsor‐event pairings. These improvements are, however, affected by the presence of competitor brands and the way in which memory is accessed.

BDNF and TNF-α polymorphisms in memory

Here, we investigate the genetic basis of human memory in healthy individuals and the potential role of two polymorphisms, previously implicated in memory function. We have explored aspects of retrospective and prospective memory including semantic, short term, working and long-term memory in conjunction with brain derived neurotrophic factor (BDNF) and tumor necrosis factor-alpha (TNF-alpha). The memory scores for healthy individuals in the population were obtained for each memory type and the population was genotyped via restriction fragment length polymorphism for the BDNF rs6265 (Val66Met) SNP and via pyrosequencing for the TNF-alpha rs113325588 SNP. Using univariate ANOVA, a significant association of the BDNF polymorphism with visual and spatial memory retention and a significant association of the TNF-alpha polymorphism was observed with spatial memory retention. In addition, a significant interactive effect between BDNF and TNF-alpha polymorphisms was observed in spatial memory retention. In practice visual memory involves spatial information and the two memory systems work together, however our data demonstrate that individuals with the Val/Val BDNF genotype have poorer visual memory but higher spatial memory retention, indicating a level of interaction between TNF-alpha and BDNF in spatial memory retention. This is the first study to use genetic analysis to determine the interaction between BDNF and TNF-alpha in relation to memory in normal adults and provides important information regarding the effect of genetic determinants and gene interactions on human memory.

The grand philosopher of the Commons: In memory of Elinor Ostrom

The grand philosopher of the Commons, Elinor Ostrom, passed away on the 12th June 2012. She was a brilliant, creative polymath; a theoretician of fine precision and great intellectual power; a deviser of masterful empirical studies; and an energetic collaborator and networker. Ostrom posed a formidable intellectual challenge to the fields of economics and the social sciences - and the advocates of central regulation, privatization, and enclosure.

An algebraic theory of functional and multivalued dependencies in relational databases

Computation of the dependency basis is the fundamental step in solving the membership problem for functional dependencies (FDs) and multivalued dependencies (MVDs) in relational database theory. We examine this problem from an algebraic perspective. We introduce the notion of the inference basis of a set M of MVDs and show that it contains the maximum information about the logical consequences of M. We propose the notion of a dependency-lattice and develop an algebraic characterization of inference basis using simple notions from lattice theory. We also establish several interesting properties of dependency-lattices related to the implication problem. Founded on our characterization, we synthesize efficient algorithms for (a): computing the inference basis of a given set M of MVDs; (b): computing the dependency basis of a given attribute set w.r.t. M; and (c): solving the membership problem for MVDs. We also show that our results naturally extend to incorporate FDs also in a way that enables the solution of the membership problem for both FDs and MVDs put together. We finally show that our algorithms are more efficient than existing ones, when used to solve what we term the ‘generalized membership problem’.

Representation of functional dependencies in relational databases using linear graphs

Functional dependencies in relational databases are investigated. Eight binary relations, viz., (1) dependency relation, (2) equipotence relation, (3) dissidence relation, (4) completion relation, and dual relations of each of them are described. Any one of these eight relations can be used to represent the functional dependencies in a database. Results from linear graph theory are found helpful in obtaining these representations. The dependency relation directly gives the functional dependencies. The equipotence relation specifies the dependencies in terms of attribute sets which functionally determine each other. The dissidence relation specifies the dependencies in terms of saturated sets in a very indirect way. Completion relation represents the functional dependencies as a function, the range of which turns out to be a lattice. Depletion relation which is the dual of the completion relation can also represent functional dependencies and similarly can the duals of dependency, equipotence, and dissidence relations. The class of depleted sets, which is the dual of saturated sets, is defined and used in the study of depletion relations.

Oscillatory brain activity in memory disorders

Neuronal oscillations are thought to underlie interactions between distinct brain regions required for normal memory functioning. This study aimed at elucidating the neuronal basis of memory abnormalities in neurodegenerative disorders. Magnetoencephalography (MEG) was used to measure oscillatory brain signals in patients with Alzheimer s disease (AD), a neurodegenerative disease causing progressive cognitive decline, and mild cognitive impairment (MCI), a disorder characterized by mild but clinically significant complaints of memory loss without apparent impairment in other cognitive domains. Furthermore, to help interpret our AD/MCI results and to develop more powerful oscillatory MEG paradigms for clinical memory studies, oscillatory neuronal activity underlying declarative memory, the function which is afflicted first in both AD and MCI, was investigated in a group of healthy subjects. An increased temporal-lobe contribution coinciding with parieto-occipital deficits in oscillatory activity was observed in AD patients: sources in the 6 12.5 Hz range were significantly stronger in the parieto-occipital and significantly weaker in the right temporal region in AD patients, as compared to MCI patients and healthy elderly subjects. Further, the auditory steady-state response, thought to represent both evoked and induced activity, was enhanced in AD patients, as compared to controls, possibly reflecting decreased inhibition in auditory processing and deficits in adaptation to repetitive stimulation with low relevance. Finally, the methodological study revealed that successful declarative encoding and retrieval is associated with increases in occipital gamma and right hemisphere theta power in healthy unmedicated subjects. This result suggests that investigation of neuronal oscillations during cognitive performance could potentially be used to investigate declarative memory deficits in AD patients. Taken together, the present results provide an insight on the role of brain oscillatory activity in memory function and memory disorders.

Representation of functional dependencies in relational databases using linear graphs

Functional dependencies in relational databases are investigated. Eight binary relations, viz., (1) dependency relation, (2) equipotence relation, (3) dissidence relation, (4) completion relation, and dual relations of each of them are described. Any one of these eight relations can be used to represent the functional dependencies in a database. Results from linear graph theory are found helpful in obtaining these representations. The dependency relation directly gives the functional dependencies. The equipotence relation specifies the dependencies in terms of attribute sets which functionally determine each other. The dissidence relation specifies the dependencies in terms of saturated sets in a very indirect way. Completion relation represents the functional dependencies as a function, the range of which turns out to be a lattice. Depletion relation which is the dual of the completion relation can also represent functional dependencies and similarly can the duals of dependency, equipotence, and dissidence relations. The class of depleted sets, which is the dual of saturated sets, is defined and used in the study of depletion relations.

Eine Erinnerung an den 67. Geburtstag des Herrn Sobernheim (in memory of the 67th birthday of Mr. Sobernheim); Wiesbaden Portraits Groups

Participants include Erna Hirsch, Else Giesenow, Marta Nachmann, Erna Goldschmidt (Goldi), Lotte Strauss, Marta Bruchfeld, Toni Eichenberg, Grete Guthmann, Flora Goldschmidt, Hedwig Trum, Hedel Korhmann, Paula Arendt, Erna Behr and Frl. Minka Friedmann