A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

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
1
vote
1answer
35 views

Thomas write rula andview serializability

Yesterday our Professor told in the class that Thomas Write rule ensures view serializability, but while surfing on this topic today on internet I am not able to find any information about that claim. ...
0
votes
0answers
9 views

Why only one sparse Index possible for any data file and two for dense index?

Why only one sparse Index possible for any data file and two for dense index? Can some one please explain in intuitive way?
0
votes
0answers
26 views

How does database indexing improve performance for lookup?

I read that indexing a database will improve its performance by assigning a number to each row to loop through. Even after indexing, to get the data at say row 1024, shouldn't the memory reader go ...
0
votes
0answers
16 views

Linking Subtype table to another table in EERD

I made this Enhanced Entity relationship diagram for my database project, but there is a problem that I have been mulling over. Over here, it can be seen that MANAGER is under the supertype of ...
0
votes
1answer
25 views

Is relational algebra a procedural, imperative, and/or declarative language?

In Database System Concepts 6ed, 6.2 The Tuple Relational Calculus When we write a relational-algebra expression, we provide a sequence of procedures that generates the answer to our query. ...
-2
votes
1answer
84 views
1
vote
1answer
48 views

Database Theory - Does the dependency preservation and lossless join properties hold for every decomposition of a relation into 3NF?

I was reading Database Systems, 6th ed by Ramez Elmasri and Shamkant Navathe. In the textbook they make a claim (in Chapter 15, section 15.2 Properties of Relational Decompositions) which I quote ...
4
votes
0answers
26 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$. ...
0
votes
1answer
19 views

Are entities in a many-to-many relation related individually?

I know in some many-to-many relationships, an entity is related to other entities on an individual basis. But is this always the case? For example, in the ...
0
votes
0answers
34 views

Complexity of Rearranging a Prefix Tree/Alternative Data Structures

Let $S$ be a subset of $[0,1]^l$. Is there some data structure that can represent $S$ and can perform the following operations/queries efficiently*? $ADD(s \in [0,1]^l)$ - operation which updates $S$ ...
0
votes
0answers
13 views

Does graph based protocol in DBMS suffer from starvation issues?

I know that graph based protocols require prior knowledge of access of data items. Besides when a transaction locks some data item in graph based protocol it also locks some unnecessary data items ...
0
votes
0answers
29 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
33 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 ...
2
votes
1answer
38 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
134 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
31 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
13 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
46 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
105 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
21 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
52 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
43 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
341 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
22 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
103 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
43 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. ...
4
votes
1answer
32 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
50 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
29 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
26 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
103 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
80 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
31 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
83 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
31 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
32 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
202 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
65 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
45 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
32 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
48 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
95 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
25 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
1answer
32 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
52 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
99 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
1answer
35 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
63 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
426 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
154 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 ...