Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [database-theory]

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

0
votes
1answer
36 views

Why “ every non-prime attribute of R is non-transitively dependent on every key of R” in the original def of 3NF?

I have read the definition in of Third_normal_form here , which shows The third normal form (3NF) is a normal form used in database normalization. 3NF was originally defined by E.F. Codd in 1971.[2]...
0
votes
1answer
27 views

Finding the frequency of each unique value of an attribute in a relation (RELATIONAL ALGEBRA)

I am trying to figure out how I can use aggregate functions to solve this problem. For example if I had the table enrolled(student-id, course-id) 123 897 123 645 589 452 009 897 If I wanted to ...
1
vote
2answers
43 views

Why databases make the distinction between basic logical operations and functions

It just occurred to me that things like "greater than or equal to" and other "logical operators" are also just simple functions, such as gte(a, b) == a >= b. ...
1
vote
2answers
25 views

System restarted before transaction is committed

Consider the following log sequence of two transactions on a bank account, with initial balance 12000, that transfer 2000 to a mortgage payment and then apply a 5% interest. ...
0
votes
1answer
26 views

Normal form after decomposition of a relation

I came across a text recently which claims that if we perform a lossless decomposition of a relation R into smaller relations R1 and R2, and if R is in 3NF, both R1 and R2 are 3NF. I felt a bit ...
0
votes
1answer
30 views

Doubt regarding foreign key and referential integrity

I am studying database from Database System Concepts. The author was explaining foreign keys and referential integrity with the help of following schemas: $$ instructor(\underline{ID},\space name,\...
0
votes
1answer
14 views

No. of disk blocks writes required for writing the file

Assume that a file is written using write(fd, buf, K) system calls, where fd is the file descriptor, and K, the number of files to be written to the current file offset which is a multiple of the disk ...
0
votes
0answers
8 views

view serialisable and conflict serialisable

I recently was solving some problems on these topic and realised that in cases where conflict serialisable schedule existed; the number of view serialisable schedule was actually equal to the number ...
0
votes
0answers
17 views

When BCNF decomposition preserves Functional Dependencies?

It is known that BCNF decomposition does not preserve functional dependencies (FDs). For example, for FDs on R(A,B,C), ...
0
votes
1answer
21 views

Whether same output is obtained for the two queries

Consider the following SQL Queries executed on the relation Employee: Employee (Eid, Ename, sal) Eid is the primary key Queries: S1:SELECT count (*) FROM Employee; S2: SELECT count (Eid)...
0
votes
1answer
36 views

Normal form of relation R

It is given that for a relation R all the attributes of the relation appear in some of the candidate keys. It is also given that there is only one compound candidate key which exists for a relation, ...
0
votes
0answers
69 views

How are these two definitions of the Third Normal Form (3NF) equivalent?

According to the textbook by Silberschatz, A relation schema R is in third normal form with respect to a set $F$ of functional dependencies if, for all functional dependencies in $F^+$ of the form $\...
0
votes
0answers
57 views

Any Recoverable schedule which is not a Cascadeless schedule?

When I read about Cascadeless schedule, it says "Every Cascadeless schedule is also recoverable schedule." and the examples are also almost same. I want to know an example of Recoverable schedule ...
0
votes
0answers
10 views

Is a schedule with autocommit and no aborts automatically recoverable?

As in the title, since we won't have problems with cascading aborts and each transaction is committed automatically, doesn't this mean that the schedule will always be recoverable?
0
votes
1answer
28 views

Given a relation and asked to enumerate all FD's and mark the trivial FD's

Given a relation R(A,B,C) and a FD set (A->B, B->C), find the FD Closure. Enumerate all the FD's and organize them accordingly to the LHS of the FD's. Mark all the trivial FD's. I am a little ...
2
votes
0answers
35 views

Is the data-centric “push” model for SQL evaluation nonsense?

The traditional way to implement a SQL database is to parse the query, create a parse tree, and then evaluate it using the "volcano" model. In this model you call .next() on the root node of the tree ...
0
votes
1answer
29 views

How to decompose into BCNF while preserving all functional dependencies

I have a relation R = {A,B,C} and F={AB -> C , C -> B}. In order to check if R is in BCNF. I checked if AB and C are both superkeys and since C is not a superkey I conclude R is not in BCNF. After ...
1
vote
1answer
30 views

Is my decomposition of R into 3NF is lossless and preserving all dependencies?

I have a schema R = {A,B,C,D,E} and the set F of FDs: F = {A --> BCDE, CD --> E, EC --> B}. Candidate key = A Non - Prime Attributes = BCDE Prime Attributes = A According to me, there is no partial ...
0
votes
1answer
33 views

Did Date and Darwen's “Third Manifesto” have a lasting impact?

In 1995, two DB theory researchers, C.J. Date and H. Darwen, published a text with the rather impressive-sounding name "The Third Manifesto" with their ideas regarding future DBMSes, which would ...
3
votes
0answers
32 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. ...
1
vote
0answers
39 views

How to determine conflict serializability without read and writes

I'm learning about conflict serializability in an introduction to databases class. I know how to check if a schema of transactions is conflict serializable when there's reads and writes. Draw the ...
0
votes
1answer
60 views

Why checking if tuple belongs to join of two tables is NP-complete?

I have read that checking if tuple belongs to join of two tables is NP-complete. I had computional-complexity activities during my studies, I remember basics, however I have forgotten details. ...
0
votes
0answers
37 views

Relational calculus expression for projection (Database Management)

I recently came across this question: Let the following relation schemas be given: $R=(A,B,C)$ $S=(D,E,F)$ Let relations r(R) and s(S) be given. Give an expression in the tuple relational calculus ...
0
votes
1answer
52 views

Storing Specific data on DB Table(s)

I have an Excel with 40columns and 20k rows, and i have to store it in a database but i cant figure the best approach for it, the excel format is like this: This table has 30 columns for days, then ...
0
votes
0answers
84 views
-3
votes
2answers
196 views

How many candidate keys are there in the table shown below?

One candidate key is (report_no, author_id). What are the other candidate keys?
0
votes
1answer
45 views

Checking claim in paper “A Read-Only Transaction Anomaly Under Snapshot Isolation” by Alan Fekete et al

In the 2004 paper "A Read-Only Transaction Anomaly Under Snapshot Isolation" by Alan Fekete et al. (which can be found here and here) the authors state: We also note that any execution of T1 and T2 ...
0
votes
1answer
44 views

What are the essential differences and similarities among “data”, “Information” and “knowledge” in the context of Computer Science?

The terms "data", "information" and "knowledge" are quite interchangeably used in Computer Science. Strictly speaking, they do carry a very different meaning. I want to know their precise meanings and ...
1
vote
2answers
215 views

Serializability and the Lost Update Problem

Serializability is the strongest consistency level with regard to the execution of two concurrent transactions T1 and T2. That is, if T1 and T2 independently change the application between consistent ...
0
votes
1answer
19 views

Is relation following given characteristic already in 2NF, 3NF and BCNF?

The definitions of 2NF, 3NF and BCNF goes like this: 2 Normal Form (NF) definition A relation is in second normal form if and only if it is in first normal form and all the non-key attributes ...
0
votes
0answers
91 views

Understanding multiversion timestamp ordering protocol in database systems

I was reading multiversion timestamp ordering protocol from the book Database Systems Concepts by Korth et. al. It can be explained in simpler words as follows: Each data item version $Q$ has two ...
0
votes
1answer
101 views

Use of existential quantifier in tuple relational calculus

It is somewhat confusing to me when to use quantifiers in tuple relational calculus (TRC). I stumbled upon following problem and I am still scratching my head thinking why not TRC query can be ...
-2
votes
1answer
69 views

Query Super Type and Subtype in Mysql

Assuming I have a schema depicted in the image , showing relationships(specialization) between Staffs, Academic Staffs and Non Academic Staffs. Is it possible to have a query that retrieves the ...
0
votes
0answers
48 views

Optimal solution to Cartesian Product of two sets (computationally)

Given two large sets (say 1 million items each), what is the fastest way to compare the values with each other. This is a typical join problem, for which there are two standard solutions: nested ...
1
vote
1answer
175 views

How a range query works on a simple B+tree

Given a B+tree indexing scheme, wondering how a database actually goes and finds records matching a range query such as the following: ...
0
votes
1answer
13 views

Meaning of “pushing x down” and “pulling x up” in database query handling

In this book there is a lot of mention of "pushing x down". For example: Pushing NOT operations down and eliminating them NOT operations need to be pushed downwards for correctness reasons. ...
2
votes
0answers
206 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 ...
0
votes
1answer
117 views

Armstrong's axioms more precisely 'inference rules': what's the distinction?

"more precisely 'inference rules'" is what wikipedia says twice. Other references I've looked at (the Alice book, Ullman lecture notes cited, Maier textbook) name them as Armstrong's Axioms, use them ...
1
vote
1answer
41 views

Data-structure for dynamic disjoint-sets

I have a collection of objects, with certain properties (let say 3 - zone, type, owner) only having a small predetermined possible set of values (like enum). This is just a simple (javascript) array ...
-1
votes
1answer
111 views

What is the equivalent form of full outer join in relational algebra?

Considering only basic relational algebra operations, how can we implement the full outer-join ?
2
votes
1answer
78 views

How to do compare-and-increment different locations with in memory MVCC?

I'm reading the paper An Empirical Evaluation of In-Memory Multi-Version Concurrency Control which is about implementations of MVCC for in-memory databases. Section 3.3 on Two-phase Locking (MV2PL) ...
0
votes
1answer
199 views

First Order Logic, First Order Logic + Recurrence and SQL

we know that SQL standard is equivalent to First Order Logic (FOL). I've seen at my lecture that graph connectivity cannot be expressed by FOL, so in SQL as well. But we know that we can easily solve ...
0
votes
1answer
240 views

Transitive dependency in 3NF

Came across this question : State whether True or False A prime attribute can be transitively dependent on a key in 3NF Answer: True How could this be true? Because as far as I know, A relation ...
0
votes
1answer
68 views

Conflict serializibility

So, the task is to prove the following: If S is a schedule containing at most one write action, then S is conflict-serializable. The answer is yes, but I disagree, because the following schedule ...
0
votes
0answers
33 views

finding third functional dependency and its candidate keys

i'm solving a multi part question regarding candidate keys and functional dependencies. now i've already found 2 dependencies(the canonical covering of the functional dependencies contains only 3 ...
0
votes
2answers
451 views

Does 1NF require that there can be no duplicate rows?

From Database System Concepts, by Silberschatz, Korth and Sudarshan : A domain is atomic if elements of the domain are considered to be indivisible units. We say that a relation schema ...
0
votes
2answers
192 views

Does 2NF require 1NF?

From Database System Concepts, by Silberschatz, Korth and Sudarshan : A domain is atomic if elements of the domain are considered to be indivisible units. We say that a relation schema ...
3
votes
1answer
604 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 ...
1
vote
1answer
144 views

Are all relational schemas with partial dependencies not in 3NF?

From Database Management Systems, by Raghu Ramakrishnan, ‎Johannes Gehrk Let R be a relation schema, F be the set of ...
2
votes
2answers
272 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}(\...