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
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 ...
jbapple's user avatar
  • 11.2k
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 ...
Jeffrey Shallit's user avatar
5 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.
M. kanté's user avatar
  • 1,046
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 ...
Reijo Jaakkola's 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. ...
holf's user avatar
  • 2,174
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: ...
mak's user avatar
  • 504
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 ...
jbapple's user avatar
  • 11.2k
3 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 ...
holf's user avatar
  • 2,174
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.
Bjørn Kjos-Hanssen's user avatar
3 votes

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 ...
Tegiri Nenashi's user avatar
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 ...
Evan Patterson's 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 ...
Gamow's user avatar
  • 5,772
3 votes

Database repository containing queries

I think that it would be useful to take a look at the following papers (and their related works sections): François Picalausa and Stijn Vansummeren. What are real SPARQL queries like? In SWIM, 2011. ...
Bartosz Bednarczyk's user avatar
2 votes

Model foreign keys as dependent types?

A database can be viewed from two levels. The physical level concerns how the data is laid out in memory. The logical level concerns what real world entities the data describes. The popular textbook ...
Kevin Clancy's user avatar
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. ...
AntC's user avatar
  • 121
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 ...
Chad Brewbaker's 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 ...
Julio Lemos's user avatar

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