Theoretical questions in Databases

learn more… | top users | synonyms

4
votes
1answer
64 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 ...
0
votes
0answers
28 views

What are the differences between data partition and data replication regarding distributed transaction?

For a large-scale distributed database (or storage) system, data is often partitioned (wiki) (a.k.a sharding) and/or replicated (wiki) across different nodes. Roughly speaking, data partition splits ...
19
votes
5answers
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 ...
-1
votes
0answers
24 views

Etymology of “relational algebra” and “relational calculus” [duplicate]

Are relational algebra and relational calculus similar to "regular" algebra and calculus? Or why are they named like that?
1
vote
1answer
62 views

Concurrent transactions satisfying “serializability” but not “snapshot isolation”

In [Lin et al@TODS'2009] (Page 5), a history of concurrent transactions satisfying "serializability" ($\textrm{SR}$) but not "snapshot isolation" ($\textrm{SI}$) is given as follows: $H_{example}: ...
0
votes
0answers
77 views

Graph database indexing

Graph databases are usually defined as index-free adjacency and that applies mostly to many current implementations - for example Neo4j - My question is: Is there are any references or papers with ...
0
votes
0answers
68 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 ...
5
votes
4answers
693 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 ...
4
votes
3answers
365 views

How to understand the “Availability” of the CAP theorem?

As we know, in the CAP theorem, "A" means "Availability". On wikipedia, the explanation of "Availability" is: Availability: a guarantee that every request receives a response about whether it ...
1
vote
1answer
167 views

What is DDL (Data Definition Language)?

As a part of my curriculum, I am studying principles of DBMS from the book by Silberschatz and Korth. A part of it is about Data Definition Language (DDL). I ...
6
votes
1answer
177 views

What are good set size estimation algorithms for small sets (around 10-50 elements)?

I'm trying to implement an online distinct counting algorithm, and I have thousands of small sets of 32 bit IP addresses whose sizes I want to estimate with high accuracy (1-5%). I came across quite ...
4
votes
2answers
334 views

Minimize a datalog program

We can consider a datalog program as a set of clauses. Some of them allow to derive others. For instance from: A(x) :- B(x), C(x). B(x) :- D(x). C(x) :- D(x). We ...
-2
votes
1answer
267 views

Find all items which are subsets of an item

I have a problem that I think should have been studied. I am looking for algorithms for it. Each item is a set of key-value pairs. Let $x$ be an item and $F$ be a set of items. Each key and each ...
-2
votes
1answer
158 views

Relational Algebra - Natural Join [closed]

So I got two relations with two common attributes. For one of those attributes, the attribute values in two of the tuples of those relations are the same, for the other they aren't. How does my result ...
8
votes
1answer
306 views

logic in the presence of doubt, uncertainty, lies

I was reading Harry Frankfurt's On Bulls*t, a 1986 philosophical essay about this blurry notion between truth and falsity. This is not a gratuitous exercise. This may have applications to computer ...
7
votes
1answer
335 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 ...
2
votes
1answer
223 views

How do you argue a query is impossible in a query language like SPARQL or SQL?

I've been investigating the ability of the SPARQL query language to represent certain basic tasks in graph theory and machine learning, and have come to believe that it is not possible to do some. For ...
2
votes
1answer
300 views

How to go about proving the basic operators in relational algebra are independent of each other?

The five basic operator select, project, cross, union and diff in relational algebra are independent of each other. I'm trying to formally prove this statement but can only progress for cross product ...
0
votes
1answer
144 views

Combining multiple time-based datasources with different periods

I have two time-based data sources (one providing data by month and the other by week) that must be combined to create a third daily source (recognizing that at best we're getting one possible ...
6
votes
1answer
129 views

Can we do joins in NC?

Suppose we want to join two relations on a predicate. Is this in NC? I realize that a proof of it not being in NC would amount to a proof that $P\not=NC$, so I'd accept evidence of it being an open ...
7
votes
0answers
180 views

Relational model for data structure reasoning

I am trying to find out if there is any work on applying the Codd's relational model (underlying relational databases) for reasoning about linked data structures. Any connections with UML models and ...
4
votes
2answers
439 views

Is analogy between database and probability concepts legitimate?

In Relational Databases: Tutorial for Statisticians Joe R. Hill casts probability view onto database theory. In Table 1 the author summarized the parallels between the two disciplines, describing ...
2
votes
1answer
76 views

Lower bounds on batched query search

I am not much in the field of databases. But the problem I m facing is the following: given a database $D$, we receive a batch of distinct queries $Q = \{q_1, ..., q _k\}$, where each $q_i$ is a ...
0
votes
1answer
68 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 ...
11
votes
3answers
589 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 ...
5
votes
1answer
354 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 ...
2
votes
1answer
264 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 ...
2
votes
0answers
74 views

Is DB Normalization done purely based on the primary key or is it done based on all the candidate keys?

I have come across two flavors of the normalization procedure while referring the Internet and textbooks: Type 1. Normal forms based only on the primary key. In this type, 2NF disallows Partial ...
4
votes
2answers
420 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 ...
13
votes
2answers
969 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 ...
8
votes
2answers
284 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 ...
3
votes
3answers
542 views

why is Linear Datalog interesting?

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? ...
9
votes
1answer
329 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 ...
0
votes
0answers
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 ...
9
votes
2answers
1k 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 ...
2
votes
1answer
308 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), ...
2
votes
1answer
314 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 ...
6
votes
1answer
279 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 ...
6
votes
3answers
642 views

Complexity of finding minimal cover of FDs

Given a relational database and the problem is to generate some minimal cover (i.e. the minimal (by cardinality) set of functional dependencies that all other FD follows from them by Armstrong rules) ...
2
votes
3answers
138 views

Searching for matching queries

Suppose you have a large set of queries (could be in SQL form, but conceivably the same problem exists for search engine query strings or Lucene expressions, etc...) stored and you want to know which ...
1
vote
1answer
572 views
4
votes
2answers
553 views

What are the prospects of research in database field?

I have been working with database management systems, and would like to focus on research in this very area some day. I was having a look at the various research labs around the world, ...