Theoretical questions in Databases

learn more… | top users | synonyms

-3
votes
0answers
25 views

Difference between parallel and concurrent buffering?

In double buffering there are two terms Concurrent buffering. Parallel buffering. What is the difference between them, answer with example will be appreciated. Are they both in use now a days ? ...
1
vote
1answer
53 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}: ...
-2
votes
0answers
21 views

Does 4NF imply BCNF? [migrated]

Wiki says: 4NF is the next level of normalization after Boyce–Codd normal form, but I can not see how the definition of 4NF implies BCNF. Consider the relation with 3 attributes: Country, ...
0
votes
0answers
76 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
63 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 ...
1
vote
1answer
149 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 ...
-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
132 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
304 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
315 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
220 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
285 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 ...
6
votes
1answer
176 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 ...
0
votes
1answer
143 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 ...
5
votes
1answer
127 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
178 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
3answers
363 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 ...
4
votes
2answers
431 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 ...
4
votes
2answers
331 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
256 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
399 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 ...
11
votes
3answers
576 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 ...
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 ...
3
votes
3answers
527 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? ...
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 ...
8
votes
1answer
326 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 ...
15
votes
3answers
904 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 ...
8
votes
2answers
282 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 ...
5
votes
4answers
659 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 ...
5
votes
1answer
344 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
312 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 ...
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), ...
6
votes
1answer
276 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 ...
13
votes
2answers
942 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 ...
6
votes
3answers
637 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
137 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
538 views

How to recognize safe queries in tuple relational calculus?

How do I determine whether query in tuple relational calculus is a safe query?
4
votes
2answers
545 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, ...