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 ...


12

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 ...


7

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: ...


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

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

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

1.56 bits per key is now possible using "RecSplit: Minimal Perfect Hashing via Recursive Splitting" by Emmanuel Esposito, Thomas Mueller Graf, and Sebastiano Vigna. It is quite expensive: 1,700 times more expensive than 1.79 bits per key!


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

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


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

(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

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

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

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 ...


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

There's a lot to unpack here and I don't know about Goguen's institutions. But perhaps I can give a partial answer to your question. Let's start with "simple interpretations" of RDF, as defined by the spec, forgetting about richer languages like RDFS or OWL. If we ignore IRIs and literals, as in the first part of your question, then an RDF model is a simple ...


1

A co-Relational Model of Data for Large Shared Data Banks by Erik Meijer and Gavin Bierman, http://queue.acm.org/detail.cfm?id=1961297 Good article describing SQL and No-SQL databases as categorical duals.


1

It is common wisdom that database field is firmly grounded in the two math disciplines: predicate logic and set theory. However, this is very fuzzy observation, and reality is more subtle. The structure of the basic building block - relation - is described in set language, but that's about it. This is not really very insightful, because the whole ...


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