16

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


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


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

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

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


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


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

It essentially depends on what you mean by "evaluating this join". If you want to compute the whole table, then the $2^n$ blow-up is unavoidable, just because you need to store all these values. However, given an acyclic query, you can compute the "semi-join" in time linear in the size of the data and linear in the size of the query. The semi-join is the ...


4

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


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!


3

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


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

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


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


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


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

[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

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

Some of the performance-related things you can objectively compare between different databases: IO complexity and computational complexity of different queries. E.g. there are different ways to do joins, sorting, different kinds of indices (including "no indices"), with objectively different asymptotic complexity. There are also column-oriented and row-...


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


1

Answer my own question: I am not sure with the ideas below. Both comments and answers from experts are highly appreciated. Any references are also welcome. I think the confusion arises from the fact that the two definitions of serializability ($\textrm{SR}$, for short) adopted in [Lin et al@TODS'2009] and [Berenson et al@MSR-TR'1995] are different. The SR ...


1

John Sowa (probably the foremost expert on knowledge representation) gives a thorough discussion of the subject here: Sowa


1

You are probably speaking about something like a process ontology. Lately, that research has focused (moved?) on semantic workflows, e.g. to model processes in science, related with reproducibility. Similarly, we can also find the application of ontologies to business processes. For more classical (lower level?) approaches, you may be interested in the ...


1

There is a distinction between LSM-Tree and Log-Structured Storage: Log-Structured Merge Tree (LevelDB, SQLite4, Apache Cassandra, and others). Log-Structured Storage (Berkeley DB Java Edition)


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