Skip to main content

Questions tagged [db.databases]

Questions in database theory

Filter by
Sorted by
Tagged with
24 votes
1 answer
3k 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 ...
Chill2Macht's user avatar
19 votes
5 answers
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 ...
imz -- Ivan Zakharyaschev's user avatar
15 votes
0 answers
356 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 ...
WuTheFWasThat's user avatar
14 votes
2 answers
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 ...
Tianyi Cui's user avatar
12 votes
3 answers
884 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 (...
andreypopp's user avatar
12 votes
2 answers
5k 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 ...
Sam Saffron's user avatar
11 votes
1 answer
808 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 ...
john mangual's user avatar
10 votes
1 answer
651 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 ...
hengxin's user avatar
  • 2,329
9 votes
2 answers
366 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 ...
Ariadne's user avatar
  • 93
9 votes
1 answer
434 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 ...
Artem Kaznatcheev's user avatar
8 votes
1 answer
397 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 ...
john mangual's user avatar
7 votes
1 answer
423 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 ...
kjo's user avatar
  • 531
7 votes
3 answers
2k 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 ...
zfm's user avatar
  • 223
7 votes
0 answers
116 views

Complexity of the unique homomorphism problem up to automorphisms

I am interested in the following problem: given two relational structures $\mathbf{A},\mathbf{B}$, is there a unique homomorphism from $\mathbf{A}$ to $\mathbf{B}$ up to automorphisms of $\mathbf{B}$, ...
Rémi's user avatar
  • 262
7 votes
0 answers
230 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 ...
Uday Reddy's user avatar
  • 4,796
6 votes
4 answers
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 ...
user avatar
6 votes
2 answers
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 ...
Jarek Duda's user avatar
6 votes
1 answer
136 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 ...
Xodarap's user avatar
  • 385
6 votes
1 answer
263 views

What is the impact of encodings of sparse structures on the complexity of the model checking problem?

Some preliminaries first. Consider a purely-relational structure (a.k.a. database) $\mathfrak{A} = (A, R_1^{\mathfrak{A}}, \ldots, R_{|\tau|}^{\mathfrak{A}})$ over some finite signature $\tau = \{ R_1,...
Bartosz Bednarczyk's user avatar
6 votes
3 answers
1k 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) ...
MikleB's user avatar
  • 391
6 votes
1 answer
228 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 ...
nia's user avatar
  • 61
5 votes
3 answers
1k 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? ...
zfm's user avatar
  • 223
5 votes
2 answers
629 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 ...
Tegiri Nenashi's user avatar
5 votes
1 answer
167 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 ...
Ioannis Kokkinis's user avatar
4 votes
2 answers
819 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, ...
user avatar
4 votes
2 answers
964 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 ...
Doug McClean's user avatar
4 votes
2 answers
449 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 ...
Trylks's user avatar
  • 604
4 votes
3 answers
473 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 was ...
ciphor's user avatar
  • 141
4 votes
2 answers
692 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 ...
Henry Story's user avatar
4 votes
0 answers
127 views

Exploding number of homomorphisms

I'm trying to tackle the following problem: given two graphs $A$ and $B$, if there exists a graph $D$ such that $\hom(A, D) > \hom(B, D)$ (i.e. there is more homomorphisms from $A$ to $D$ than from ...
Franciszek Malinka's user avatar
4 votes
4 answers
1k 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 ...
john mangual's user avatar
3 votes
1 answer
557 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 ...
Abraham D Flaxman's user avatar
3 votes
1 answer
115 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 ...
hengxin's user avatar
  • 2,329
3 votes
1 answer
272 views

Model foreign keys as dependent types?

A database consists a list of tables. For example you have a table of Worker and a table of Project where each project needs a ...
molikto's user avatar
  • 347
3 votes
2 answers
468 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 ...
Josh's user avatar
  • 131
3 votes
2 answers
365 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 ...
Jason Kleban's user avatar
3 votes
0 answers
156 views

Is it possible to recover the set of derivation trees of a fact from its semiring provenance in Datalog?

Background: In the context of Datalog, Green et. al (2007) introduce the notion of the Datalog provenance semiring, a generalization of why-provenance as well as bag and probabilistic database ...
Justin Lubin's user avatar
3 votes
0 answers
132 views

I am looking for a detailed list of known reductions of NP-Complete problems

I am looking for a detailed list of known reductions of NP-Complete problems. Much like Richard Karp's list of 21 NP-Complete problems has more than a dozen reductions, I am looking for a bigger ...
Andrija Sevaljevic's user avatar
2 votes
1 answer
2k 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 ...
gizgok's user avatar
  • 141
2 votes
1 answer
85 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 ...
AJed's user avatar
  • 644
2 votes
1 answer
107 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)$ ...
Display Name's user avatar
2 votes
1 answer
177 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 ...
SagarM's user avatar
  • 716
2 votes
2 answers
647 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 ...
Tegiri Nenashi's user avatar
2 votes
1 answer
60 views

Database repository containing queries

For my research, I need to find real database queries (just queries, I do not need the data). However, the unique public "real" queries I know are those appearing in the TPC benchmarks. Does ...
441Juggler's user avatar
2 votes
2 answers
1k 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 ...
An SO User's user avatar
2 votes
3 answers
155 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 ...
Teun D's user avatar
  • 123
2 votes
1 answer
345 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), ...
crazyaboutliv's user avatar
2 votes
0 answers
174 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.
Bartosz Bednarczyk's user avatar
1 vote
1 answer
315 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 ...
MainstreamDeveloper00's user avatar
1 vote
1 answer
2k views

How to recognize safe queries in tuple relational calculus?

How do I determine whether query in tuple relational calculus is a safe query?
Tom Pažourek's user avatar