Skip to main content

# Tag Info

## Hot answers tagged relational-structures

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, ...
• 32.7k
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 ...
• 17.9k
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. ...
• 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 ...
• 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$. ...
• 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{|...
• 427

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