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
12 votes
Accepted

Does the first order theory of a finite structure have bounded quantifier rank?

The theory of any finite structure is model complete. In fact, it is easy to see that any formula is equivalent to an existential formula with one quantifier per each element of the structure, after ...
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
3 votes

Does the first order theory of a finite structure have bounded quantifier rank?

To make what Emil said a bit more concrete: consider the formula expressing existence of k distinct objects. That shows we need unbounded number of quantifiers. Now you have a formula with q ...
user avatar
  • 21.3k
2 votes

Complete axiomatization of relation algebras without ${}^-$ and $\top$

The equational theory of the signature $S=\{\vee,\wedge,.,\epsilon,^\smile\}$ is decidable. See this paper by Andréka and Bredikhin. The idea is to associate to every term $t$ over $S$ a graph $G_t$. ...
user avatar
  • 161
1 vote
Accepted

Upper bound on the size of a Concept Lattice (Galois Lattice)?

As told in the previous comments, $min\{2^{|O|}, 2^{|A|}\}$ is a correct upper bound. When the parameter $R$ is also available, we can improve the upper bound to $min\{2^{|O|}, 2^{|A|}, 2^{1+\sqrt{|...
user avatar
  • 427
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

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