475 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
Traffic simulation datasets supporting a Digital Twin of Milos Island road network
No full textThis dataset contains traffic simulation inputs and outputs used to develop and validate a Digital Twin of the road network of Milos Island, Greece. The data support scenario testing of congestion mitigation and sustainability interventions using SUMO, including traffic counts, synthetic demand, route files, and simulation-derived performance indicators such as travel time loss, fuel consumption, and CO₂ emissions© the author</p
Historical fiction and post-modernism. View of the older Czech history in the works of Milos Urban
No full text(in English) The aim of this work is especially the post-modern art, its symbols and manifestations. The main area of this research is post-modern literature and effort to concretise post-modern symbols in literature. This work is also trying show the influence of post-modern on historiographical approach. The solution of this work goes from general manifestations of post-modern to particular manifestation in post-modern literature. The main source represented the set of monographs about this theme. The significantly part is about publications of Czech author Milos Urban, and especially the interview of author this thesis with him. On the particular symbols was able to improved, that Milos Urban really writing literature with influence of post-modernism. The post-modern symbols in literature and also the influence of post-modern on historiography were managed to described and instanced
Bourgeois Balkans: world-building in Belgrade and Sofia 1830-1912
No full textThis dissertation examines the transformation of urban life in the Balkan capitals of Belgrade and Sofia between 1830 and 1912. In the nineteenth century, mayors, planners, doctors and intellectuals envisioned a new, urban society in which progressive social transformation could emerge through a combination of political and economic institutions based on expertise. I explore the ambitions and limits of this “bourgeois world-building” through three constitutive processes: the production of space, the gendered transformation of intimate labor, and the re-calibration of state violence. With the advent of autonomous rule, the Balkan capitals were reconstructed as “European” cities through dispossession, real-estate speculation and municipal corruption. For architects, merchant capitalists, and municipal officials, the post-Ottoman city appeared as a landscape of accumulation, a vision often frustrated by its failure to materialize in full. Medical professionals and police officials envisioned the city as a space of managed, commodified intimacy, yet found limits in expanding institutional control over sex workers, domestic servants, and other working women. Activists and state actors were likewise frustrated in their attempts to create productive urban subjects through scientific policing and prison labor. Ultimately, the application of bourgeois visions was both intensive and costly, limited by the scope of elite ambitions and the struggle of those who were excluded from them.Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2018-12-01The student, Milos Jovanovic, accepted the attached license on 2016-12-02 at 13:57.The student, Milos Jovanovic, submitted this Dissertation for approval on 2016-12-02 at 13:58.This Dissertation was approved for publication on 2016-12-02 at 14:26.DSpace SAF Submission Ingestion Package generated from Vireo submission #10419 on 2017-02-28 at 14:43:05Made available in DSpace on 2017-03-01T17:02:01Z (GMT). No. of bitstreams: 2
JOVANOVIC-DISSERTATION-2016.pdf: 51651849 bytes, checksum: 84a1504bdf45a382a2a3f80764815dfc (MD5)
LICENSE.txt: 4212 bytes, checksum: 5cd1fcd6263d49f4d43815869eea9221 (MD5)
Previous issue date: 2016-12-02Embargo set by: Seth Robbins for item 98724
Lift date: 2019-03-01T17:02:22Z
Reason: Author requested closed access (OA after 2yrs) in Vireo ETD systemEmbargo set by: Seth Robbins for item 98724
Lift date: 2019-03-01T17:03:32Z
Reason: Author requested closed access (OA after 2yrs) in Vireo ETD systemEmbargo set by: Seth Robbins for item 98724
Lift date: 2019-03-01T17:05:02Z
Reason: Author requested closed access (OA after 2yrs) in Vireo ETD systemEmbargo set by: Seth Robbins for item 98724
Lift date: 2019-03-01T17:06:55Z
Reason: Author requested closed access (OA after 2yrs) in Vireo ETD systemLimited Restriction Lifted for Item 98724 on 2019-03-02T10:15:33Z
Problems of translation Milos Macourek's fairy-tales into Polish
No full textSummery This thesis deals with the issue of translation Milos Macourek's fairy tales into Polish. The starting point for the analysis is a comparison of two versions of a translation of selected texts. The author of the first one is Marie Erhardtowa, the second version is translated by Herman Grzeszczyk and Andrzej Kulikowski. The first part of the thesis is a theoretical preparation which explains the basic questions of literary translation. The main goal of the practical part of this thesis is to determine the target groups of readers, followed by an analysis of the particular translation issues.The conclusion contains a summary of findings and an assessment of individual translation in terms of adequacy
Integration and Laplace Transformation of Orthogonal Series
No full textTitle: Integration and Laplace Transformation of Orthogonal Series, Author: Milos Novotny, Location: ThodeIn the first part of this thesis the basic
properties of classical orthogonal polynomials are derived from a unified
theory. Then sufficient conditions for term-by-term integration and
Laplace transformation of Fourier expansions in terms of an orthogonal
system with respect to a weight function on a bounded or unbounded interval
are given, and successively applied to Fourier expansions in terms of the
trigonometric system, the classical orthogonal polynomials, the Haar system
and eigenfunction expansions for ordinary linear differential equations with
boundary conditions on both ends of a compact interval as well as in limit
point and limit circle cases for an infinite interval. Finally a necessary
and sufficient condition for representation of a complex function as a
Laplace interval of f ε L(0,2π) with period 2π is proved.ThesisDoctor of Philosophy (PhD
- …
