# Tag Info

18

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

12

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 which all quantifiers of the original formula can be simulated by conjunctions and disjunctions. In particular, the number of quantifiers (hence quantifier rank) ...

4

Consider $S=\{1,2,3\}$ and relations $A=\{(1,3)\}, B=\{(1,2)\}, C=\{(2,3)\}$. Then $A^*=(A\setminus B)^*= A\cup\{(i,i)\ |\ i\in S\}$, $(B\cup C)^* = \{(i,j)\ |\ i,j\in S, i\le j\}$, and $C^* = C\cup \{(i,i)|i\in S\}$. In particular, $A^*\subseteq (B\cup C)^*$, but $(A\setminus B)^*\nsubseteq C^*$.

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

3

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 quantifiers and your model has k objects in it you can express the formula by stating that k distinct objects exists and the relation between them can be expressed as a ...

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

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$. Then Andréka and Bredikhin show that two terms $t$ and $u$ are equivalent iff there is a graph homomorphism from $G_t$ to $G_u$ and a graph homomorphism from $... 1 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{|R|}}\}\$

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

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