Questions tagged [db.databases]

Questions in database theory

11 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...
WuTheFWasThat's user avatar
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}$, ...
Rémi's user avatar
  • 262
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 ...
Uday Reddy's user avatar
  • 4,806
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 ...
nia's user avatar
  • 61
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 ...
Franciszek Malinka's user avatar
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 ...
Justin Lubin's user avatar
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 ...
Andrija Sevaljevic'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
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 ...
Nicola Gigante's user avatar
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-...
Andy's user avatar
  • 1
-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 ...
wroscoe's user avatar
  • 111