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
0answers
23 views

Relational Database to Aggregate Data Model

Can any application currently using a relational database be rewritten to use an Aggregate Data Model, by Focusing on data modelling aspects only (ignoring other features like salability or ...
0
votes
1answer
39 views

Ε-R diagram with conditions , is it possible?

I want to create a database and model it with an E-R diagram. This database should be about a library. An entity is the member of the library, where the member can borrow books from the library. ...
3
votes
1answer
23 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 ...
1
vote
0answers
27 views

How do I implement fixed block storage file system in database from typical file-level file system?

I've a typical parent ID based file system in database and files are physically stored on disks. What I want is to store files in blocks (4096K) of fixed size. Chunking can be used I found, but how ...
0
votes
0answers
19 views

Understanding non repeatable read anomaly in databases

This paper discusses in detail ANSI isolation levels discussed in ANSI SQL standard on page 84. Paper introduces following shorthand for describing histories which contain reads, writes, commits and ...
0
votes
0answers
22 views

SQL - Are there row and column operations in row storage SQL database

I have a very fundamental question. When one says data is stored in a table, I understand what row-store is, but are all values in a table stored in contiguous locations? If we are trying to join ...
0
votes
0answers
22 views

Understanding repeatable read isolation level

Wikipedia defines following terms: With a lock-based concurrency control DBMS implementation, serializability isolation level requires read and write locks (acquired on selected data) to be ...
1
vote
1answer
28 views

Can a schedule be conflict serializable but not serializable?

A schedule is called conflict serializable if it can be transformed into a serial schedule by swapping non-conflicting operations. Then, My question is: Can a schedule be conflict serializable but ...
1
vote
1answer
25 views

Role of weak entities in avoiding inconsistencies

My material on database claims that: Weak entities help to avoid data duplication and inconsistencies arising due to duplicating the key of the strong entity. My question is how can a strong ...
0
votes
0answers
23 views

When cascadeless and / or recoverable schedules can contain blind writes?

Some quick definitions / theory: If instructions $I_i$ and $I_j$ of two different transactions operate on same data item and if any of them is a write operation then they are conflicting ...
1
vote
0answers
13 views

Understanding connection between different database concurrency control protocol

I have came across following diagram related to timestamp based concurrency control protocols in database systems: I don't know whether its correct or not. As per my interpretation, it means all ...
1
vote
0answers
23 views

Understanding validation based database concurrency control protocol

Database book by Korth explains validation protocol as follows : To perform the validation test, we need to know when the various phases of transactions took place. We shall, therefore, associate ...
0
votes
1answer
54 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
38 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
27 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
28 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
36 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
33 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
37 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
71 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
67 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
29 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
39 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
39 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
51 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
35 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
52 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
61 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
43 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
54 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
89 views
-3
votes
2answers
219 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
48 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
50 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
287 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
20 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
162 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
112 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
104 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
57 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
260 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
14 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
238 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
129 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 ...