656 research outputs found
Evaluation Trade-Offs for Acyclic Conjunctive Queries
No full textWe consider the evaluation of acyclic conjunctive queries, where the evaluation time is decomposed into preprocessing time and enumeration delay. In a seminal paper at CSL'07, Bagan, Durand, and Grandjean showed that acyclic queries can be evaluated with linear preprocessing time and linear enumeration delay. If the query is free-connex, the enumeration delay becomes constant. Further prior work showed that constant enumeration delay can be achieved for arbitrary acyclic conjunctive queries at the expense of a preprocessing time that is characterised by the fractional hypertree width.
We introduce an approach that exposes a trade-off between preprocessing time and enumeration delay for acyclic conjunctive queries. The aforementioned prior works represent extremes in this trade-off space. Yet our approach also allows for the enumeration delay and the preprocessing time between these extremes, in particular the delay may lie between constant and linear time.
Our approach decomposes the given query into subqueries and achieves for each subquery a trade-off that depends on a parameter controlling the times for preprocessing and enumeration. The complexity of the query is given by the Pareto optimal points of a bi-objective optimisation program whose inputs are possible query decompositions and parameter values
Conjunctive Queries with Free Access Patterns Under Updates
No full textWe study the problem of answering conjunctive queries with free access patterns under updates. A free access pattern is a partition of the free variables of the query into input and output. The query returns tuples over the output variables given a tuple of values over the input variables.
We introduce a fully dynamic evaluation approach for such queries. We also give a syntactic characterisation of those queries that admit constant time per single-tuple update and whose output tuples can be enumerated with constant delay given an input tuple. Finally, we chart the complexity trade-off between the preprocessing time, update time and enumeration delay for such queries. For a class of queries, our approach achieves optimal, albeit non-constant, update time and delay. Their optimality is predicated on the Online Matrix-Vector Multiplication conjecture. Our results recover prior work on the dynamic evaluation of conjunctive queries without access patterns
Tractable Conjunctive Queries over Static and Dynamic Relations
No full textWe investigate the evaluation of conjunctive queries over static and dynamic relations. While static relations are given as input and do not change, dynamic relations are subject to inserts and deletes.
We characterise syntactically three classes of queries that admit constant update time and constant enumeration delay. We call such queries tractable. Depending on the class, the preprocessing time is linear, polynomial, or exponential (under data complexity, so the query size is constant).
To decide whether a query is tractable, it does not suffice to analyse separately the sub-queries over the static relations and over the dynamic relations, respectively. Instead, we need to take the interaction between the static and the dynamic relations into account. Even when the sub-query over the dynamic relations is not tractable, the overall query can become tractable if the dynamic relations are sufficiently constrained by the static ones
Towards analytics over dirty databases
No full textIn today's data-driven world, organizations increasingly rely on large and complex datasets to drive decision-making, build predictive models, and optimize operations. From e-commerce companies leveraging customer behavior data to improve marketing strategies, to financial institutions analyzing transactions for fraud detection, the demand for efficient, scalable, and seamless data processing is critical. However, real-world data is often incomplete, inconsistent, or erroneous, which undermines the accuracy and reliability of the insights drawn from it. Traditional workflows require moving data out of database systems into external analytical tools for machine learning, data cleaning, and query answering tasks, introducing significant inefficiencies and creating bottlenecks. This thesis presents integrated solutions that enable these operations to be performed directly within the database, addressing three key problems in modern database systems: (1) inefficiency in executing machine learning tasks, (2) inability to handle missing data effectively, and (3) limitations in querying inconsistent databases.
First, we address the challenge of efficiently training machine learning models over relational data. Most data resides in databases, yet current machine learning systems typically require exporting data into external tools, leading to excessive data transfer and redundant computations. To overcome these inefficiencies, we propose an in-database machine learning library implemented on PostgreSQL and DuckDB. Our approach rewrites popular machine learning algorithms to run directly within the database, leveraging the relational data structure. By training models over aggregate values computed from normalized tables, we eliminate the need for expensive joins and preprocessing, achieving 10 to 100-fold faster model training compared to state-of-the-art solutions like MADLib. Additionally, our library allows multiple models to be constructed using the same set of aggregate computations, further optimizing the learning process.
Second, missing data is a pervasive issue in real-world datasets, often necessitating the use of imputation techniques to fill in gaps before analysis or model training can proceed. External tools for imputation, such as those implementing the Multiple Imputation by Chained Equations (MICE) method, typically require data export and preprocessing, adding complexity to the workflow. We introduce an in-database imputation framework that integrates MICE directly into database systems, allowing it to operate over normalized data. By re-engineering the MICE algorithm to share computations across iterations and optimize for fast access to frequently used data, we significantly reduce runtime. Our solution, implemented in both PostgreSQL and DuckDB, outperforms traditional methods, providing a more efficient and scalable way to handle missing data without leaving the database environment.
Third, we tackle the problem of query answering over inconsistent databases -- a critical challenge for organizations that rely on accurate query results despite data inconsistencies. Conventional methods often involve data cleaning to restore consistency, but this can be impractical in real-time environments or where altering the original data is not feasible. To address this, we develop a method based on Consistent Query Answering (CQA), which allows queries to be evaluated directly over inconsistent data. We model the concept of ``minimal repairs'' -- smallest changes that restore consistency -- as a logical formula and use model counting techniques to determine the number of possible repairs. Furthermore, by optimizing the size of the logical formula, we achieve up to a 1000-fold reduction in computational complexity. To efficiently compute the number of repairs supporting each query answer, we introduce two Monte Carlo approximation algorithms that leverage the compiled logical formula. These algorithms provide theoretical guarantees for approximation accuracy while maintaining practical efficiency, enabling the execution of CQA over large datasets with multiple functional dependency violations.
In conclusion, this thesis presents a comprehensive set of in-database solutions designed to overcome inefficiencies in machine learning, data imputation, and query evaluation processes, particularly in the presence of incomplete or inconsistent data. By integrating these tasks directly into modern relational databases, our approach not only streamlines workflows but also significantly improves performance. Our contributions include a high-performance machine learning library, a scalable imputation technique for handling missing data, and a robust framework for consistent query answering over erroneous databases. Collectively, these innovations represent a significant advancement toward more efficient, reliable, and scalable data management solutions
Counting Triangles under Updates in Worst-Case Optimal Time
No full textWe consider the problem of incrementally maintaining the triangle count query under single-tuple updates to the input relations. We introduce an approach that exhibits a space-time tradeoff such that the space-time product is quadratic in the size of the input database and the update time can be as low as the square root of this size. This lowest update time is worst-case optimal conditioned on the Online Matrix-Vector Multiplication conjecture. The classical and factorized incremental view maintenance approaches are recovered as special cases of our approach within the space-time tradeoff. In particular, they require linear-time maintenance under updates, which is suboptimal. Our approach can also count all triangles in a static database in the worst-case optimal time needed for enumerating them
Developing a Generic Agent-Based Model to Explore Servicising Policy
No full textContinuous economic growth, ignoring the incidental recession, is currently still coupled with increases in the use of resources and generation of wastes. The European Commission (EC) is looking for ways to achieve absolute decoupling between economic growth and environmental impacts. A shift from product-based to function-based production and consumption, known as `servicising' of the economy, has the potential to contribute to absolute decoupling. The EC is therefore looking for policy measures on all political levels that may stimulate a servicising shift and thereby contribute to absolute decoupling. In this thesis, I propose a generic agent-based model to inform policy towards absolute decoupling, with a focus on the role of servicising. The model captures interactions between selling and buying `agents' and can be parametrised for many different specific markets. It integrates rational and non-rational considerations, decision making on multiple levels of both producers and consumers, and resulting material flows and impacts, all in a generic way. Also, the model features sophisticated market research as a novel basis for the decision making of agents in an artificial market. The model was developed following the methodology for developing an agent-based model proposed by Van Dam, Nikolic and Lukszo \citep{Dam2012}. A substantial part of this thesis is reserved for a reflection on the methodology. The main conclusion from that part is that although the methodology provides valuable structure to help new modellers through model development, the recommended techniques and practices are mostly suitable for relatively small, domain-specific models. Additional practices are recommended in order to successfully build large and generic models. The proposed model is suitable for the three planned case studies in the pan-European SPREE project, of which the generic model development constituted a central part. The concluding sections of this thesis provide suggestions for future extensions of the model, including the inclusion of social networks, spatial explicitness and chain-level interactions.SEPAMESSTechnology, Policy and Managemen
The Incorporation of International Law in the Swiss Legal System
No full textThe paper examines the incorporation of international law into Swiss legal system. Under a realistic approach, founding its roots in the Italian School of International Law, the problematic and uniqueness of Swiss legal system is explained under an alternative dimension. The intention of the author is that of (re)conceptualizing the methodology of interpretation of relationship between international law and internal law through a realistic analyze of the phenomenon, based on the social origin and nature of international law. The principal accent is given to the necessary distinction between relationship and mechanisms of adaptation. Bringing the scientific debate on social binaries might help scholars and commentators to better identify the real object and purpose of the realistic approach
Compilation and code generation for efficient data science
No full textIn today's data-driven world, data science plays an important role in benefiting from big data, enabling smart decision-making, and helping innovative acts across industries. The fact that data science creates tangible value for businesses and organizations has resulted in an increasing demand for efficient data science tools.
Python has become the main tool and language of choice for data scientists. It is mostly because of its simplicity and rich ecosystem of libraries such as Pandas, NumPy, and TensorFlow. However, Python's user-friendliness comes with the costs of inefficiency and lack of scalability. This limitation relates to the interpreted nature of this language and also the way its libraries are developed. While previous efforts towards more scalable data science in Python have explored avenues such as fine-tuned low-level kernels, auto-parallelization, and compilation to other languages, their approaches missed some enhancement opportunities or showed only limited coverage on the diverse spectrum of data science workloads.
In this thesis, we adopt a compilation-centric approach to address the challenges of scalable Python data science and introduce a framework comprising different compilation pipelines for the same goal. This framework aims to enhance the efficiency of data science workloads by translating them into SQL/C++. After these transformations, the workloads can be executed by a conventional query engine (RDBMS), with proven optimization and computation power, or a tailored query engine that is crafted for the given workloads. In the case of specialized query engines, we additionally propose a design for optimizing these engines that exploit batch-processing techniques to accelerate the execution and improve the overall performance. We showcase the efficacy of the proposed framework through comprehensive micro and end-to-end benchmarks.
By making data science processing more efficient, our framework not only accelerates data analytics and decision-making but also contributes to sustainable computing practices by reducing the computing resource requirements
Efficient structured tensor algebra by compilation and compression
No full textTensor algebra is fundamental to data-intensive computational workloads across domains such as machine learning, scientific computing, and signal processing. As data complexity increases, researchers face a trade-off between the highly specialized optimizations of dense tensor algebra frameworks and the efficiency of structure-aware algorithms in sparse tensor algebra. On the one hand, extensive research has been conducted on dense tensor algebra, where computations involve tensors without explicit structure. Known memory access patterns for the computation at compile time allow compilers and high-performance engineers to heavily tune the kernels by leveraging optimizations such as parallelization, vectorization, and tiling. On the other hand, many real-world applications require computations over tensors with sparsity patterns and inherent structure. Many lines of research have been dedicated to sparse tensor algebra, to efficiently exploit the memory structure, enhance algorithmic complexity, and improve computational performance.
Many real-world applications involve tensors with well-defined structures (e.g., diagonal, upper-triangular, Toeplitz-like), often known at compile time. Exploiting these structures can drastically reduce computational costs. While prior efforts have leveraged tensor structure to develop specialized and optimized kernels, they suffer from three major limitations: 1) they are restricted to a small set of predefined structures, 2) they cannot be composed or propagated through computation, and 3) they do not necessarily provide the best memory layout for a given computation.
This dissertation aims to leverage the benefits of both dense and sparse worlds and create an infrastructure to bridge the gap by leveraging the structure. This will lead to overcoming the 3 aforementioned limitations and solving the dilemma by introducing an end-to-end pipeline that transforms structured tensor algebra expressions to specialised low-level code through 1) Structured Tensor Unified Representation (\stur{}) language, a language with structure as its first-class citizens, 2) structure inference and compilation, and 3) automatic data layout compression.
This dissertation presents the three major components of this pipeline. The first component which is the backbone of the infrastructure is Structured Tensor Unified Representation (\stur{}). \stur{} is a domain-specific language that represents tensor algebra computation using generalised Einstein summation (einsum). \stur{} treats tensor structure as a first-class citizen using a unique set and redundancy map, making structured tensor algebra computation both expressible and extensible beyond a fixed set of predefined structures.
The second component, \structtensor{}, is a framework that automatically infers and propagates the structure of input tensors throughout the entire computation by applying a set of program reasoning rules. \structtensor{} uses \stur{} as the intermediate language to reason about sparsity and redundancy patterns. This reasoning limits the iteration space of the tensor computation to non-zero and non-repetitive values. Hence, the computation is done more efficiently.
The densely assembled tensor algebra compiler (\dastac{}) is the final component of this pipeline. \dastac{} is built on top of \structtensor{} and uses \stur{} as an intermediate language similarly. \dastac{} automatically reorders the elements and compresses the underlying data layout of the structured tensors based on the iteration space and the structure throughout the computation, leading to more memory efficiency. Polyhedral optimizations and parallelisation are also enabled through ISL and MLIR in \dastac{}.
Through extensive benchmarks and evaluation, it is demonstrated that this pipeline achieves orders of magnitude speed-up compared to sparse (e.g., TACO) and dense (e.g., TensorFlow and PyTorch) tensor algebra frameworks when compile time structure is available. It is also presented that in many real-world applications, the system outperforms hand-tuned specialised expert code (e.g., Intel MKL) by up to 2 orders of magnitude in both single- and multi-threaded scenarios while taking up to 5x less memory.
This work establishes an infrastructure that bridges the gap between dense and sparse tensor algebra by bringing the best aspects together. It significantly reduces the computational cost and memory requirements for tensor algebra computation while achieving state-of-the-art performance. This pipeline also mitigates the development overhead for implementing new kernels or composing them by providing a compilation pipeline and a code generator that produces highly optimized code
Recommended from our members
System Design of Cooperative Wireless Networks
No full textWith the prediction that the number of wireless devices will reach tens of billions by 2020, wireless networks that exist today will have to be reengineered to support the increase in the number of users and the required capacity. Cooperation among terminals is envisioned as an enabling technique that can benefit from the increased number of connected devices and boost the network capacity beyond what is possible with today's network architectures, which rely on direct source-destination transmissions. While most of the work in this area focuses on designing relaying schemes that can achieve the promised capacity increase, little has been done in terms of implementing practical cooperative systems. To implement cooperation among terminals, a number of practical challenges need to be addressed across several layers of the communication system. This work focuses on the design aspects of physical and MAC communication layers, by suggesting low-complexity signal processing algorithms for multi- device cooperation and designing digital baseband hardware that showcases cooperation between two wireless devices.We use the quantize-map-and-forward (QMF) relaying scheme, which has been shown to have good theoretical performance with multiple relays. System design of a cooperative communication link with half-duplex QMF relays is presented in three steps. First, we perform a theoretical analysis of the achievable rate and propose a local relay scheduling algorithm that performs close to the optimal relay scheduling algorithm. This local scheduling algorithm, as well as the system design approach in general, is based on the premise that relay terminals can be oblivious to other relays in the network. We show that spectral efficiency scaling with the number of relays achieved with this approach is close to optimal for both slow and fast- fading channel environments. The performance of a physical layer system design procedure for a QMF link is demonstrated by an example in which the spectral efficiency of a direct link is doubled by cooperating with three relays close to the source, as predicted by the theoretical analysis. Finally, we design the main baseband blocks for the three cooperating terminals in hardware and implement them on FPGAs. We show that the complexity of the cooperative receiver's baseband increases by 40% compared to a direct-link receiver
- …
