Questions tagged [database-theory]

the analytic study of ways in which information is efficiently and effectively stored to and retrieved from computer systems.

Filter by
Sorted by
Tagged with
38
votes
6answers
6k views

What use are groups, monoids, and rings in database computations?

Why would a company like Twitter be interested in algebraic concepts like groups, monoids and rings? See their repository at github:twitter/algebird. All I could find is: Implementations of ...
29
votes
3answers
2k views

Do subqueries add expressive power to SQL queries?

Does SQL need subqueries? Imagine a sufficiently generalized implementation of the structured query language for relation databases. Since the structure of the canonical SQL ...
20
votes
3answers
320 views

Extension of SQL capturing $\mathsf{P}$

According to Immerman, the complexity class associated with SQL queries is exactly the class of safe queries in $\mathsf{Q(FO(COUNT))}$ (first-order queries plus counting operator): SQL captures safe ...
19
votes
2answers
840 views

Does the 'difference' operation add expressiveness to a query language that already includes 'join'?

The set difference operator (e.g., EXCEPT in some SQL variants) is one of the many fundamental operators of relational algebra. However, there are some databases ...
12
votes
1answer
435 views

About Codd's reduction algorithm

Codd's Algorithm converts an expression in tuple relational calculus to Relational Algebra. Is there a standard implementation of the algorithm? Is this algorithm used anywhere? (It seems that the ...
9
votes
3answers
2k views

What does this definition of a Primary key mean?

My text book gives the following definition of a primary key in a relational database, which I don't entirely understand. Help would be greatly appreciated. Let $R$ be a relation. Then the primary ...
9
votes
1answer
265 views

Can joins be parallelized?

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 ...
7
votes
1answer
625 views

A relational algebra extended to model the full DML (“CRUD”) domain

There are multiple references about the relational algebra for modeling queries (SELECT) but I have found very very little on the expanded algebra that would ...
6
votes
3answers
22k views

What is the difference between “strict schedule” and “cascadeless schedule”?

In database transactions theory, what is the difference between a strict schedule and a schedule that is merely secured against cascade aborts? Could you give an example of a schedule that is ...
6
votes
2answers
122 views

Optimizing a join where each table has a selection

Consider the following query: ...
6
votes
1answer
472 views

Why do relational databases use 2PC for distributed transactions over the likes of Paxos?

Paxos is more powerful and in the famous writing "Consensus on Transaction Commit" : http://research.microsoft.com/pubs/64636/tr-2003-96.pdf, Jim Gray and Leslie Lamport describe 2PC as a special case ...
6
votes
1answer
1k views

Measuring entropy for a table (e.g., SQL results)

We're running some benchmarks for an approximative query-answering system. It's sufficient to just think of it as running some SQL queries with joins. We are counting the results returned as part of ...
5
votes
4answers
3k views

When should you use the existential and universal quantifiers for Relational Calculus?

Could someone explain to me WHEN do you use existential and universal quantifiers for Relational Calculus? Given this schema: Hotel(hotelNo, hotelName, city) ...
5
votes
2answers
5k views

Why is the Mean Time To Failure of multiple disks calculated via division and not multiplication?

I am reading about disk redudancy. I read the following: Suppose that the mean time to failure of a disk is 100,000 hours. Then the mean time to failure of some disk in an array of 100 disks ...
5
votes
1answer
515 views

Compare-and-Swap in an RDBMS for custom locks and lock escalation

I'm applying the Compare-and-Swap technique to a SQL database to create custom row-level locking in my dataset, allowing for safe READ UNCOMMITTED isolation at the database level. The Resource table ...
5
votes
0answers
37 views

Uni-directional synchronization and locking issues

Suppose there are two databases, $D_1$ and $D_2$. Let's further assume $D_1$ is always up and $D_2$ can be down sometimes. When it goes up again, it has to restart. $D_1$ is filled by say a dozen ...
4
votes
2answers
152 views

Measuring availability from CAP theorem

I wonder how to check availability property from CAP theorem. Consistency check is conceptually easy: if at least once somehow same query at the same time returns different results, then the system ...
4
votes
1answer
2k views

Time Complexity of Sort-Merge Join

According to this German Wikipedia article, the time required to merge relations $R$ and $S$ is $\in \mathcal{O}(|R| + |S|)$ if both relations are already sorted. [Note: You don't really need to read ...
4
votes
1answer
444 views

What actually is the concept of transparency? Why not call it Abstraction?

I searched this over Google few times but ended up with articles on transparency rather than an answer. With relation to distributed database study(or distributed OS), what is the concept of ...
4
votes
1answer
188 views

Computing number of block reads given relational algebra statement

So I'm just starting to learn about query processing and such in databases and I'm having some trouble. I don't really understand how to compute the minimum number of block reads given a relation and ...
4
votes
1answer
545 views

How to determine if a database schema violates one of the less known normal forms?

In database normalization, 1NF (no multivalued attributes), 2NF (all non-PK attributes depending only on PK attributes) and 3NF (all non-PK attributes depending on all of the PK attributes) are widely ...
4
votes
1answer
35 views

How to model references in an ontology

I am interested in creating an ontology which will model arguments (among other things). For example, a triple in the ontology might be ...
4
votes
1answer
444 views

Difference between the Cartesian product in set theory and in relational algebra

What's the difference between the Cartesian product in set theory and in relational algebra? The Cartesian product in set theory is defined as: $$A \times B = \{(a, b) \mid (a \in A) \land (b \in B)\...
4
votes
1answer
1k views

What is OUTER UNION and why is it partially compatible

I am trying to understand how a OUTER UNION $∪^✳$ works, and why it is only partially compatible. I am aware this operation was created to take union of tuples ...
4
votes
1answer
2k views

Number of conflict serializable schedules

Two transactions $T_1$ and $T_2$ are given as: $$T_1: r_1(X)w_1(X)r_1(Y)w_1(Y)$$ $$T_2: r_2(Y)w_2(Y)r_2(Z)w_2(Z)$$ where $r_i(V)$ denotes a read operation by transaction $T_i$ on a variable $V$ and $...
4
votes
1answer
97 views

why should I go for logistic regression?

I am a student working on a Database management project with a bit of Python coding involved. The project is about Review Analysis.Basically I am trying to read a review and determine how good or bad ...
4
votes
1answer
116 views

Algorithm for automatic/optimal database joins?

I'm curious if there is existing literature or well known algorithms out there for a problem I am working on. Given a normalized relational database with valid foreign key constraints and a list of ...
4
votes
2answers
8k views

“At least one” clause in Relational Algebra

I'm fairly new to the syntax of relational algebra, and I'm having a hard time understanding how I could set a "at least one" clause. Example: I have: a table with books (listing the title, year ...
4
votes
0answers
27 views

Data structure for identifying elements while keeping track of relation

I'm looking for a data structure representing a finite set $I$ and a $d$-relation $R \subseteq I^d$ such that the following operations can be implemented efficiently: Add a new element $i$ to $I$. ...
3
votes
3answers
1k views

What is the difference between Transitive Closure and Join?

In database theory, there is a notion of transitive closure over relations. I am wondering if join operator over relations is also a special case of transitive closure?
3
votes
1answer
2k views

Combine the following IP Addresses into a single block

I was asked to combine the ip addresses into a single block: 16.27.24.0/26, 16.27.24.64/26, 16.27.24.128/25 I managed to convert the given ip addresses into binary: 00010000.00011011.00011000....
3
votes
1answer
608 views

How to evaluate relations in a DAG?

To begin with: what I know of computer science is what friends have told me and what I've read on Wikipedia. Please correct me if I'm using some term wrongly, or if there is something I can clarify. ...
3
votes
2answers
446 views

Can you reduce a precedence graph or do *all* relevant nodes need to be connected

Let's say we have the following simple transaction-schedule: T1 | T2 | T3 -----+------+----- w(x)| | | w(x) | | | w(x) T1 comes before ...
3
votes
1answer
697 views

Keeping a binary search tree by splitting nodes (like a B-Tree)

A B-tree is kept balanced (i.e. all leaves at same depth) by splitting a node when adding a child that won't fit, and propagating this splitting up to the root. Can the same technique be used to keep ...
3
votes
1answer
14k views

What is the difference between Strict 2Phase Locking and 2Phase Locking?

I have read some notes about the two but yet still confused about why there is a need for the strict 2phase locking. Based on some slides, Two Phase Locking and Strict Two Phase Locking They have ...
3
votes
1answer
898 views

Partial order, total order, and version order in transaction histories

In Section 3.1.2 "Transaction Histories" of the PhD thesis by Atul Adya [1]: A history $H$ over a set of transactions consists of two parts: (1) a partial order of events $E$ that reflects the ...
3
votes
2answers
94 views

Conjunctive Query Containment as SAT

The problem of conjunctive query containment is known to be NP-Complete (originated at Chandra&Merlin 1977). Typically it's shown by reducing 3SAT or 3-colorability into this problem, and the ...
3
votes
1answer
7k views

When is relation in 3NF but not in BCNF?

A book by Korth et al. defines BCNF as follows: A relation schema $R$ is in BCNF with respect to a set F of functional dependencies if, for all functional dependencies in $F^+$ of the form $α→β$, ...
3
votes
1answer
121 views

State of the art time complexity for getting (tree) descendants by type/attribute

Let's say I have a tree comprised of nodes where each node is of some type (T), where there is a known/fixed number of types (i.e. similar to attributes in an xml document), and where a node can only ...
3
votes
2answers
962 views

Rollback and Timestamp Ordering in Database

If we use the Timestamp Ordering for concurrency control in the following scheduling: My TA says $T_2,T_3,T_5$ is Run and $T_4,T_5$ is Rollback. I think it's false. Is there any expert who could help ...
3
votes
1answer
1k views

Can a schedule with cyclic precedence graph still be serialisable?

We know Every conflict serializable schedule is serializable, but not all serializable schedules conflict-serializable. (*) so it means there is at least one serializable schedule that not conflict ...
3
votes
1answer
33 views

Space-efficient data structure for analytical querying of multiple branching evolutions of a dataset

Problem Description I have a data state space: a set of data sets, each of which can be modelled as a collection of arbitrary key-value pairs. These data sets are each a branch of evolution of a ...
3
votes
0answers
34 views

If we could use electrons as information storage, how would we model a database?

It's not completely incredible that electrons are accessible information storage units. So let's say there is a breakthrough and we suddenly have read/write access to every electron on the planet. ...
3
votes
0answers
477 views

Algorithm for segmenting input query into query/join tree

Wondering what algorithms look like for implementing a complex JOIN query handler. Taking a look at this paper Building Query Compilers they talk about Query Graphs ...
3
votes
0answers
48 views

What data structure should I use for storing my data?

I am currently looking for a way in which I can store my data, and quickly look it up. What currently seem to be the best idea is to use a hash map. reasons: To identify what item I am looking for, ...
3
votes
0answers
82 views

Wikipedia on MVCC

I read about Multiversion Concurrency Control in Wikipedia. They say that every piece of data in DB has a Read Time Stamp (RTS) and If transaction Ti wants to Write to object P, and there is also ...
3
votes
0answers
98 views

Describe data structure using equations

Good afternoon. At work I'm currently developing a system which takes user input (well structured) and then stores it in memory to do some processing. The input is basically a dataset formed by ...
3
votes
0answers
530 views

How to generate globally unique timestamps for transactions in distributed database systems?

According the paper [1] (Section 4), timestamp ordering (T/O) is a technique whereby a serialization order is selected a priori and transaction execution is forced to obey this order. In the following,...
2
votes
1answer
38k views

Use count() in relational algebra

Person(name, phone) Mike 456-789 Mike 123-456 John 230-785 $\dots \dots$ How to get those people who have more than one phone numbers with relational algebra? This sounds simple, but I am ...
2
votes
2answers
817 views

Max() in Domain Relational Calculus

I was looking through my notes on domain relational calculus, and noticed an interesting result in a question about finding the most expensive pizza(s), given a pizza table with schema $\text{pizza}(\...

1
2 3 4 5