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

What is the advantage of Rete algorithm compared to relational database engines?

Per my understanding, the Rete algorithm and relational database engines essentially solve the same problem: answering to a certain query about a (large) set of relational facts. To me, the Rete ...
0
votes
0answers
5 views

Transaction Management using MVCC concurrency algorithm

Good Morning, I am confused as to what logic should I apply to the current scenario. Both transactions are R-W, and according to my notes T2 should get an Xlock on A, while T1 would get an Xlock on ...
0
votes
0answers
14 views

Relation Closure for F+

$A \rightarrow B C$ $C D \rightarrow E$ $B \rightarrow D$ $E \rightarrow A$ I have these Relations for R={A,B,C,D,E} Now I have to calculate the closure $F^+$ and give the candidate keys I came ...
0
votes
1answer
26 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
21 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 ...
0
votes
0answers
26 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
31 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
30 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
40 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
77 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
177 views
1
vote
1answer
63 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
29 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
44 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
45 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
285 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
59 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
120 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
25 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
452 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 ...
1
vote
1answer
530 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
131 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
34 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
55 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
140 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
58 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
303 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
99 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
43 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
63 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
131 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
28 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 ...

1
2 3 4 5