Medical datasets play a crucial role in advancing healthcare research and supporting clinical decision-making. At the same time, the reliability of responsible and accountable AI systems is directly dependent on the integrity and transparency of the datasets on which they are built. The data subcard implements the System Cards framework's data assessment dimension to evaluate tabular medical datasets across four criteria: privacy, fairness, quality, and protection. It combines data-level profiling with optional model-based diagnostics, selected to fit each dataset, to assess completeness, duplication, outliers, demographic dispar-ities, re-identification risk, and compliance readiness. Applied to the UCI Heart Disease and Diabetes Readmission datasets, the method flags privacy risks, fairness imbalances, quality defects, and protection gaps that warrant review before modeling. The data subcard produces quantitative scores and visual summaries, providing a structured and interpretable mechanism for dataset accountability within the System Cards framework.

Electronic health record (EHR) datasets come in various schemas and can contain a range of data types, measurement units, and variables that share duplicate semantic content. The process of bringing such datasets into a common schema with consistent values, so that it is possible to perform queries uniformly, is known as harmonization. However, performing this process manually can be both time-consuming and prone to errors. In this work, we present a web-based platform that semi-automates the harmonization and linking of EHR datasets through a human-in-the-loop framework, guiding users with the use of large language models (LLMs). Our solution is a two-stage harmonization pipeline that keeps schema metadata processing online while handling patient-level data locally, to align with HIPAA data privacy principles. In the first stage, users harmonize and link only non-identifiable schema information. In the second stage, sensitive value-level harmonization occurs entirely on the user's system, so no private and protected health information ever leaves their environment. Throughout both stages, we expect that LLM-powered suggestions could potentially speed up the harmonization and linking processes.

Given the climate change crisis, there is a worldwide growing concern on energy production, energy consumption and pollution. Cloud computing represents a small fraction of global energy consumption, but trends indicate it will continue to grow, driven by Big Data and AI. AI analytics are pushing computing resources, especially CPUs and GPUs, to their limits. However, powerful CPUs and GPUs, consume tons of energy and require cooling appliances, which results into higher operating cost and as an indirect consequence, higher pollution and global warming. Based on these issues, we present a survey on measuring and reducing energy, especially when processing analytic workloads. We discuss tradeoffs between high performance (low latency to get results) and low energy (less power consumed over time). Our focus is on identifying modern hardware components which have a significant impact on energy consumption and then examining how software optimizations can manage hardware to reduce energy in a cloud data center. We conclude with a tentative research agenda, based on the state of the art of research at the intersection of big data analytics, high performance computing, electrical energy and cloud computing.

Key-value stores are a well-established technology for big data management, with many leveraging the Log-Structured Merge (LSM) tree for its high write throughput and efficient primary key lookups. However, searching for non-key values in LSM trees is slow, as it typically requires scanning all LSM tree files. Secondary indexes are a common solution, but they typically require rebuilding the entire LSM tree and involve a challenging selection of indexing attribute(s). To overcome these limitations, we propose a Bloom filter hierarchy to accelerate searching for non-key values in LSM trees. In a nutshell, a Bloom filter is built for each data file in the LSM tree, and then a hierarchy (another tree) of these Bloom filters is created. Experiments show our new indexing mechanism outperforms existing LSM methods by 80% with a small space overhead.

In Data Science, data modeling (including relational databases and big data) has traditionally used Entity-Relationship (ER) diagrams to represent structural characteristics of data. However, ER diagrams lack the capability to capture the flow and transformation of data through analytic pipelines, which are essential to manage modern data science workflows. On the other hand, flowcharts have been used for decades to describe the processing. Based on this motivation, this paper provides a historical perspective identifying the limitations of employing ER diagrams and Data Flow Diagrams (DFDs), separately, emphasizing the need to integrate both solutions. We examine established diagram notations and design models, including traditional models such as UML, ER, DFD, BPMN, and FLOWER. Our literature analysis suggests that integrative diagram approaches can provide a more intuitive and comprehensive understanding of data collection, data integration, and data transformation for big data analytics in the future.

Analytic processing systems have been traditionally designed to optimize time performance, leaving energy as a secondary aspect. More recently, during the past decade, there has been a growing interest in addressing the energy efficiency of analytics and in particular query processing (QP), our focus in this article. Numerous solutions, spanning both software and hardware approaches, have been proposed in database systems, but they have important limitations: (i) They were designed for old QP architectures, (ii) they do not consider emerging QP AI trends, such as learned query plans and hybrid QP, and (iii) they lack a well-defined framework with clear steps, which can be applied in a modern data science ecosystem. With such reasons in mind, we introduce a general framework that will help researchers and industry practitioners in addressing energy-efficiency challenges. Our framework, named ${SATM}^{2}V$, integrates five major steps: (1) assessing public sentiment and alerting analysts on the real impact of data science on decarbonization, (2) conducting “under the hood” energy consumption audits to identify energy-hungry components, (3) turning on/off and tuning parameters of components to understand their contribution to energy savings. (4) developing models and measurement techniques for quantifying energy consumption, (5) developing and executing tactics for energy saving. We then turn our attention to database systems and identify relational join processing as a representative energy consumption example. QP becomes particularly difficult when dealing with queries involving multiple join operations since join ordering is known to be an NP-hard problem, whose optimal solution remains an open problem. We apply our solution framework to the specific case of hybrid QPs, studying the impact of various join ordering optimization techniques on energy efficiency. Extensive experiments are conducted using the well-known Join Order Benchmark dataset to evaluate the effectiveness and tradeoffs of several query optimization techniques on time and energy consumption.

In a data science project, a significant effort is spent pre-processing databases, text and image data sets, before a machine learning model can be computed. Moreover, the analytic process is iterative, requiring a team of data scientists to add and remove features (attributes) from the target data set going all the way back to data sources. However, such programming effort is carried out without a data model behind, which results in redundant and inconsistent data sets and source code difficult to extend and maintain. On the other hand, the ER model has a proven track record to design databases before developing source code. Heeding the importance of data-centric models to store and analyze data, we propose a hybrid diagram (FLOWER=FLOW+ER) mixing data objects and processing flow, under the CRISP standard. Specifically, our novel diagram mixes ER entities (data objects) and processing steps (function calls). We explain how diagram creation can be partially automated by parsing source code. We present two case studies illustrating how our proposed hybrid diagram works in two challenging problems from biomedical engineering and computer vision: (1) detecting and classifying spikes in biomedical signals and (2) labeling identified objects in images. We argue our diagram can reduce code development time, enhance team collaboration and eliminate redundant data. We hope our work will motivate research bridging database design, project management and machine learning.

We discuss our progress towards solving a challenging biomedical problem: identifying similar patterns among multiple physiological nerve signals hidden in high throughput data, collected from micro electrical sensors implanted in several animal organs. The problem is difficult because patterns come as spikes within millisecond time-windows, data sets have high dimensionality and there is background electrical noise. A previous analytic system discovers patterns combining PCA dimensionality reduction and K-means clustering, which is slow and misses important patterns hidden by noise. Moreover, it requires reading the data set several times and it requires multiple languages and tools. With such limitations in mind, we present an improved, integrated system that effectively allows the discovery of more accurate patterns, with automated algorithm parameter tuning, by learning model parameters incrementally exploiting summarization. Our integrated solution combines signal filtering, variable construction (feature engineering) and multidimensional data summarization, for a tighter and more effective integration of PCA and K-means clustering. We present preliminary experiments on signals collected from key nerves in a rat. We show our method discovers more patterns in larger time-windows, with better noise filtering, taking less time. In the future, we plan to link signal patterns to specific physiological functions, paving the way for innovative medical treatment via nerve stimulation.

Given the large and growing volume of big data and frequent use of complex analytical queries, understanding energy efficiency of query processing has become a critical research issue, as highlighted by database systems papers in the last few years. Common software solutions mainly consider IO cost models to estimate energy consumption when executing queries. On the other hand, current hardware solutions benefit from advances in the development of green components and their associated tuning techniques, especially dynamic voltage and frequency scaling (DVFS), which can balance the performance and power consumption of multicore CPUs. Unfortunately, to the best of our knowledge, there is an absence of solutions mixing both (hardware and software). Heeding this gap, we propose a novel predictive model to measure and predict energy consumption of analytical queries when using multi-core processors and different frequency configurations. We first experimentally illustrate the surprising impact of CPU frequency and the number of processor cores on execution time, power and energy consumption. Second, we introduce an extended predictive model that enriches a well-known machine learning cost model with our new angle, the frequency scaling in multi-core environment. Specifically, by using Support Vector Regression and Random Forest Regression, we compute the energy coefficients of an accurate regression model for energy prediction. Experiments with benchmark data sets TPC-H and TPC-DS evaluate our proposed framework in terms of energy consumption reduction, showing promising results.

Clustering data streams is an important problem in big data analytics to detect and monitor activity in fast-evolving environments. We thereby present efficient variants of the K-Means algorithm for finding quality clusters in one-pass, suitable for stream processing in a DBMS. Our main variants are Online K-means, Incremental K-means, and Sliding Window K-means, which can consider or ignore time decay. We then explain how to integrate our algorithms with a DBMS using a combination of SQL queries and UDFs. Acceleration is achieved through a careful combination of optimizations, including sufficient statistics (data summarization), sparse distance computation (Jaccard and Euclidean), multithreaded processing (for multi-core CPUs), and sparse matrix operations. We present benchmark experiments comparing the quality of results and speed. We show that Incremental K-Means achieves similar or even better results than the Standard K-Means algorithm. On the other hand, we show that the sliding window K-Means algorithm captures the evolution of data streams through time.

Multidimensional data summarization is a fundamental mechanism to accelerate the computation of machine learning (ML) models. On the other hand, relational DBMSs can scale beyond main memory limits, they can evaluate SQL queries in parallel and they hide complex internal system details. Heeding this motivation, we present a wide spectrum of alternative SQL queries to compute a summarization matrix that significantly accelerates the computation of many ML models in a data science language (e.g. Python). We consider two fundamental storage layouts: horizontal and vertical. Our proposed SQL queries lead to diverse query plans, which in turn yield highly different processing times. We identify storage layout (row vs column) and relational join optimization as two key performance factors. After careful analysis and bechmarking, we recommend two SQL queries that can work across DBMSs. We show UDFs, an extensibility mechanism, despite being faster, they have many disadvantages compared to plain SQL queries (not portable, system-dependent limitations, main memory, manual optimization required). An extensive experimental evaluation shows the pros and cons of our proposed SQL-based solution. Columnar storage provides an order of magnitude performance improvement over row storage. Moreover, SQL queries can match UDF performance on sparse matrices. We show that by exploiting the summarization matrix in Python, the computation of two popular statistical models (Linear Regression and PCA), is much faster than popular Python libraries (on a single machine) and also faster than Apache Spark (in parallel, in-memory solution for big data clusters). We also show our SQL-based solution exhibits linear speedup in parallel processing. In short, the DBMS can act as a backend linear algebra kernel.

Two decades ago, the most popular data mining technique were association rules (ARs). Nowadays deep neural networks (DNNs) are the most popular mechanism for building predictive models. On the other hand, medical data sets, despite being generally small in size (low volume), they are challenging for predictive models due to diverse attribute content (high variety) and variables with low redundancy (high variability). In this work we compare these two analytic techniques to identify effective models to predict heart disease, a multi-target prediction problem. Both techniques require expertise, manual tuning, and iterative experimentation to determine optimal parameters. Our goal is to build a DNN model that is at least as good as the best ARs. There exist two Big Data challenges: risks factors combined with imaging attributes produce a large number of hidden patterns and the number of association rules reaches millions, without using search constraints at low support (frequency) values. Preliminary experiments on a real data set show discovered rules have high predictive accuracy and they provide a highly accurate, but highly specific, profile of sick patients. Despite careful data pre-processing and hyper-parameter tuning DNNs are slightly more accurate than association rules, but more generalizable. Therefore, both techniques can complement each other.

Incremental learning is used to continuously update and tune an existing model, as more data points come in. However, there is a tradeoff between speed and accuracy as the model becomes stable. From a big data angle, computing machine learning models is challenging when data sets cannot fit in main memory or when they exceed CPU capacity. On the other hand, data summarization is a fundamental technique that has promise to accelerate data science computations and compress a data set. Keeping these motivations in mind, we present an innovative system, VIM, that computes machine learning models in an incremental manner, visualizing continuous learning of model parameters as the data set is scanned. Our system is fast, it works for a wide spectrum of machine learning models and it can handle data sets larger than main memory. We developed an intuitive GUI which: (1) guides the user to upload data sets and choose a machine learning model, (2) offers interactive visualization of model parameters, and (3) helps getting an approximate model, stopping early, without reading the whole data set.

We present GALGO, a system for large scale graph analytics. GALGO provides complex graph analytics in a parallel cluster, exploiting a parallel database system as a computation engine. In this demonstration we show that fundamental graph algorithms including all pairs shortest path, single source shortest path, PageRank, triangle counting, connected components and reachability can be solved completely with queries, dynamically generated by our system. Our system presents performance that is very competitive to state-of-the-art graph systems. Furthermore, our out-of-core graph computation can process graphs larger than available main memory, without compromising performance.

Machine learning algorithms must be able to handle large volume in big data. Nowadays, data science languages such as Python and R, are widely popular to compute machine learning models. Unfortunately, model computation can be slow, especially when the data set does not fit in the main memory or it needs to be iteratively analyzed. With these motivations in mind, we present theory and algorithms to produce a multidimensional data set summary. We show our data summaries preserves essential statistical properties of the data set and it can be computed with an accelerated Gramian matrix multiplication. That is, our data summaries represents a lossless compression and we accelerate the expensive Gramian matrix multiplication in Python with C++ code. Our solution also works for a subset of the original data set obtained by variable selection without much loss on accuracy and without recomputing all intermediate matrices. We also consider parallel processing aspects leveraging our recently introduced low-cost parallel architecture. Our experimental evaluation shows that our Gramian matrix multiplication mechanism is superior to Python and it can work beyond RAM limitations. On the other hand, our computation of the machine learning model is competitive with the Python and R on a single machine, but it outperforms Spark in parallel machines.

In a typical Data Science project, the analyst uses many programming languages to explore and analyze big data coming from diverse data sources. A major challenge is managing and pre-processing so much data, with potentially inconsistent content, significant redundancy, in diverse formats, with varying data quality. Database systems research has tackled such problems for a long time, but mostly on relational databases. With such motivation in mind, this paper compares strengths and weaknesses of popular languages used nowadays from a database pespective: Python, R and SQL. We discuss the entire analytic pipeline, going from data integration, cleaning and pre-processing to model application and tuning. From a database systems perspective, we present a comprehensive survey of storage mechanisms, data processing algorithms, external algorithms, run-time memory management, consistency, optimizations and parallel processing. From a programming languages angle, we consider elegance, expressiveness, abstraction, composability, interactive behavior and automatic code optimization. We present a short experimental evaluation comparing the performance of the three languages on typical data exploration and pre-processing tasks. Our conclusion: there is no winner.

ER diagrams have a proven track record to rep-resent data structure and relationships, in many CS problems, beyond relational databases. The ER diagram strengths are abstraction, generality, flexibility, and intuitive visual representation, with few weaknesses; hence its popularity. The main con is the old box-diamond-ellipse-line notation, which has been subsumed by the more modern and simpler UML box-line notation. Given the broad, varied, and dynamic nature of big data ER diagrams are mostly ignored, except when the data sources are databases. It is common wisdom raw big data needs significant pre-processing before computing any analytics, resulting in a long chain of data transformations computed in SQL, Python, or R languages, for instance. On the other hand, flow diagrams remain the main mechanism to visualize major components of a software system or main processing steps of an algorithm, showing rectangles (verbs) connected by arrows (processing order, dependence). In this work, we propose to combine both diagrams into one. We propose a hybrid diagram, which we call ER-Flow, based on modern UML notation, to assist analysts in data pre-processing and exploration. Aiming to introduce a minimal change to the ER diagram, we extend relationships lines with an arrow, indicating processing flow and we annotate entities coming from pre-processing with numbers and transformation labels. We illustrate how our novel ER-Flow diagram can help the user navigate big data at the metadata level, providing an integrated view of data and source code, with many practical benefits.

Big Data Systems (Hadoop, DBMSs) require a complicated setup and tuning to store and process big data on a parallel cluster. This is mainly due to static partitioning when data sets are loaded or copied into the file system. Parallel processing thereafter works in a distributed manner, aiming for balanced parallel execution across nodes. Node synchronization, data redistribution and distributed caching in main memory are difficult to tune in the system. On the other hand, there exist analytical problems and algorithms, which can be computed in parallel, with minimal synchronization and fully independent computation. Moreover, some problems can be solved in one pass or few passes. In this paper, we introduce a low cost, yet useful, processing architecture in which data sets are dynamically partitioned at run-time and storage is transient. Each node processes one partition independently and partial results are gathered at the master processing node. Surprisingly, we show this architecture works well for some popular machine learning models as well as some graph algorithms. We attempt to identify which problem characteristics enable such efficient processing, and we also show the main bottleneck is the initial data set partitioning and distribution across nodes. We anticipate our architecture can benefit parallel processing in the cloud, where a dynamic number of virtual processors is decided at runtime or when the data set is analyzed for a short time.

Analysts prefer simpler interpreted languages to program their computations. Prominent languages include R, Python, and Matlab. On the other hand, analysts aim to compute mathematical models as fast as possible, especially with large data sets. Data summarization remains a fundamental technique to accelerate machine learning computations. Based on this motivation, we propose a novel summarization mechanism computed via a single matrix multiplication in the statistical R language. We show our summarization benefits a large family of linear models, including Linear Regression, PCA, and Naive Bayes. We present a subsystem that enables exploiting summarization by detecting Gramian matrix products in R. We optimize the existing R source code by overriding the internal R matrix multiplication algorithm using ours. Our solution can be plugged into R and help solving where a similar matrix multiplication appears, much faster and without RAM limitations. Moreover, our solution can be benefited from the parallel processing ability of the summarization matrix. We present an experimental validation showing our subsystem incurs little overhead since it works on source code while providing much faster speeds compared to the R language built-in functions. To round up our comparisons, we also compare our subsystem with Spark in parallel machines. For our solution, we assume that data can be in the HDFS, disk, or already partitioned. Our solution triumphs Spark in most cases proving we can also compete in the big data space.

Workload-driven approaches for partitioning and tuning traditional Parallel Database systems are well studied in the literature. Unfortunately, in the context of new generation "Big Data" warehouses, these approaches are not correctly adapted to Business Intelligence 2.0, where the analyst is at the heart of decision support systems. This "disconnect" situation strongly impacts both data partitioning and fragment allocation processes, which are essential to achieve good query performance. To overcome this problem, recent studies proposed online data partitioning and fragment allocation using AI techniques to improve query performance with adaptive behavior. Nevertheless, they have important limitations: they add significant overhead and they tend to focus on the current workload, ignoring query logs. With such motivation in mind, we first formulate the problem of optimizing database partitioning subject to feasibility constraints, based on a query workload. We then introduce a proactive partitioning approach combining offline and online processing phases, inspired by closed-loop control (used in engineering disciplines) and genetic algorithms (from AI). We present an experimental validation on a big data cluster that shows promising results on typical OLAP workloads.

Nowadays, energy reduction has become a critical and urgent issue for the database community. A lot of initiatives have been launched on energy-efficiency for intensive-workload computation covering individual hardware components, system software, to applications. This computation is mainly ensured by query optimizers. Their current versions minimize inputs-outputs operations and try to exploit RAM as much as possible, by ignoring energy. A couple of studies proposed the integration of energy into query optimizers that can be classified into hardware and software solutions. Several researchers have the idea that the operating systems and firmware manage energy and put software solutions in the second plan. This does not distinguish between tasks of operating systems and DBMSs. In this paper, we claim that building from scratch a green query processors and revisiting existing ones pass through 4-steps procedure: (1) establishment of a deep audit that allows understanding the query processor functioning, (2) identification of relevant energy-sensitive parameters belonging to hardware and software components, (3) elaboration of mathematical cost models estimating consumed energy when executing a query on a target DBMS and (4) setting of values of the energy-sensitive parameters using a nonlinear regression technique. To show the effectiveness of this procedure, we apply it on two open-source DBMSs with different functioning policies: PostgreSQL and MonetDB and compared them using the dataset and the workload of the TPC-H benchmark.

Software compliance, auditing, and maintainability of large application repositories force organizations to rely on source code analysis tools to identify code vulnerabilities, data flows, technical debt, and bugs. We propose a novel method to identify data flows within an application by analyzing the code traces or `links` that exist between the code and the data. Our application, SourceDB, leverages a relational database system as the backend to perform such discovery and computations. Our experiments show that SourceDB is able to process, analyze, and query the data source, logs, and source code in seconds.

Monitoring networks requires efficiently detecting abnormal events and summarizing connection information in big volumes of packet-level data. Some of these tasks can be accomplished with network and operating system utilities, but the questions should be relatively simple and each tool is designed to provide specific analysis. Another requirement is to be able to process data both in a centralized and decentralized manner, given the diversity in instrumentation and vantage points. On the other hand, database systems can answer complex questions phrased as queries, provided data is in the right format and is quickly loaded. Having such motivation in mind, we propose to monitor a network with queries, running on a traditional DBMS (i.e. not a custom-built system programmed in C or C++). Thus, queries can be processed in a central manner in a traditional database server or in a distributed fashion, with edge computing. Our experimental evaluation shows queries can indeed be used to monitor the network with low latency and reasonable delay on a low-resource device like the Raspberry Pi. We explain some interesting findings in a local network. In addition, we show queries can be efficiently evaluated in a small computing device capturing local traffic, showing promise for distributed monitoring.

Analyzing large data sets are challenging. Most data analytics research has proposed parallel algorithms that outside a DBMS because SQL is considered inadequate for complexity computations. R and Python are popular analysis systems that provide a vast collection of mathematical models and functions. However, they are limited by main memory and single computer. Recently, parallel DBMSs have significantly improved query processing performance. Moreover, SQL queries are elegant and efficient. This paper introduces a novel system architecture integrating a popular analysis system and parallel DBMSs, which has the matrix multiplication involving a large matrix evaluated inside a parallel DBMS and complex mathematical computations are done in R or Python. Many graph problems can be solved by matrix multiplication. In this paper, we show optimized queries which perform matrix multiplication in DBMSs to solve two fundamental graph problems, single-source reachability and transitive closure.

Triangles are an important pattern in large-scale graph analysis for their practical use in many real-life applications. However, with the expansion of networks, maintaining a balanced computational load is challenging especially for problems like triangle computations because of skewed vertices. On the other hand, there is a huge amount of data in database management systems (DBMSs) that can be modeled and analyzed as graphs. With these motivations in mind, we developed PandaSQL, a novel approach using SQL queries to enumerate all the triangles in a given graph based on Randomized Triangle Enumeration Algorithm. Our approach is elegant, abstract, and short compared to traditional languages like C++ or Python. Moreover, our partitioning queries ensures perfect load balancing. Thus, the triangle enumeration is independent, local, and parallel.

In big data analytics, graph problems are as important as machine learning. There exist many algorithms to analyze large graphs, but most of them are limited by the main memory. On the other hand, a lot of data stored on DBMSs needs to be analyzed as graphs. Even data is not in DBMSs, it is fast to load large data sets into DBMSs. More importantly, DBMSs can work in parallel and they do not have RAM limitations. Based on these reasons, we propose several algorithms that compute metrics and properties of the graph as well as help us to understand the graph structure specifically diameter, betweenness centrality. This work is a big step beyond transitive closure and recursive queries. We propose SQL queries that can work on a large graph stored in relational form as triples. And we prove these queries can compute complex graph metrics in a more flexible and efficient manner. Moreover, we study how to optimize the SQL queries combining demanding joins and aggregations that remove the main memory limitation and also can work in parallel. We provide an experimental evaluation to evaluate the accuracy and performance of our SQL algorithms by comparing our algorithms with popular platforms including Python and Spark. In general, the experiments show our SQL algorithms are accurate and efficient, without memory limitation.

Energy consumption is increasingly more important in large-scale query processing. This problem requires revisiting traditional query processing in actual DBMSs to identify the potential of energy saving, and to study the trade-offs between energy consumption and performance. In this paper, we propose EnerQuery, a tool built on top of a traditional DBMS to capitalize the efforts invested in building energy-aware query optimizers, which have the lion's share in energy consumption. Energy consumption is estimated on all query plan steps and integrated into a mathematical linear cost model used to select the best query plans. To increase end users' energy awareness, EnerQuery features a diagnostic GUI to visualize energy consumption per step and its savings when tuning key parameters during query execution.

Data summarization is an essential mechanism to accelerate analytic algorithms on large data sets. On the other hand, array DBMSs enable scalable computation with large matrices. With that motivation in mind, we propose a parallel array operator, based on a specific form of matrix multiplication, that computes a comprehensive data summarization matrix. By deriving equivalent equations based on the summarization matrix, statistical methods are adapted to work in two phases: (1) Parallel summarization of the data set in one pass; (2) Iteration exploiting the summarization matrix in many intermediate computations. We prove our summarization matrix captures essential statistical properties of the data set and it allows iterative algorithms to work faster in main memory, by decreasing the number of times the data set is scanned, and by reducing the number of CPU operations. Specifically, we show our summarization matrix benefits statistical models, including PCA, linear regression, and variable selection. From a systems perspective, we carefully study the efficient computation of the summarization matrix on the SciDB parallel array DBMS and how to exploit it in the R language statistical system. To achieve best performance, we introduce two specialized array operators for dense and sparse data sets, respectively. We present an experimental evaluation comparing SciDB, R, a columnar DBMS (a fast SQL engine), and Spark (a popular Hadoop system). Our experiments show R working together with SciDB eliminates main memory and performance limitations from R. More importantly, our R+SciDB prototype is significantly faster and more scalable than Spark and the columnar DBMS.

Presents the introductory editorial for this issue of the publication.

Given a table T ( Id , D 1 , …, D d ), the skycube of T is the set of skylines with respect to to all nonempty subsets (subspaces) of the set of all dimensions { D 1 , …, D d }. To optimize the evaluation of any skyline query, the solutions proposed so far in the literature either (i) precompute all of the skylines or (ii) use compression techniques so that the derivation of any skyline can be done with little effort. Even though solutions (i) are appealing because skyline queries have optimal execution time, they suffer from time and space scalability because the number of skylines to be materialized is exponential with respect to d . On the other hand, solutions (ii) are attractive in terms of memory consumption, but as we show, they also have a high time complexity. In this article, we make contributions to both kinds of solutions. We first observe that skyline patterns are monotonic. This property leads to a simple yet efficient solution for full and partial skycube materialization when the skyline with respect to all dimensions, the topmost skyline, is small. On the other hand, when the topmost skyline is large relative to the size of the input table, it turns out that functional dependencies, a fundamental concept in databases, uncover a monotonic property between skylines. Equipped with this information, we show that closed attributes sets are fundamental for partial and full skycube materialization. Extensive experiments with real and synthetic datasets show that our solutions generally outperform state-of-the-art algorithms.

The ACM DOLAP workshop presents research that bridges data warehousing, On-Line Analytical Processing (OLAP), and other large-scale data processing platforms. The program has four interesting sessions on data warehouse design, database modeling, query processing, and text processing, as well as an invited paper on Big Data Database Design.

Graphs represent a major challenge on big data analytics, for which there are many systems and prototypes, most of them not based on relational database management systems (DBMSs). Graph problems require substantially different algorithms compared to other analytical techniques (i.e., cubes, statistical models, machine learning) and they are especially important in the analysis of social networks and the Internet. On the other hand, recursive queries are a fundamental query mechanism to analyze graphs in a DBMS, but they can be slow with large graphs. Column DBMSs are a novel kind of faster database systems, but with significantly different storage and retrieval mechanisms compared to traditional row DBMSs. Thus we study the pros and cons of optimizing recursive queries on a column DBMS. Specifically, we study two inter-related graph problems: transitive closure and adjacency matrix multiplication, together with their respective optimization of queries combining recursive joins and recursive aggregations. An experimental evaluation with large graphs compares query optimization in a column DBMS and a row DBMS. We analyze performance tradeoffs with graphs having significantly different size, shape and connectivity. Our benchmark results prove column DBMSs are much faster than row DBMSs to analyze graphs, especially as graphs get larger and denser.

One of the major challenges of big data analytics is the diverse information content, which has no pre-defined structure or classification. This is in contrast to the well-designed structure of a database specified on an ER model. A standard mechanism for understanding interrelationships and the structure of documents is using ontologies. With such motivation in mind, we present a system that enables data management and querying of documents based on ontologies by leveraging the functionality of the DBMS. In this paper, we present ONTOCUBO, a novel system based on our research for text summarization using ontologies and automatic extraction of concepts for building ontologies using Online Analytical Processing (OLAP) cubes. ONTOCUBO is a database-centric approach that excels in its performance, due to an SQL-based single pass summarization phase through the original data set that computes values such as keyword frequency, standard deviation, and lift. This approach is complemented with a set of User-Defined-Function-based algorithms that analyze the summarization results for concepts and their interrelationships. Finally, we show in detail our application that extracts and builds an ontology, but also allows concept summarizations and allows domain experts to explore and modify the resulting ontology.

Bayesian models are generally computed with Markov Chain Monte Carlo (MCMC) methods. The main disadvantage about MCMC methods is the large number of iterations they need to sample the posterior distributions of model parameters, especially for large data sets. On the other hand, variable selection remains a challenging problem due to its combinatorial search space, where Bayesian models are a promising solution. In this work, we study how to accelerate Bayesian model computation for variable selection in linear regression. We propose a fast Gibbs sampler algorithm, a widely used MCMC method, that incorporates several optimizations. We use non-informative and conjugate prior distributions on several model parameters, which enable data set summarization in one pass exploiting an augmented set of sufficient statistics. Thereafter the algorithm can iterate in main memory. Sufficient statistics are indexed with a sparse binary vector to efficiently compute matrix projections based on selected variables. Discovered variable subsets probabilities, selecting and discarding each variable, are stored on a hash table for fast retrieval in future iterations. We study how to integrate our algorithm into a database management system (DBMS), exploiting aggregate User-Defined Functions for parallel data summarization and stored procedures to manipulate matrices with arrays. An experimental evaluation with real data sets evaluates accuracy and time performance, comparing our DBMS-based algorithm, with the R package. Our algorithm is shown to produce accurate results, scale linearly on data set size and run orders of magnitude faster than the R package.

Clustering is a fundamental problem in statistics and machine learning, whose solution is commonly computed by the Expectation-Maximization (EM) method, which finds a locally optimal solution for an objective function called log-likelihood. Since the surface of the log-likelihood function is non convex, a stochastic search with Markov Chain Monte Carlo (MCMC) methods can help escaping locally optimal solutions. In this article, we tackle two fundamental conflicting goals: Finding higher quality solutions and achieving faster convergence. With that motivation in mind, we introduce an efficient algorithm that combines elements of the EM and MCMC methods to find clustering solutions that are qualitatively better than those found by the standard EM method. Moreover, our hybrid algorithm allows tuning model parameters and understanding the uncertainty in their estimation. The main issue with MCMC methods is that they generally require a very large number of iterations to explore the posterior of each model parameter. Convergence is accelerated by several algorithmic improvements which include sufficient statistics, simplified model parameter priors, fixing covariance matrices and iterative sampling from small blocks of the data set. A brief experimental evaluation shows promising results.

Hardware technology has improved to a point where a solid state drive (SSD) can read faster than a traditional hard disk drive (HDD). This unique ability to retrieve data quickly combines perfectly with OLAP cube processing. In this paper, we study how to improve performance of OLAP cube processing on SSDs. The main novelty of our work is that we do not alter the internal subsystems of the DBMS. Instead, the DBMS treats the SSD as though it was a regular HDD. We propose optimizations for SQL queries to enhance their performance on SSDs. An experimental evaluation with the TPC-H database compares performance of our optimizations on SSDs and HDDs. We found that even though SSDs have slower write speeds than HDDs, their excellent read speed more than overcomes this limitation.

Finding aggregations of records with high dimensionality in large data warehouses is a crucial and costly task. These groups of similar records are the result of partitions obtained with GROUP BYs. In this research, we focus on obtaining aggregations of groups of similar records by turning the problem into efficient binary clustering of a fact table as a relaxation of a GROUP BY clause. We present an efficient window-based Incremental K-Means algorithm in a relational database system implemented as a user-defined function. This variant is based on the Incremental K-Means algorithm. The speed up is achieved through the computation of sufficient statistics, multithreading, efficient distance computation and sparse matrix operations. Finally, the performance of our algorithm is compared against multiple variants of the K-Means algorithm. Our experiments show that our incremental K-Means algorithm achieves similar or even better results more quickly than the traditional K-Means algorithm.

Relational DBMSs remain the main data management technology, despite the big data analytics and no-SQL waves. On the other hand, for data analytics in a broad sense, there are plenty of non-DBMS tools including statistical languages, matrix packages, generic data mining programs and large-scale parallel systems, being the main technology for big data analytics. Such large-scale systems are mostly based on the Hadoop distributed file system and MapReduce. Thus it would seem a DBMS is not a good technology to analyze big data, going beyond SQL queries, acting just as a reliable and fast data repository. In this survey, we argue that is not the case, explaining important research that has enabled analytics on large databases inside a DBMS. However, we also argue DBMSs cannot compete with parallel systems like MapReduce to analyze web-scale text data. Therefore, each technology will keep influencing each other. We conclude with a proposal of long-term research issues, considering the "big data analytics" trend.

We present a novel cloud system based on DBMS technology, where data mining algorithms are offered as a service. A local DBMS connects to the cloud and the cloud system returns computed data mining models as small relational tables that are archived and which can be easily transferred, queried and integrated with the client database. Unlike other analytic systems, our solution is not based on MapReduce. Our system avoids exporting large tables outside the local DBMS and thus it avoids transmitting large volumes of data to the cloud. The system offers three processing modes: local, cloud and hybrid, where a linear cost model is used to choose processing mode. In hybrid mode processing is split between the local DBMS and the cloud DBMS. Our system has a job scheduler with FIFO, SJF and RR policies to enhance response time and get partial results early. The cloud DBMS performs dynamic job scheduling, model computation and model archive management. Our system incorporates several optimizations: local data set summarization with sufficient statistics, sampling, caching matrices in RAM and selectively transmitting small matrices, back and forth. We show that in general the most efficient computing mechanism is hybrid processing: summarizing or sampling the data set in the local DBMS, transferring small matrices back and forth, leaving mathematically complex methods as a task for the cloud DBMS.

Efficient and scalable execution of numerical methods inside a DBMS is difficult as its architecture is not suited for intense numerical computations. We study computing Principal Component Analysis (PCA) on large data sets via Singular Value Decomposition (SVD). Given the difficulty to program and optimize numerical methods on an existing DBMS, we explore an alternative reusability approach: calling the well-known numerical library LAPACK. Thus we study several alternatives to summarize the data set with aggregate User-Defined Functions (UDFs) and how to efficiently call SVD numerical methods available in LAPACK via Stored Procedures (SPs). We propose algorithmic and system optimizations to enhance scalability and to push processing into RAM. We show it is feasible to efficiently solve PCA by first summarizing the data set with arrays incrementally updated with aggregate UDFs and then pushing heavy matrix processing in SVD to RAM calling LAPACK via SPs. We benchmark our solution on a modern DBMS. Our solution requires only one pass on the data set and it exhibits linear scalability.

Text columns commonly extend core information stored as atomic values in a relational database, creating a need to explore and summarize text data. OLAP cubes can precisely accomplish such tasks. However, cubes have been overlooked as a mechanism for capturing not only text summarizations, but also for representing and exploring the hierarchical structure of an ontology. In this paper, we focus on exploiting cubes to compute multidimensional aggregations on classified documents stored in a DBMS (keyword frequency, document count, document class frequency and so on). We propose CUBO (CUBed Ontologies), a novel algorithm, which efficiently manipulates the hierarchy behind an ontology. Our algorithm is optimized to compute desired summarizations without having to search all possible dimension combinations, exploiting the sparseness of the document classification frequency matrix. Experiments on large text data sets show CUBO can explore faster more dimension combinations than a standard cube algorithm, especially when the cube has a large number of dimensions. CUBO was developed entirely inside a DBMS, using SQL queries and extensibility features.

SQL presents limitations to return aggregations as tables with a horizontal layout. A user generally needs to write separate queries and data definition statements to combine transposition with aggregation. With that motivation in mind, we introduce horizontal aggregations, a complementary class of aggregations to traditional (vertical) SQL aggregations. The SQL syntax extension is minimal and it significantly enhances the expressive power and ease of use of SQL. Our proposed SQL extension blurs the boundary between row values and column names. We present a prototype query optimizer that can evaluate arbitrary nested queries combining filtering, joins and both classes of aggregations. Horizontal aggregations have many applications in ad-hoc querying, OLAP cube processing and data mining. We demonstrate query optimization of horizontal aggregations introduces new research challenges.

Preparing a data set for analysis is generally the most time consuming task in a data mining project, requiring many complex SQL queries, joining tables, and aggregating columns. Existing SQL aggregations have limitations to prepare data sets because they return one column per aggregated group. In general, a significant manual effort is required to build data sets, where a horizontal layout is required. We propose simple, yet powerful, methods to generate SQL code to return aggregated columns in a horizontal tabular layout, returning a set of numbers instead of one number per row. This new class of functions is called horizontal aggregations. Horizontal aggregations build data sets with a horizontal denormalized layout (e.g., point-dimension, observation-variable, instance-feature), which is the standard layout required by most data mining algorithms. We propose three fundamental methods to evaluate horizontal aggregations: CASE: Exploiting the programming CASE construct; SPJ: Based on standard relational algebra operators (SPJ queries); PIVOT: Using the PIVOT operator, which is offered by some DBMSs. Experiments with large tables compare the proposed query evaluation methods. Our CASE method has similar speed to the PIVOT operator and it is much faster than the SPJ method. In general, the CASE and PIVOT methods exhibit linear scalability, whereas the SPJ method does not.

Ontologies are knowledge conceptualizations of a particular domain and are commonly represented with hierarchies. While final ontologies appear deceivingly simple on paper, building ontologies represents a time-consuming task that is normally performed by natural language processing techniques or schema matching. On the other hand, OLAP cubes are most commonly used during decision-making processes via the analysis of data summarizations. In this paper, we present a novel approach based on using OLAP cubes for ontology extraction. The resulting ontology is obtained through an analytical process of the summarized frequencies of keywords within a corpus. The solution was implemented within a relational database system (DBMS). In our experiments, we show how all the proposed discrimination measures (frequency, correlation, lift) affect the resulting classes. We also show a sample ontology result and the accuracy of finding true classes. Finally, we show the performance breakdown of our algorithm.

There exist many interrelated information sources on the Internet that can be categorized into structured (database) and semistructured (documents). A key challenge is to integrate, query and analyze such heterogeneous collections of information. In this paper, we defend the idea of building web metadata repositories using relational databases as the main source and central data management technology of structured data, enriched by the semistructured data surrounding it. Our proposal rests on the assumption that heterogeneous relational databases can be integrated (i.e. entity resolution is assumed to work well) and thus can serve as references for external data. That is, we tackle the problem of integrating information in the deep web, departing from databases. We discuss a prototype system that can integrate and query metadata and related documents, based on relational database technology. Metadata includes database ER model elements like database name, table, and column (entity, attribute). Web document data include files, documents and web pages. Links between metadata and external documents are built with SQL queries. Once databases and documents are linked, they are managed and queried with SQL. We discuss an interesting scientific application of our solution with a water pollution database.

Most research on data mining has proposed algorithms and optimizations that work on flat files, outside a DBMS, mainly due to the following reasons. It is easier to develop efficient algorithms in a traditional programming language. The integration of data mining algorithms into a DBMS is difficult given its relational model foundation and system architecture. Moreover, SQL may be slow and cumbersome for numerical analysis computations. Therefore, data mining users commonly export data sets outside the DBMS for data mining processing, which creates a performance bottleneck and eliminates important data management capabilities such as query processing and security, among others (e.g. concurrency control and fault tolerance). With that motivation in mind, we developed a novel system based on SQL queries and User-Defined Functions (UDFs) that can directly analyze relational tables to compute statistical models, storing such models as relational tables as well. Most algorithms have been optimized to reduce the number of passes on the data set. Our system can analyze large and high dimensional data sets faster than external data mining tools.

An OLAP cube is typically explored with multiple aggregations selecting different subsets of cube dimensions to analyze trends or to discover unexpected results. Unfortunately, such analytic process is generally manual and fails to statistically explain results. In this work, we propose to combine dimension lattice traversal and parametric statistical tests to identify significant metric differences between cube cells. We present a 2D interactive visualization of the OLAP cube based on a checkerboard that enables isolating and interpreting significant measure differences between two similar cuboids, which differ in one dimension and have the same values on the remaining dimensions. Cube exploration and visualization is performed by automatically generated SQL queries. An experimental evaluation with a medical data set presents statistically significant results and interactive visualizations, which link risk factors and degree of disease.

Data mining research is extensive, but most work has proposed efficient algorithms, data structures and optimizations that work outside a DBMS, mostly on flat files. In contrast, we present a data mining system that can work on top of a relational DBMS based on a combination of SQL queries and User-Defined Functions (UDFs), debuking the common perception that SQL is inefficient or inadequate for data mining. We show our system can analyze large data sets significantly faster than external data mining tools. Moreover, our UDF-based algorithms can process a data set in one pass and have linear scalability.

Query recommendation is an invaluable tool for enabling users to speed up their searches. In this paper, we present algorithms for generating query suggestions, assuming no previous knowledge of the collection. We developed an online OLAP algorithm to generate query suggestions for the users based on the frequency of the keywords in the selected documents and the correlation between the keywords in the collection. In addition, performance and scalability experiments of these algorithms are presented as proof of their feasibility. We also present sampling as an additional approach for improving performance by using approximate results. We show valid recommendations as a result of combinations generated using the correlations between the keywords. The online OLAP algorithm is also compared with the well-known Apriori algorithm and found to be faster only when simple computations were performed in smaller collections with a few keywords. On the other hand, OLAP showed a more stable behavior between collections, and allows us to have more complex policies during the aggregation and term combinations. Additionally, sampling showed improvement in the time without a significant change on the suggested queries, and proved to be an accurate alternative with a few small samples.

The ACM DOLAP workshop presents research on data warehousing and On-Line Analytical Processing (OLAP). The program has three interesting sessions on modeling, query processing and new trends, as well as a keynote talk on OLAP query processing and a panel comparing relational and non-relational technology for data warehousing.

Many database applications and OLAP tools dynamically generate SQL queries involving join operators and aggregate functions and send these queries to a database server for execution. This dynamically generated SQL code normally assumes the underlying tables and columns are clean and lacks the necessary robustness to deal with foreign keys with null and invalid or undefined values that are ubiquitous in databases with inconsistent or incomplete content. The outcome is that at query time, several issues arise mostly as inconsistencies in answer sets, difficult to detect and explain by users of OLAP tools. In this article, we present an automated query rewriting method for automatically generated OLAP queries that are executed over tables with foreign key columns having potentially null or invalid values. Our method is applicable in queries that use join operators and aggregate functions obeying the summarizability property (e.g. sum(), count()). If a user of an OLAP tool wants or requests it, using our method the queries that use join operators may be rewritten and he or she may be warned of the referential integrity condition of the underlying database and the answer sets may present alternative consistent results in the case aggregate functions are involved. Preliminary experimental evaluation shows rewritten queries provide valuable information on referential integrity and take almost the same time as original queries, highlighting efficiency is good and overhead is minimal.

Relational database systems have been the dominating technology to manage and analyze large data warehouses. Moreover, the ER model, the standard in database design has a close relationship with the relational model. Recently, there has been a surge of alternative technologies for large scale analytic processing, most of which are not based on the relational model. Out of these proposals, distributed file systems together with MapReduce have become strong competitors to relational database systems to analyze large data sets, exploiting parallel processing. Moreover, there is progress on using MapReduce to evaluate relational queries. With that motivation in mind, this panel will compare pros and cons of each technology for data warehousing and will identify research issues, considering practical aspects like ease of use, programming flexibility and cost; as well as technical aspects like data modeling, storage, hardware, scalability, query processing, fault tolerance and data mining.

Computing Bayesian statistics with traditional techniques is extremely slow, specially when large data has to be exported from a relational DBMS. We propose algorithms for large scale processing of stochastic search variable selection (SSVS) for linear regression that can work entirely inside a DBMS. The traditional SSVS algorithm requires multiple scans of the input data in order to compute a regression model. Due to our optimizations, SSVS can be done in either one scan over the input table for large number of records with sufficient statistics, or one scan per iteration for high-dimensional data. We consider storage layouts which efficiently exploit DBMS parallel processing of aggregate functions. Experimental results demonstrate correctness, convergence and performance of our algorithms. Finally, the algorithms show good scalability for data with a very large number of records, or a very high number of dimensions.

Data mining remains an important research area in database systems. We present a review of processing alternatives, storage mechanisms, algorithms, data structures and optimizations that enable data mining on large data sets. We focus on the computation of well-known multidimensional statistical and machine learning models. We pay particular attention to SQL and MapReduce as two competing technologies for large scale processing. We conclude with a summary of solved major problems and open research issues.

Recursion is a fundamental computation mechanism which has been incorporated into the SQL language. This work focuses on the optimization of linear recursive queries in SQL. Query optimization is studied with two important graph problems: computing the transitive closure of a graph and getting the power matrix of its adjacency matrix. We present SQL implementations for two fundamental algorithms: seminaive and direct. Five query optimizations are studied: 1) storage and indexing; 2) early selection; 3) early evaluation of nonrecursive joins; 4) pushing duplicate elimination; and 5) pushing aggregation. Experiments compare both evaluation algorithms and systematically evaluate the impact of optimizations with large input tables. Optimizations are evaluated on four types of graphs: binary trees, lists, cyclic graphs, and complete graphs, going from the best to worst case. In general, Seminaive is faster than direct, except for complete graphs. Storing and indexing rows by vertex and pushing aggregation work well on trees, lists, and cyclic graphs. Pushing duplicate elimination is essential for complete graphs, but slows computation for acyclic graphs. Early selection with equality predicates significantly accelerates computation for all types of graphs.

Statistical models are generally computed outside a DBMS due to their mathematical complexity. We introduce techniques to efficiently compute fundamental statistical models inside a DBMS exploiting User-Defined Functions (UDFs). Specifically, we study the computation of linear regression, PCA, clustering, and Naive Bayes. Two summary matrices on the data set are mathematically shown to be essential for all models: the linear sum of points and the quadratic sum of cross products of points. We consider two layouts for the input data set: horizontal and vertical. We first introduce efficient SQL queries to compute summary matrices and score the data set. Based on the SQL framework, we introduce UDFs that work in a single table scan: aggregate UDFs to compute summary matrices for all models and a set of primitive scalar UDFs to score data sets. Experiments compare UDFs and SQL queries (running inside the DBMS) with C++ (analyzing exported files). In general, UDFs are faster than SQL queries and not much slower than C++. Considering export times, C++ is slower than UDFs and SQL queries. Statistical models based on precomputed summary matrices are computed in a few seconds. UDFs scale linearly and only require one table scan, highlighting their efficiency.

The Bayesian classifier is a fundamental classification technique. In this work, we focus on programming Bayesian classifiers in SQL. We introduce two classifiers: naive Bayes and a classifier based on class decomposition using K-means clustering. We consider two complementary tasks: model computation and scoring a data set. We study several layouts for tables and several indexing alternatives. We analyze how to transform equations into efficient SQL queries and introduce several query optimizations. We conduct experiments with real and synthetic data sets to evaluate classification accuracy, query optimizations, and scalability. Our Bayesian classifier is more accurate than naive Bayes and decision trees. Distance computation is significantly accelerated with horizontal layout for tables, denormalization, and pivoting. We also compare naive Bayes implementations in SQL and C++: SQL is about four times slower. Our Bayesian classifier in SQL achieves high classification accuracy, can efficiently analyze large data sets, and has linear scalability.

Queries on digital libraries generally involve the retrieval of specific documents, but most techniques lack the ability to efficiently explore these collections. The integration of OLAP techniques with digital libraries allows users to navigate throughout these collections on multiple levels. In order to accomplish this, we propose the creation of OLAP networks, a complex data structure that contains summarized representations of the original collection of metadata to enrich traditional retrievals and allow the users to quickly explore the collection. We developed a system that enables OLAP-based exploration on the metadata of digital libraries through the use of a combination of efficient UDFs and optimized SQL queries. In addition, we also incorporated visualization methods into our system to allow fast navigation and exploration.

OLAP tools for distributed data warehouses generally assume underlying replicated tables are up to date. Unfortunately, maintaining updated replicas is difficult due to the inherent tradeoff between consistency and availability. In this paper, we propose techniques to evaluate OLAP queries in distributed data warehouses assuming a lazy replication model. Considering that it may be admissible to evaluate OLAP queries with slightly outdated replicated tables, our technique first efficiently computes the degree of obsolescence of replicated local tables and when such result is acceptable, given an error threshold, then the query is evaluated locally, avoiding the transmission of large tables over the network. Otherwise, the query can be remotely evaluated less efficiently with the master copy of tables, provided they are stored at a single site. Inconsistency measurement is computed by adapting distributed set reconciliation algorithms to efficiently compute the symmetric difference between the master and replicated tables. Our improved distributed database algorithm has linear communication complexity and cubic time complexity in the size of the symmetric difference, which is expected to be small in a replicated data warehouse. Our technique is independent of the method employed to propagate data warehouse insertions, deletions and updates. We present experiments simulating distributed databases, with different CPU and transmission speeds, showing our method is effective to decide if the query should be evaluated either locally or remotely.

OLAP is a set of database exploratory techniques to efficiently retrieve multiple sets of aggregations from a large dataset. Generally, these techniques have either involved the use of an external OLAP server or required the dataset to be exported to a specialized OLAP tool for more efficient processing. In this work, we show that OLAP techniques can be performed within a modern DBMS without external servers or the exporting of datasets, using standard SQL queries and UDFs. The main challenge of such approach is that SQL and UDFs are not as flexible as the C language to explore the OLAP lattice and therefore it is more difficult to develop optimizations. We compare three different ways of performing OLAP exploration: plain SQL queries, a UDF implementing a lattice structure, and a UDF programming the star cube structure. We demonstrate how such methods can be used to efficiently explore typical OLAP datasets.

Since the early 1990s, On-Line Analytical Processing (OLAP) has been a well studied research topic that has focused on implementation outside the database, either with OLAP servers or entirely within the client computers. Our approach involves the computation and storage of OLAP cubes using User-Defined Functions (UDF) with a database management system. UDFs offer users a chance to write their own code that can then called like any other standard SQL function. By generating OLAP cubes within a UDF, we are able to create the entire lattice in main memory. The UDF also allows the user to assert more control over the actual generation process than when using standard OLAP functions such as the CUBE operator. We introduce a data structure that can not only efficiently create an OLAP lattice in main memory, but also be adapted to generate association rule itemsets with minimal change. We experimentally show that the UDF approach is more efficient than SQL using one real dataset and a synthetic dataset. Also, we present several experiments showing that generating association rule itemsets using the UDF approach is comparable to a SQL approach. In this paper, we show that techniques such as OLAP and association rules can be efficiently pushed into the UDF, and has better performance, in most cases, compared to standard SQL functions.

Database integration builds on tables coming from multiple databases by creating a single view of all these data. Each database has different tables, columns with similar content across databases and different referential integrity constraints. Thus, a query in an integrated database is likely to involve tables and columns with referential integrity errors. In a data warehouse environment, even though the ETL processes take care of the referential integrity errors, in many scenarios this is generally done by including 'dummy' records in the dimension tables used to relate to the fact tables with referential errors. When two tables are joined, and aggregations are computed, the tuples with an undefined foreign key value are aggregated in a group marked as undefined effectively discarding potentially valuable information. With that motivation in mind, we extend aggregate functions computed over tables with referential integrity errors on OLAP databases to return complete answer sets in the sense that no tuple is excluded. We associate to each valid reference, the probability that an invalid reference may actually be a certain correct reference. The main idea of our work is that in certain contexts, it is possible to use tuples with invalid references by taking into account the probability that an invalid reference actually be a certain correct reference. This way, improved answer sets are obtained from aggregate queries in settings where a database violates referential integrity constraints.

Multidimensional statistical models are generally computed outside a relational DBMS, exporting data sets. This article explains how fundamental multidimensional statistical models are computed inside the DBMS in a single table scan exploiting SQL and User-Defined Functions (UDFs). The techniques described herein are used in a commercial data mining tool, called Teradata Warehouse Miner. Specifically, we explain how correlation, linear regression, PCA and clustering, are integrated into the Teradata DBMS. Two major database processing tasks are discussed: building a model and scoring a data set based on a model. To build a model two summary matrices are shown to be common and essential for all linear models: the linear sum of points and the quadratic sum of cross-products of points. Since such matrices are generally significantly smaller than the data set, we explain how the remaining matrix operations to build the model can be quickly performed outside the DBMS. We first explain how to efficiently compute summary matrices with plain SQL queries. Then we present two sets of UDFs that work in a single table scan: an aggregate UDF to compute summary matrices and a set of scalar UDFs to score data sets. Experiments compare UDFs and SQL queries (running inside the DBMS) with C++ (running outside on exported files). In general, UDFs are faster than SQL queries and UDFs are more efficient than C++, due to long export times. Statistical models based on the summary matrices can be built outside the DBMS in just a few seconds. Aggregate and scalar UDFs scale linearly and require only one table scan, making them ideal to process large data sets.

In general, a relational DBMS provides limited capabilities to perform multidimensional statistical analysis, which requires manipulating vectors and matrices. In this work, we study how to extend a DBMS with basic vector and matrix operators by programming User-Defined Functions (UDFs). We carefully analyze UDF features and limitations to implement vector and matrix operations commonly used in statistics, machine learning and data mining, paying attention to DBMS, operating system and computer architecture constraints. UDFs represent a C programming interface that allows the definition of scalar and aggregate functions that can be used in SQL. UDFs have several advantages and limitations. A UDF allows fast evaluation of arithmetic expressions, memory manipulation, using multidimensional arrays and exploiting all C language control statements. Nevertheless, a UDF cannot perform disk I/O, the amount of heap and stack memory that can be allocated is small and the UDF code must consider specific architecture characteristics of the DBMS. We experimentally compare UDFs and SQL with respect to performance, ease of use, flexibility and scalability. We profile UDFs based on call overhead, memory management and interleaved disk access. We show UDFs are faster than standard SQL aggregations and as fast as SQL arithmetic expressions.

Integrating data mining algorithms with a relational DBMS is an important problem for database programmers. We introduce three SQL implementations of the popular K-means clustering algorithm to integrate it with a relational DBMS: 1) a straightforward translation of K-means computations into SQL, 2) an optimized version based on improved data organization, efficient indexing, sufficient statistics, and rewritten queries, and 3) an incremental version that uses the optimized version as a building block with fast convergence and automated reseeding. We experimentally show the proposed K-means implementations work correctly and can cluster large data sets. We identify which K-means computations are more critical for performance. The optimized and incremental K-means implementations exhibit linear scalability. We compare K-means implementations in SQL and C++ with respect to speed and scalability and we also study the time to export data sets outside of the DBMS. Experiments show that SQL overhead is significant for small data sets, but relatively low for large data sets, whereas export times become a bottleneck for C++.

Recursion represents an important addition to the SQL language. This work focuses on the optimization of linear recursive queries in SQL. To provide an abstract framework for discussion, we focus on computing the transitive closure of a graph. Three optimizations are studied: (1) Early evaluation of row selection conditions. (2) Eliminating duplicate rows in intermediate tables. (3) Defining an enhanced index to accelerate join computation. Optimizations are evaluated on two types of graphs: binary trees and sparse graphs. Binary trees represent an ideal graph with no cycles and a linear number of edges. Sparse graphs represent an average case with some cycles and a linear number of edges. In general, the proposed optimizations produce a significant reduction in the evaluation time of recursive queries.

Using SQL has not been considered an efficient and feasible way to implement data mining algorithms. Although this is true for many data mining, machine learning and statistical algorithms, this work shows it is feasible to get an efficient SQL implementation of the well-known K-means clustering algorithm that can work on top of a relational DBMS. The article emphasizes both correctness and performance. From a correctness point of view the article explains how to compute Euclidean distance, nearest-cluster queries and updating clustering results in SQL. From a performance point of view it is explained how to cluster large data sets defining and indexing tables to store and retrieve intermediate and final results, optimizing and avoiding joins, optimizing and simplifying clustering aggregations, and taking advantage of sufficient statistics. Experiments evaluate scalability with synthetic data sets varying size and dimensionality. The proposed K-means implementation can cluster large data sets and exhibits linear scalability.

Existing SQL aggregate functions present important limitations to compute percentages. This article proposes two SQL aggregate functions to compute percentages addressing such limitations. The first function returns one row for each percentage in vertical form like standard SQL aggregations. The second function returns each set of percentages adding 100% on the same row in horizontal form. These novel aggregate functions are used as a framework to introduce the concept of percentage queries and to generate efficient SQL code. Experiments study different percentage query optimization strategies and compare evaluation time of percentage queries taking advantage of our proposed aggregations against queries using available OLAP extensions. The proposed percentage aggregations are easy to use, have wide applicability and can be efficiently evaluated.

K-means is one of the most popular clustering algorithms. We introduce an efficient disk-based implementation of K-means. The proposed algorithm is designed to work inside a relational database management system. It can cluster large data sets having very high dimensionality. In general, it only requires three scans over the data set. It is optimized to perform heavy disk I/O and its memory requirements are low. Its parameters are easy to set. An extensive experimental section evaluates quality of results and performance. The proposed algorithm is compared against the Standard K-means algorithm as well as the Scalable K-means algorithm.

Clustering is a fundamental Data Mining technique. This article presents an improved EM algorithm to cluster large data sets having high dimensionality, noise and zero variance problems. The algorithm incorporates improvements to increase the quality of solutions and speed. In general the algorithm can find a good clustering solution in 3 scans over the data set. Alternatively, it can be run until it converges. The algorithm has a few parameters that are easy to set and have defaults for most cases. The proposed algorithm is compared against the standard EM algorithm and the On-Line EM algorithm.

This work describes our experiences in discovering association rules in medical data to predict heart disease. We focus on two aspects of this work: mapping medical data to a transaction format suitable for mining association rules, and identifying useful constraints. Based on these aspects we introduce an improved algorithm to discover constrained association rules. We present an experimental section explaining several interesting discovered rules.

Clustering is a data mining problem that has received significant attention by the database community. Data set size, dimensionality and sparsity have been identified as aspects that make clustering more difficult. The article introduces a fast algorithm to cluster large binary data sets where data points have high dimensionality and most of their coordinates are zero. This is the case with basket data transactions containing items, that can be represented as sparse binary vectors with very high dimensionality. An experimental section shows performance, advantages and limitations of the proposed approach.

Clustering is one of the most important tasks performed in Data Mining applications. This paper presents an efficient SQL implementation of the EM algorithm to perform clustering in very large databases. Our version can effectively handle high dimensional data, a high number of clusters and more importantly, a very large number of data records. We present three strategies to implement EM in SQL: horizontal, vertical and a hybrid one. We expect this work to be useful for data mining programmers and users who want to cluster large data sets inside a relational DBMS.