Questions tagged [db.databases]
Questions in database theory
11
questions with no upvoted or accepted answers
15
votes
0
answers
351
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 ...
7
votes
0
answers
115
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}$, ...
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 ...
6
votes
1
answer
227
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
0
answers
123
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 ...
3
votes
0
answers
149
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 ...
3
votes
0
answers
105
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 ...
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.
0
votes
0
answers
38
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 ...
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-...
-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 ...