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
1answer
24 views

Probability of data loss for mirrored,3 disk system

I am reading the book Database Systems the Complete Book 2nd Edition. A slightly modified Question 13.4.5 states: Suppose we use three disks as a mirrored group; i.e., all three hold identical ...
1
vote
1answer
15 views

Space-efficient data structure for analytical querying of multiple branching evolutions of a dataset

Problem Description I have a data state space: a set of data sets, each of which can be modelled as a collection of arbitrary key-value pairs. These data sets are each a branch of evolution of a ...
-1
votes
0answers
15 views

Studying database management engines

I am primarily a backend dev with Java and C# as my primary tools of the trade. Lately I've been trying to delve into the inner workings of a DBMS or even a key-value store. I've narrowed down my ...
0
votes
0answers
22 views

Doesn't Linearizability implies Serializability?

Serializability is a concurrency scheme where the concurrent transaction is equivalent to one that executes the transactions serially. In Linearizability, Once write completes, all later reads should ...
0
votes
1answer
18 views

Incremental View Maintenance for projection

I was reading https://www2.cs.duke.edu/courses/spring02/cps296.1/lectures/08-view.pdf Or in the paper "Incremental Maintenance of Views with Duplicates," by Griffin and Libkin, SIGMOD, 1995. figure 2....
0
votes
0answers
30 views

Need help in understanding these relational algebra queries

I just finished reading about operators in relational algebra and tried to solve this problem. But I dont even understand what the first statement is doing. From what I know, $π$ (project) is a unary ...
1
vote
1answer
29 views

Algorithm for determining whether 2 entities of some feature are the same?

I'm trying to think of a way to do approximate joins between 2 rows in a data table. Like for example lets say I have a row where the person name is "John Doe" but then another data table uses a ...
1
vote
0answers
52 views

What are the common practices to weight tags relations?

I am working on a webapp (fullstack JS) where the user create documents and attach tags to them. They also select a list of tags they are interested in and attach them to their profile. I am not a ...
1
vote
1answer
37 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
12 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
29 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
26 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
50 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
153 views
1
vote
1answer
55 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
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$. ...
0
votes
1answer
20 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
26 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
30 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
39 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
39 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
194 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
33 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
14 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
53 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
114 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
214 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
46 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
443 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
121 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
33 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
54 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
27 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 ...
1
vote
1answer
102 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
34 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 ...
1
vote
0answers
35 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
50 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
266 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
86 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
39 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
61 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
120 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
26 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
39 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
58 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, ...

1
2 3 4 5