Questions tagged [db.databases]
Theoretical questions in Databases
61
questions
1
vote
1
answer
44
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 ...
- 121
3
votes
0
answers
90
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 ...
3
votes
0
answers
113
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 ...
0
votes
0
answers
37
views
Do we need generic libraries of the SQL language?
Sorry I don't know where to post this question as it's interdisciplinary of progLang, softEng and databases.
When I program in SQL I frequently need to write duplicate code of similar functionalities. ...
- 11
3
votes
1
answer
253
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 ...
- 347
7
votes
0
answers
111
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}$, ...
- 143
0
votes
0
answers
36
views
Making primary keys explicit in a Boolean relation
Suppose we have a Boolean formula $\phi(X,Y)$ over the sets of Boolean variables $X$ and $Y$, representing a binary relation. There are in general many tuples in this relation.
Is there a way to ...
- 1,558
1
vote
1
answer
116
views
On motivation towards study of width parameters beyond treewidth
Many width parameters are invented to capture the tractability of CSP (and its equivalent problem, conjunctive queries (CQ) evaluation): treewidth, hypertree width, generalized hypertree width, ...
- 125
6
votes
1
answer
257
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,...
- 1,185
2
votes
0
answers
170
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,185
2
votes
1
answer
174
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 ...
- 706
2
votes
1
answer
100
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
4
votes
1
answer
165
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 ...
4
votes
2
answers
670
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 ...
- 575
1
vote
1
answer
99
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
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 ...
- 325
15
votes
0
answers
344
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 ...
- 331
24
votes
1
answer
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 ...
- 503
-1
votes
2
answers
111
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
4
votes
3
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 ...
- 568
1
vote
1
answer
310
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 ...
-2
votes
1
answer
164
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 ...
3
votes
1
answer
114
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,329
10
votes
1
answer
635
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,329
1
vote
1
answer
118
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,329
3
votes
2
answers
463
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 ...
- 131
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 ...
- 123
-2
votes
1
answer
291
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 ...
- 111
-2
votes
1
answer
930
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 ...
- 1
8
votes
1
answer
395
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 ...
- 568
11
votes
1
answer
777
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 ...
- 568
3
votes
1
answer
551
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
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 ...
- 141
6
votes
1
answer
223
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 ...
- 61
0
votes
1
answer
173
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 ...
- 109
6
votes
1
answer
134
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 ...
- 385
7
votes
0
answers
228
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,786
4
votes
3
answers
470
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 ...
- 141
5
votes
2
answers
628
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 ...
- 626
2
votes
1
answer
84
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 ...
- 644
4
votes
2
answers
438
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 ...
- 604
3
votes
1
answer
351
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 ...
- 179
4
votes
2
answers
934
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 ...
- 141
12
votes
3
answers
865
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 (...
- 221
0
votes
1
answer
76
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-...
- 1
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? ...
- 223
0
votes
0
answers
109
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 ...
- 101
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 ...
- 221
9
votes
1
answer
431
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 ...
- 10.2k
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 ...
