Skip to main content
20 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, ...
Neel Krishnaswami's user avatar
12 votes

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 ...
Emil Jeřábek's user avatar
4 votes

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. ...
holf's user avatar
  • 2,174
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 ...
Kaveh's user avatar
  • 21.7k
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$. ...
A. D.'s user avatar
  • 161
1 vote

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{|...
Luz's user avatar
  • 427

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