# Questions tagged [db.databases]

Theoretical questions in Databases

55 questions
Filter by
Sorted by
Tagged with
23 views

• 1,110
163 views

### Order-invariant conjunctive queries are FO-definable without the order

I'm looking for a reference for Exercise 6.11 from Libkin's FMT book: Prove that an order-invariant conjunctive query is FO-definable without the order relation. All help is appreciated.
• 1,110
164 views

### What is the computational complexity of Acyclic Joins?

I am quite new to relational algebra, but I realize that there are efficiency proofs for processing Acyclic joins. I have not been able to understand these results, but this particular problem is ...
• 684
90 views

### In external memory, is grouping equal elements easier than sorting?

Sorting an array will put equal elements adjacent to each other. So, in no model of computation can grouping equal elements be harder than sorting. In the RAM model, grouping equal elements is $O(n)$ ...
• 327
162 views

### Complexity of Acyclic Hypergraph Isomorphism

It is well known that the graph isomorphism problem restricted on trees is much easier than the general case. It can be done in logarithmic space (Jenner B, Lange KJ, McKenzie P. "Tree isomorphism and ...
624 views

### What does the category of RDF models look like in Institution Theory?

The Question in short Here is the question in its pure form. Details of my reasoning can be found below. The RDF1.1 spec semantics defines a model to consist of a set IR of objects and IP of ...
• 515
1 vote
97 views

### Minimum number of columns making each row different

I'm curious whether this problem is NP-hard: suppose you are given an arbitrary $m\times n$ 0-1 matrix (each element is either 0 or 1, for the simplicity of the problem), and any pair of rows (i.e. a ...
• 41
2k views

### Improving Bloom filter - can we distinguish elements of a database using less than 2.33275 bits/element?

While we usually use large e.g. 64 bit hashes, there are many techniques to reduce this size, e.g. for savings in storage and transmission. Popular Bloom filter instead of marking just 1 hash ...
• 317
324 views

### Differential privacy and data poisoning

A differentially private algorithm takes datasets containing inputs and produces randomized outputs, such that no small change in the dataset can shift the distribution of outputs by too much. This ...
2k views

### Is there a relationship between relational algebra/calculus and category theory?

I am aware of at least two different theoretical approaches for understanding relational databases: Codd's relational algebra/calculus, and category theory. Is there any relationship between these ...
• 493
109 views

### Are there (N-1)! ways to order joins?

On page 2 of http://db.csail.mit.edu/6.830/lectures/selinger.ppt, there is the following text: How to order a series of N joins, e.g., A.a = B.b AND A.c = D.d AND B.e = C.f $N!$ ways to order joins (...
• 109
939 views

### Is there a set theoretic way to look at SQL?

I have been learning about SQL and at times it feels like set theory. A statement like SELECT * FROM myTable is like a set $\{ x: x \in \text{myTable} \}$. A ...
• 578
1 vote
288 views

### How can I formalize key value stores with set theory? [closed]

I'm currently developing a simple key-value NoSQL store and want to build its formal model. I'm interested in knowing if there some work about formalization of key-value stores outside of category ...
161 views

### What are the most fundamental metrics (criterions) of database performance?

I'm a student working on my thesis in database theory and looking for some research in the field of formal models of database performance and couldn't find any works in this area. I'm interested: what ...
113 views

### Lower bounds and impossibility results for distributed transactions

I am studying on distributed transactions, mainly on the correctness criteria (e.g., serializability (SR) and snapshot isolation (SI) in replicated settings) and their implementations. To avoid ...
• 2,319
621 views

### What are the major research issues in distributed transactions?

Background: Transaction processing has been a traditional research topic in database theory. Nowadays distributed transactions are popularized by the large-scale distributed storage systems which ...
• 2,319
1 vote
115 views

356 views

### DATALOG references

What are the best references for self study in DATALOG? I am particularly interested in expressive power, complexity results, evaluation methods, extensions of DATALOG with negation etc. Are there any ...
• 93
1k views

### What are the most known database disk storage layout algorithms?

I can list for example algorithms used in databases: append only b-trees (MVCC like used in CouchDB) merged logs (like used in Big Table, Hbase, Cassandra) paged storages grouped in extents (like in ...
1k views

### What is First-Order Rewritable (and FO-Query)?

I just wonder what FO Rewritable is, put an example to make it clearer for me. Also, I heard that a language that is FO Rewritable is very good, in what sense? It is said as follow: A class C of ...
• 223
588 views

### First order expression for functional dependency

I'm puzzled with functional dependency formula in first order logic. It is triggered by http://rjlipton.wordpress.com/2010/01/17/a-limit-of-first-order-logic/ where there seems to be a confusion ...