In this tutorial, we will survey known results on the complexity of conjunctive query evaluation in different settings, ranging from Boolean queries over counting to more complex models like enumeration and direct access. A particular focus will be on showing how different relatively recent hypotheses from complexity theory connect to query answering and allow showing that known algorithms in several cases can likely not be improved.
Two-phase locking (2PL) is a consolidated policy commonly adopted by Database Management Systems to enforce serializability of a schedule. While the policy is well understood, both in its standard and in the strict version, automatically deriving a suitable tabular/graphical analysis of schedules with respect to 2PL is far from trivial, and requires several technicalities that do not straightforwardly translate to visual cues. In this paper, we delve into the details of the development of a tool for 2PL analysis.
Recent advances in computing have changed not only the nature of mathematical computation, but mathematical proof and inquiry itself. While artificial intelligence and formalized mathematics have been the major topics of this conversation, this paper explores another class of tools for advancing mathematics research: databases of mathematical objects that enable semantic search. In addition to defining and exploring examples of these tools, we illustrate a particular line of research that was inspired and enabled by one such database.
In PODS'21, Hu presented an algorithm in the massively parallel computation (MPC) model that processes any acyclic join with an asymptotically optimal load. In this paper, we present an alternative analysis of her algorithm. The novelty of our analysis is in the revelation of a new mathematical structure -- which we name "canonical edge cover" -- for acyclic hypergraphs. We prove non-trivial properties for canonical edge covers that offer us a graph-theoretic perspective about why Hu's algorithm works.
We study consistent query answering in relational databases. We consider an expressive class of schema constraints that generalizes both tuple-generating dependencies and equality-generating dependencies. We establish the complexity of consistent query answering and repair checking under tuple-deletion semantics for different fragments of the above constraint language. In particular, we identify new subclasses of constraints in which the above problems are tractable or even first-order rewritable.
A set of preferred records can be obtained from a large database in a multi-criteria setting using various computational methods which either depend on the concept of dominance or on the concept of utility or scoring function based on the attributes of the database record. A skyline approach relies on the dominance relationship between different data points to discover interesting data from a huge database. On the other hand, ranking queries make use of specific scoring functions to rank tuples in a database. An experimental evaluation of datasets can provides us with information on the effectiveness of each of these methods.
Top-$k$ queries and skylines are the two most common approaches to finding the most interesting entries in a homogeneous multi-dimensional dataset. However, both of these strategies have some shortcomings. Top-$k$ queries are very challenging to specify precisely and skylines are not customizable to specific scenarios, on top of having unpredictable output cardinalities. We describe some alternative methods aimed at addressing the shortcomings of top-$k$ queries and skylines and compare all approaches to illustrate which of the desired properties each of them possesses.
This paper presents TXSC, a framework that provides smart contract developers with transaction primitives. These primitives allow developers to write smart contracts without the need to reason about the anomalies that can arise due to concurrent smart contract function executions.
We present a new approach to the logical design of relational databases, based on strategic port graph rewriting. We show how to model relational schemata as attributed port graphs and provide port graph rewriting rules to perform computations on functional dependencies. Using these rules we present a strategic graph program to find the transitive closure of a set of functional dependencies. This program is sound, complete and terminating, assuming that there are no cyclical dependencies in the schema.
The aim of this article is to present an overview of the existing biomedical data warehouses and to discuss the issues and future trends in this area. We illustrate this topic by presenting the design of an innovative, complex data warehouse for personal, anticipative medicine.
The aim of this article is to present an overview of the major families of state-of-the-art data processing benchmarks, namely transaction processing benchmarks and decision support benchmarks. We also address the newer trends in cloud benchmarking. Finally, we discuss the issues, tradeoffs and future trends for data processing benchmarks.
In this extended abstract we describe, mainly by examples, the main elements of the Ontological Multidimensional Data Model, which considerably extends a relational reconstruction of the multidimensional data model proposed by Hurtado and Mendelzon by means of tuple-generating dependencies, equality-generating dependencies, and negative constraints as found in Datalog+-. We briefly mention some good computational properties of the model.
Integrity checking is a crucial issue, as databases change their instance all the time and therefore need to be checked continuously and rapidly. Decades of research have produced a plethora of methods for checking integrity constraints of a database in an incremental manner. However, not much has been said about when to check integrity. In this paper, we study the differences and similarities between checking integrity before an update (a.k.a. pre-test) or after (a.k.a. post-test) in order to assess the respective convenience and properties.
The explosion of available data along with the need to integrate and utilize that data has led to a pressing interest in data integration techniques. In terms of Semantic Web technologies, Ontology Alignment is a key step in the process of integrating heterogeneous knowledge bases. In this paper, we present the Edge Confidence technique, a modification and improvement over the popular Similarity Flooding technique for Ontology Alignment.
We extend RDF with the ability to represent property values that exist, but are unknown or partially known, using constraints. Following ideas from the incomplete information literature, we develop a semantics for this extension of RDF, called RDFi, and study SPARQL query evaluation in this framework.
For data integration in information ecosystems, semantic heterogeneity is a known difficulty. In this paper, we propose Shadow Theory as the philosophical foundation to address this issue. It is based on the notion of shadows in Plato's Allegory of the Cave. What we can observe are just shadows, and meanings of shadows are mental entities that only exist in viewers' cognitive structures. With enterprise customer data integration example, we proposed six design principles and algebra to support required operations.