# Questions tagged [db.databases]

Theoretical questions in Databases

52 questions
Filter by
Sorted by
Tagged with
117 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 ...
16 views

### Why is it more efficient to merge larger runs higher in the tree than perform a balanced tree of merges in an unbalanced ping-pong merge?

While studying the research paper published by Microsoft in 2014, I stumbled upon Unbalanced Ping-Pong Merge. In section 3.2 of the paper, it discusses about merging two sorted runs at a time. It ...
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 ...
74 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)$ ...
156 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 ...
644 views

### How do database aggregations form a monoid?

On cs.stackexchange I asked about the algebird scala library on github, speculating on why they might need an abstract algebra package. The github page has some clues: Implementations of Monoids ...
196 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 ...
93 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 ...
524 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 ...
264 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 ...
1k 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 ...
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 ...
108 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 (...
392 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 ...
409 views

### Representation of procedural knowledge

I know that knowledge about relationships between things can be represented using ontologies and stored in some sort of file or database system. Can a network of procedural knowledge also be created ...
219 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 ...
154 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 ...
107 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 ...
522 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 ...
1k views

### Why do relational databases work at all, given the theoretical exponential complexity of answer finding (in the size of the query)?

It seems to be known that to find an answer to a query $Q$ over a relational database $D$, one needs time $|D|^{|Q|}$, and one cannot get rid of the exponent $|Q|$. As $D$ can be very large, we wonder ...
100 views

74 views

### How to automatically generate indexes and preaggregations from queries

This question might be a little ill-specified, but the idea I want to explore is: User writes a bunch of queries that they want to perform over some data (for concreteness, just consider it a read-...
768 views

### What are recent advances in relational databases?

I'm wondering what are recent advances in relational database theory and related domains? I'm interested in new approaches, query languages (alternatives to SQL and/or extensions to it), products (...
328 views

### Transactional partially-ordered message queuing

I'm having a really hard time finding a solution to a practical programming problem, and I think raw CS might have an answer. The requirement is for a familiar message queue for which there are ...
815 views

### Canonical forms for relational algebra expressions

I'm looking for whatever work may exist, or thoughts people have, on the question of whether/to what extent there exist(s) one or more canonical form(s) to which relational algebra expressions may be ...
2k views

### Purely Functional Equivalent of B-Tree?

I am exploring the idea of writing a DBMS in purely functional way. The traditional data structure used for indexing is B-Tree. I'd like to know some purely functional equivalent of B-Tree that would ...
331 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 ...
980 views

For those doesn't know about linear datalog, linear datalog is a datalog rule in which the number of IDB predicate in each rule is less or equal than one. My question is, why is this interesting? ...
402 views

### Database query languages for efficient queries

It seems that in popular query languages for relational databases, it is possible to create queries that will require a lot of resources to answer. In practice, database admins manage this by limiting ...
108 views

### Producing more functional dependencies (FDs) from a list of functional dependencies (FDs) [duplicate]

Possible Duplicate: Producing more functional dependencies (FDs) from a list of functional dependencies (FDs) I am currently trying to understand functional dependencies and their properties. I ...
3k views

### Data structure that allow efficient tag based lookups

I am looking for a highly efficient data structure for storage of data similar to the following. Id Tags Order1 Order2 -------------------------- 1 1,2 1 1 2 2,5 2 3 3 ...
340 views

### Getting started with Hashing for Information retrieval

I recently finished my bachelors and now work on Cross-lingual language search. I want to get started in hashing and see how they are useful in information retrieval. (Yes, I know what hashing is), ...
372 views

### Cartesian factorization of a finite set of n-tuples

(NB: I asked this question in Math Overflow, and based on the one reply [a comment, actually] that it received so far, I realized that this may be a more appropriate forum for it. I've added a few ...