Skip to main content

Questions tagged [db.databases]

Questions in database theory

Filter by
Sorted by
Tagged with
0 votes
0 answers
17 views

On the Relationship Between Graph Isomorphism and Equivalence in ETL Workflow Dependency Graphs

Let $G = (V, E)$ and $G' = (V', E')$ be two DAGs representing dependency graphs of ETL workflows. Each node $v \in V$ (or $v' \in V'$) represents a task, which is a tuple $t_v = (q_v, d_v, s_v)$, ...
Zoom's user avatar
  • 1
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
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
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
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
3 votes
1 answer
273 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
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
0 votes
0 answers
39 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
1 vote
1 answer
121 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, ...
xxks-kkk's user avatar
  • 125
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
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
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
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
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
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
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 ...
defg's user avatar
  • 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 ...
Jarek Duda'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
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
-1 votes
2 answers
113 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 (...
Jingguo Yao'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
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 votes
2 answers
180 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 ...
MainstreamDeveloper00'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
10 votes
1 answer
652 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
1 vote
1 answer
121 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}: ...
hengxin's user avatar
  • 2,329
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
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
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
-2 votes
1 answer
1k 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 ...
ab cd's user avatar
  • 1
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
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
3 votes
1 answer
558 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
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
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
0 votes
1 answer
180 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 ...
Jack R-G's user avatar
  • 109
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
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
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
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
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
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
3 votes
2 answers
366 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
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
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
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
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
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 ...
Alex's user avatar
  • 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 ...
Sam Saffron's user avatar
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