Questions tagged [databases]
The databases tag has no usage guidance.
175
questions
-3
votes
0answers
14 views
Query in relational algebra and relational calculus
Using the following relations: Emp(eid, did, skill)
When writing the following query in relational algebra and relational calculus, how can I?
Im trying but I cannot find the answer, let me know how ...
2
votes
1answer
47 views
Efficiently storing and modifying a reorderable data structure in a database
I'm trying to create a list curation web app. One thing that's important to me is being able to drag-and-drop reorder items in the list easily. At first I thought I could just store the order of each ...
0
votes
1answer
80 views
Databases and B-Trees: What are Keys and how are they related
I confused about the description & definition of "key" occuring as terminology for databases and b-trees.
In first case dealing with theory of databases a key is defined as a choice for ...
1
vote
1answer
42 views
What is the maximum number of indices one can create on a table with N columns?
Say, I have a database table with $N$ columns. What is the (theoretical) maximum number of indices I can create on that table? For $N = 1,2,3$ it's easy enough to calculate the answer $(1, 4, 15)$, ...
1
vote
1answer
18 views
Confused between 2 phase locking and 2 phase commit
I understand that both algorithms are very different, but what I don't understand is whether they achieve the same thing in the end. 2PC is for atomic commits and 2PL is for serializable isolation. ...
1
vote
0answers
7 views
how to get rows with more than 1 appearance of a specific column in relational algebra
I have a table like this:
...
0
votes
0answers
12 views
Parsing text, then searching it: one entry per position, vs. 1 JSON column per text
I have a Rails application using Postgresql.
Texts get added to the application (ranging in size -- as short as a few words, to as long as, say, 5,000 words?).
The text gets parsed, both ...
0
votes
0answers
15 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
0answers
16 views
How to create a database of meta-model transformations with real data?
I am currently working on meta-model transformation and the coevolution of models. I have already done some kind of a state of the art, and the next step in my research would be to collect some (...
0
votes
1answer
21 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
14 views
Evolving graph rewritings between trees (representing JSON) and graphs (representing relational database schemas)
I have in input different, say 100, types of trees with labeled nodes (representing JSON files). I need to transform the information contained in the trees into graphs with labeled nodes (representing ...
0
votes
1answer
36 views
Need help understanding the tuple relational calculus
We say that a query in a TRC is a statement of the form $\{T: P(T)\}$, where $T$ is a tuple variable and $P(T)$ is a formula.
Now my question is, what are the possible tuples $T$ to be tested i.e., ...
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
45 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 ...
1
vote
0answers
62 views
Using relational algebra to express all with a condition
I encountered this question while revising for my finals exam on database theory.
The following database contains information about car repair workshops. The following tables are used:
$$Workshop(\...
1
vote
1answer
65 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 ...
0
votes
1answer
33 views
DBMS: MINIMUM NUMBER OF TABLES REQUIRED TO REALIZE THIS ER MODEL
I was following a discussion on a forum where they have posted a question like this-->
Some people are saying that we can merge A,B,C in a single table and m:n relation of A and C in another table ...
0
votes
0answers
22 views
Consistency CAP vs ACID
I understand that the consistency property specifies what values can be read, depending on what has been written before. For instance, if we consider a simple abstract read/write service. It enjoys ...
0
votes
0answers
33 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 ...
1
vote
1answer
82 views
Does basic 2 PL always ensure conflict serializability?
While going through the DBMS book by Korth, it was mentioned :
" For a set of transactions, there may be conflict-serializable schedules that
cannot be obtained through the two-phase locking ...
0
votes
0answers
128 views
What is difference between r, and r(R) in DBMS?
Sorry, for asking such a basic question.
I am really confused between small 'r' and 'r(R)' being interchangeably denoted as 'relation' or 'relational instance'. I know, that R is a relational schema. ...
0
votes
0answers
43 views
What is the difference between Instance of a relation and Instance of a relation schema?
Following question was asked in the exam. The correct answer to this question is 2. But, I feel that it is a wrong answer. Option 2 is an example of instance of a relation and not an example of ...
0
votes
1answer
40 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
45 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 ...
0
votes
1answer
335 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
61 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
50 views
In a DBMS what are the implementation details that make set operations faster than cursors?
What are the low level implementation details that make set based operations exponentially faster than iterative processes, like cursors?
At a memory level how does a set operation "touch" the data ...
1
vote
1answer
26 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
583 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
560 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
0answers
44 views
Doubt on Lossless or Lossy Decomposition
Consider a relationĀ $R\left ( A,B,C,D,E \right )$ and functional dependencies areĀ
$F=\left \{ AC\rightarrow B,C\rightarrow D,A\rightarrow E,C\rightarrow B \right \}$
Relation $R$ is decomposed into ...
2
votes
1answer
420 views
Why do OS and DBMS have their own synchronisation mechanisms, when OS can alone do it and it sits at the bottom of DB?
I know that synchronization is important in the OS, but why do we need a separate topic synchronization and concurrency in the DBMS? The OS concentrates on program synchronization while the DBMS ...
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 ...
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 ...
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
60 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
334 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]...
1
vote
0answers
27 views
Why don't RDBMS use a quorum based solution to do failover
For RDBMS viz. MySql, PostgreSql a common solution for scalability and high availability is to run a primary instance as master that is a read-write instance and one or more read replicas. If the ...
0
votes
1answer
132 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
3answers
708 views
Functional Dependencies
Let relational schema R(A,B,C,D,E,F,G,H,I).
The functional dependencies are: A -> BC, AD -> BE, C ->F , A->F , D-> E
Find the number of non-trivial functional dependencies ? I know that R has only ...
0
votes
0answers
124 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
36 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 ...
0
votes
1answer
22 views
Maximum join of relations
I have a question as follows
Consider the relations $r1(P, Q, R)$ and $r2(R, S, T)$ with primary keys $P$ and $R$ respectively. The relation $r1$ contains $2000$ tuples and $r2$ contains $2500$ ...
0
votes
1answer
535 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
220 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
56 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 ...
-1
votes
2answers
747 views
Is it possible to do a NULL comparison in Relational Algebra?
Please consider the following question given in a booklet:
I have read about databases from Database System Concepts - by Henry F. Korth, but never saw an instance where we could do a NULL comparison ...
1
vote
1answer
203 views
Raft algorithm: What's the data format of `term`?
Time is divided into terms, and each term begins with an election. After a successful election, a single leader manages the cluster until the end of the term. Some elections fail, in which case the ...
1
vote
0answers
40 views
normalization: how does nf work?
I once did normalization for my Computer Science project, and I had to turn 0NF to 1NF, 2NF and 3NF.
What must we actually do to convert 0NF to 1NF, 2NF and 3NF? Must we rearrange the information and ...
