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
0
votes
0answers
24 views

How to decide if two conjunctive queries cannot have any result in common

Consider the following queries: Q1: age > 18 & age < 24 & gender = 'male' Q2: age > 25 & gender = 'male' & major = 'CS' Q3: age = 20 & major = 'CS' Clearly, given any ...
0
votes
1answer
16 views

Prime attribute dependant on another prime attribute allowed under BCNF?

I have been studying DBMS ans I have a question that I got conflicting answers to: Is prime attribute that is dependant on another prime attribute allowed under BCNF? Meaning P->P. I know that NP->P ...
1
vote
1answer
32 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 ...
0
votes
1answer
30 views

Join with Bloom-filters

can you tell me how i can use a bloom-filter by a joining operation with two tables? let's assume that: Table A ={A_id,B_id,age}, Table B = {B_id, color}. now i want to use a bloom-filter so i can ...
0
votes
0answers
27 views

For which instance are those relational queries equivalent?

I have the following problem and i hope you could help me. Given is the following database schema, Student($\underline{\text{MatNo}}$, SName) Course($\underline{\text{CNo}}$, CName) Took($\...
0
votes
0answers
11 views

Which Window models in stream data processing increasing monotonically?

Good morning, at the moment I try to understand which of the types of windows are increasing monotonically (not a strict increase) In Scholl we hat the following windows Tuple-based Sliding ...
0
votes
0answers
31 views

How do i solve this task about the the Reservoir Sampling algorithm?

Hello I have the following task (no homework). You are using the Reservoir Sampling algorithm. You process the 2000th element in the data stream and are maintaining a sample of size 500. What is ...
1
vote
1answer
74 views

Is “Query Equivalence” decidable?

I have studied in my Computability course that it is impossible to design an algorithm $A(x,y)$ which decides, for every couple of programs ($P_1$, $P_2$), whether they are equivalent (e.g. $\forall d ...
1
vote
1answer
20 views

Adding an ordered into a relationship without violating the functional dependencies

Assuming that we have the relationship $R(A,B,C,D)$, the tuple $(W,X,Y,NULL)$ and the following functional dependencies: $$A \to C$$ $$A \to B,D$$ is it possible to insert a tuple with $NULL$ values,...
1
vote
1answer
25 views

Find candidate keys given functional dependencies

In my database class we practiced how to find the candidate keys, given the functional dependencies. However they were easy examples, based on a single attribute being functionally dependent on a ...
0
votes
0answers
33 views

Can I combine these two relations from the relational model?

I have the following task: Translate the following ER diagram to the relational model. Use as few relations as possible. Do not increase or decrease the capacity. How many relations does the ...
1
vote
1answer
65 views

How to find highest normal form of a relation, given its functional dependencies

Let's say that I have a relational model, defined as: $$X(A,B,C,D,E,F,G)$$ with the functional dependencies: $$f_1: \{A,B,C\} \to \{D,E,F,G\}$$ $$f_2: \{A,B\} \to \{C\}$$ Using this information I ...
0
votes
1answer
18 views

Functional dependencies , minimizing SUU->V

Can SUU->V or any functional dependency that contains two or more times each attribute be simplified to the same dependency with one attribute? So SUU->V becomes SU->V or STTT->Q becomes ST->Q ?
0
votes
0answers
26 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
41 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
29 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
32 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
21 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
25 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
45 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
54 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
28 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
43 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
22 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
26 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
90 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
48 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
44 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
30 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
32 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
49 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
19 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
9 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
65 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
27 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
41 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
79 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
79 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
31 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
50 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
106 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
95 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
38 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
33 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
74 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
53 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
95 views

How is Eventual Consistency (EC) better than Strong Consistency (SC) when N = 3, R=W=2 when SC gives better consistency gurantee in same config?

In dynamo paper, it says that in production most of the users set N = 3, R = 2 and W = 2. ...