The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Tag Info

14

You ask why database aggregations have monoidal structure. Say we want to combine data values $a$ and $b$, but want to keep things general -- these may be integers, strings, floating point numbers, vectors, matrices, probability distributions, sets, or anything else we want to store and manipulate. So we denote the "aggregation" of $a$ and $b$ by $a.b$. ...

12

There isn't really a single formalization of the kind of thing you are asking. There are many, many aspects to truth, trust, lies, and fallible reasoning, and this leads to an enormous variety of logical formalisms, each handling different aspects of this problem. If you want to account for uncertainty about your hypotheses, the traditional route is via ...

11

Categorical approaches to query languages is a bit of a niche interest, but I think it's a very interesting niche! Two of the key figures in this area are Peter Buneman and Torsten Grust. Obviously, they didn't do all the work, but if you start with their papers and trace out the citation graph, you'll get pretty good coverage of the area. The central ...

9

There are many research areas both in the theory and practice of distributed databases. One of the main practical challenges is that of implementing efficient concurrency control mechanisms for distributed and geo-replicated databases. In order to execute transactions efficiently, such mechanisms can provide weaker guarantees than serialisability, which ...

9

In db query area arguably Provenance Semiring enjoyed the most attention recently. The "provenance" adjective is just marketing connecting it to a large body of research. Nevertheless the idea that one may have much more elegant mathematical foundation for database query languages is compelling. My personal view is that semiring perspective (which works ...

6

I would expect that the empty relation corresponds to the always-zero probability distribution. Disjoint union corresponds to addition of probability distributions. However, standard union would be more complicated. I don't really know if there is some way to encode the standard union for probability distributions. (I have heard people say that ...

6

It depends on how the query is implemented. If we are doing dictionary lookups and we stored the values using cuckoo hashing for example, then each lookup is $O(1)$ time, and doing the lookup in a batch can't possibly improve that run-time. (It takes that long just to list the values). On the other hand, if we use a tree based data structure, we may be ...

6

There does not seem to be a general algorithm. Checking whether two Datalog programs are equivalent (in the sense of producing the same output database for every possible input database) is undecidable. The containment problem, of checking whether one Datalog program always produces all the tuples of the other (plus possibly some others), is also ...

6

$n^2$ processors can compare all ${n \choose 2}$ possibilities in constant depth, so yes it's in NC.

6

Here are some hints: Select: consider the relation $\{(1),(2)\}$. Project: number of columns can't decrease. Cross product: number of columns can't increase. Union: consider the database $\{(1)\},\{(2)\}$ with identical attributes. Difference: similar to union.

6

You did not say why you want a formalization, but presumably you want to do things with it, for instance prove properties of dictionaries and operations on them. In fact, your question can be understood in two ways: you want a mathematical description of dictionaries, or you want a computer formalization of dictionaries. For a computer formalization have a ...

5

From page 52 of Leonid Libkin's Elements of Finite Model Theory textbook: Since we know that graph connectivity is not Hanf-local and transitive closure is not Gaifman-local, we immediately obtain, without using games, that these queries are not FO-definable. SQL and (original) SPARQL are based on fragments of first-order logic, without fixed-point or ...

5

2.09 bits per element is practically achievable. See http://cmph.sourceforge.net/: "[Compress, Hash, Displace] can generate MPHFs that can be stored in approximately 2.07 bits per key." 1.44 bits per element is optimal. See "Hash, displace, and compress" "Improved Bounds For Covering Complete Uniform Hypergraphs" Data Structures and Algorithms , Vol. 1: ...

5

Even testing whether $n$ elements are distinct is known to require $\Omega(n \log n)$ time on a model with some pretty reasonable restrictions. See, for example, Anna Lubiw, András Rácz: A Lower Bound for the Integer Element Distinctness Problem. Inf. Comput. 94(1): 83-92 (1991).

4

The biggest "advance" in relational databases has been the cleaving apart of the monolithic RDBMS model into discrete components, that are then put together in novel ways. These include data stores that have weak consistency (Google Percolator), column stores (NoSQL), and graph databases. The ideas are not new, but the different ways of combining the ...

4

If you're interested in writing a purely functional database, you should probably check out Phil Trinder's PhD thesis which was on this very subject. He has a chapter on the use of B-Trees.

4

Here's a more reality-concerned version of tigreen's answer from the point of a person who actually makes heavy use of (relational) databases: The whole point and complexity of their application is to structure them in a way they'd require as little amount of joins for each and every ever-needed query as possible and that's why they actually Do Work. In ...

4

There are canonical forms, but there are not unique canonical forms. Roughly, the idea is to use observe that sets form a monad and use the equational theory of Moggi's monadic metalanguage as a well-behaved IR for optimizing queries. See Torsten Grust's PhD thesis, Comprehending Queries. More recently, the Ferry Project has been investigating integrating ...

4

To complete the answer by Holf, it is claimed here DAM 145(3) that isomorphism is GI-complete in $\beta$-acyclic hypergraphs.

3

The arXiv paper "Non-Monotonic Snapshot Isolation" [1] proves several impossibility theorems demonstrating that SI (Snapshot Isolation) and GPR (Genuine Partial Replication) are incompatible. To this end, it first decomposes SI into four properties: Decomposition theorem: $SI = ACA \cap SCONS \cap MON \cap WCF$ where, $ACA$: avoiding cascading aborts;...

3

(not enough rep for comment) Can you tell us more about the data streams? I am a roboticist, and I often deal with sensors which are outputting data streams at different rates. Specifically, can you please elaborate on the following: do the data streams have the same modality? (eg, are they all telling you the velocity of something, or is one telling you ...

3

Relational Lattice is axiomatic foundation for Relational Algebra. Predictably, query transformations reduce to equational reasoning in that axiom system. Here are examples: Push-select-via-project Renaming Many others like commutativity and associativity of [relational] join operation, or permutting selection via join are trivial in the sense that they ...

3

Your question is mixing two somewhat orthogonal interpretations of the term "Availability". The "reliability theory"/"engineering" interpretation, where availability is basically the ratio of time the system is not failed. The "distributed computing" interpretation, which is centered around the idea that "every request received by a non-failing node ...

3

Part of the answer is in your question: if your language is FO-rewritable, query answering is in $\textrm{AC}_0$ in data complexity, which is almost as good as it gets. However, keep in mind that you have to pay the cost of computing $Q_\Sigma$, which might be expensive, though you have to do it only once. Other good thing is that, for a FO-rewritable ...

3

I guess $((AB)(CD))$ is actually two ways, because you could do either $(AB)$ or $(CD)$ first.

3

Your problem is known to be NP-hard. See for instance Vincent Froese, René van Bevern, Rolf Niedermeier, Manuel Sorge: "Exploiting hidden structure in selecting dimensions that distinguish vectors." Journal of Computer and System Sciences 82, pp 521-535 (2016).

2

[in the article] there seems to be a confusion between dependency and functional dependency. The article is using "dependency" in the sense of 'Dependence Logic' here or here. As @Mark R points out. Specifically it's talking about the 'branching or Henkin quantifier'. Yes those are nothing to do with database theory Functional Dependencies. (They might be a ...

2

Here is another attempt at a more comprehensive answer. Your question already contains the formal definition of FO-rewritability, which at its core says that you can reduce a query answering problem: The problem $D\cup\Sigma\models Q$ is being reduced to a problem $D\models Q_\Sigma$. Several noteworthy things are happening here. The original problem is ...

2

Operations on a database are divided into DDL and DML. DDL are operations that alter the structure of the database. This includes creating/dropping tables, constraints, indexes, packages, views, dblinks, adding or removing columns to a table, changing object names and so on. DML are the operations that alter the data stored in the database. This includes ...

2

The "Availability" in the CAP Theorem can be regarded as a classic liveness property: every request eventually receives a response. It is interpreted in Perspectives on the CAP Theorem in the context of distributed computing. Obviously, a fast response is better than a slow response, but for the purpose of CAP, it turns out that even requiring an ...

Only top voted, non community-wiki answers of a minimum length are eligible