19 votes

Is there a relationship between relational algebra/calculus and category theory?

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, ...
user avatar
9 votes
Accepted

What are the major research issues in distributed transactions?

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 ...
user avatar
7 votes
Accepted

Improving Bloom filter - can we distinguish elements of a database using less than 2.33275 bits/element?

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 ...
user avatar
  • 11k
6 votes
Accepted

How can I formalize key value stores with set theory?

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 ...
user avatar
  • 26.6k
5 votes
Accepted

In external memory, is grouping equal elements easier than sorting?

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 ...
user avatar
4 votes
Accepted

What is the impact of encodings of sparse structures on the complexity of the model checking problem?

I don't know of any natural logic, but the following is in any case a logic for which the combined complexity of the model-checking problem is different for matrix and list encodings. First, we know ...
user avatar
4 votes
Accepted

What is the computational complexity of Acyclic Joins?

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. ...
user avatar
  • 1,855
4 votes
Accepted

Complexity of Acyclic Hypergraph Isomorphism

To complete the answer by Holf, it is claimed here DAM 145(3) that isomorphism is GI-complete in $\beta$-acyclic hypergraphs.
user avatar
  • 1,026
4 votes

Why do relational databases work at all, given the theoretical exponential complexity of answer finding (in the size of the query)?

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 ...
user avatar
  • 141
4 votes

What is First-Order Rewritable (and FO-Query)?

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: ...
user avatar
  • 464
4 votes

Improving Bloom filter - can we distinguish elements of a database using less than 2.33275 bits/element?

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 ...
user avatar
  • 11k
3 votes
Accepted

Are there (N-1)! ways to order joins?

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

Lower bounds and impossibility results for distributed transactions

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 ...
user avatar
  • 2,319
3 votes
Accepted

What does the category of RDF models look like in Institution Theory?

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 ...
user avatar
3 votes

Minimum number of columns making each row different

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 ...
user avatar
  • 5,712
2 votes

On motivation towards study of width parameters beyond treewidth

It is not hard to see that if a class of queries has arity bounded by $a$ and hypertree width bouded by $k$, then it will also have treewidth bounded by $a\cdot k$. Indeed, any bag in a hypertree ...
user avatar
  • 1,855
2 votes

First order expression for functional dependency

[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. ...
user avatar
  • 121
1 vote
Accepted

What are the most fundamental metrics (criterions) of database performance?

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 ...
user avatar
  • 8,651
1 vote

Is there a set theoretic way to look at SQL?

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 ...
user avatar
1 vote

Is there a set theoretic way to look at SQL?

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 ...
user avatar
1 vote

What is First-Order Rewritable (and FO-Query)?

As a complement to Janoma's answer above: it's 'very good'--- from the point of view of implementation --- because given a FO-rewritable language, we can use the powerful engines (for evaluating ...
user avatar
1 vote
Accepted

Concurrent transactions satisfying "serializability" but not "snapshot isolation"

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 ...
user avatar
  • 2,319
1 vote

Representation of procedural knowledge

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

Representation of procedural knowledge

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. ...
user avatar
  • 584

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