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
313 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
832 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
434 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
1answer
261 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 ...
8
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 ...
7
votes
1answer
610 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
20k 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
411 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
1answer
483 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
4k 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 ...
4
votes
2answers
145 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
406 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
181 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
536 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
34 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
391 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
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
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
567 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
435 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
693 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
13k 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
840 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
1answer
1k 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 ...
3
votes
1answer
6k 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
119 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
1answer
111 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 ...
3
votes
2answers
886 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
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 ...
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
422 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
81 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
92 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
492 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
34k 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
690 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}(\...
2
votes
2answers
54 views

Restricting capabilities of admin role in database schema

Suppose I have to design database for learning management system. Which will going to have user having roles such as admin, teacher, tutor, student etc. In a system student can submit solution for an ...
2
votes
2answers
6k views

Finding the Candidate Keys of a Relation Using the FD's

I have definitely checked out many different related posts. I have also done different sample problems from online sources as well from a similar problem. However, I am stuck on the problem below ...
2
votes
2answers
146 views

Can A still be a key if two tuples are the same

I am studying database functional dependency. It says if A can functionally determine all other attributes, it is considered to be a key. What if 2 tuples are exactly the same, can we still say A is ...

1
2 3 4 5