Questions tagged [databases]
The databases tag has no usage guidance.
189
questions
0
votes
2answers
20 views
Resources about implementing a database table
I'd like to understand more how data can be stored on disk so it can be read quickly. I don't want to say database record because I'm not asking how to build a database. My question is closer to how ...
0
votes
0answers
11 views
Lost Update Problem and Recoverability and Commits
Does lost update problem must have Read first?
Can Lost-Update problem occur in:
1] Conflict Serializable
2] Strict Recoverable
I'm totally confused about basic.
R2(X) R1(X) W1(X) C1 W2(X)
Does this ...
0
votes
1answer
36 views
Find number of candidate keys given non-trivial functional dependency X->Y, where X is some set of attributes and Y is some prime attribute
In a relation R, if X is some set of attributes and Y is some prime attribute such that X uniquely determines Y is a non-trivial FD. Then is it true that R has at least two candidate keys?
For ...
0
votes
0answers
12 views
What is an example of Polyinstantiation in a bank
What is an example of polyinstantiation which could adversely affect a process in the operation of a bank
1
vote
0answers
19 views
What is the state of the art of full text searching across languages?
I have looked at a few papers on this such as this, and it basically says that full text search is all about English with few resources for languages without spaces between words (like Chinese or ...
0
votes
0answers
21 views
Mathematical representation of value set of a composite attribute
Following is a paragraph on page 70 of Fundamentals of Database Systems by Ramez Elmasri:
Mathematically, an attribute $A$ of entity set $E$ whose value set is
$V$ can be defined as a function from $...
0
votes
0answers
9 views
Dynamic replica membership in a distributed causally-consistent database
Given a distributed causally-consistent database (a replicated key-value store where writes are propagated in causal order, in the style of this paper), what are common techniques for "scaling&...
0
votes
0answers
35 views
External Sorting - Calculate passes with different number of disks
Let suppose that we have a file with n = 10^6 records. The block size is B = 10 records and we have available main memory m = 20 blocks. (Sorting with MergeSort)
a) If we have 1 disk find minimum ...
0
votes
0answers
13 views
Cardinality of weak relationships
I want to ask what is the cardinality of a weak relationship like the loan payment relationship shown below, will be ? I am guessing it should be many to many.
0
votes
1answer
18 views
Is persistence a property of a database?
I was having a discussion in another forum on this topic, and I couldn’t get a satisfactory answer. Originally, a statement was made that a redis data store couldn’t be considered a database because ...
0
votes
0answers
10 views
Anthology of term indexing
I'm interested in finding the most appropriate analogy of a data structure to describe organization/access of genetic information in cells. We humans have 23 pairs of chromosomes - each pair ...
1
vote
0answers
25 views
How does 2PL protocol apply to schedule of multiple transactions?
If a schedule follows the two-phase locking protocol, does every transaction have to follow 2PL, or is it the case that all locks must appear all unlocks in the whole schedule?
I am a little confused ...
1
vote
1answer
31 views
Does upgrading after all locks and before all unlocks violate 2PL?
2PL's rule says:
Upgrading of lock (from S(a) to X (a)) is allowed in growing phase.
But what if upgrading lies after the last lock and before the first unlock? Does it still count "in the ...
1
vote
0answers
19 views
What does mean by the independent columns in 4NF normalization?
For a table to satisfy the Fourth Normal Form, it should satisfy the following two conditions:
It should be in the Boyce-Codd Normal Form.
And, the table should not have any Multi-valued Dependency.
...
0
votes
1answer
22 views
Example for Database architecture
PHPMyadmin is stated as a 3 tier database architecture.How is this possible,Isn't it a 2 tier architecture.What are the real world examples of 1-tier and 2-tier architecture.
1
vote
0answers
19 views
In index allocation scheme, what parameters does the maximum size of a file depends on?
My understanding is as follows:
...
1
vote
0answers
29 views
What does the three schema architecture of DBMS refer to?
This architecture contains three layers or levels of the database management system:
External level
Conceptual level
Internal level
Can some one explain to me with a practical real example so that ...
0
votes
0answers
15 views
Why is Read(Q) timestamp is not checked when a transaction issues a command reading Q?
Consider a concurrent schedule of two transactions $T_1,T_2$:
$R_x(Q): T_x$ Reads $Q$
$W_x(Q): T_x$ Writes $Q$
$S:R_2(A),R_1(A),W_1(A),W_2(A)$, this schedule is not conflict serializable.However, if ...
0
votes
1answer
29 views
how two phase commit ensure serializability
Two phase commit is used in distributed transaction. For example, a client sends a transaction to two databases with a coordinator.
step1: client get a global transaction id from coordinator
step2: ...
0
votes
1answer
17 views
Bits needed to send parameters of perfect hash functions
Suppose that there is a server that has $n$ files. The server is used to construct a perfect hash function for those files and then the computed parameters will be sent to a user. These parameters ...
2
votes
1answer
98 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
86 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
47 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
26 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
2answers
36 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
18 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
19 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
28 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
15 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
14 views
Serializable schedules but not view serializable
I know that to check if a given schedule is serializable we can test for either view serializability or conflict serializability. But do serializable schedules exist which are not view serializable?
0
votes
1answer
56 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., ...
1
vote
0answers
18 views
Number of tables required to decompose a function into BCNF
I know this is not a question answer posting site, but for sake of explaining my doubt I will like to post a question
Say you are given table like
R(A,B,C,D,E,F)= {AB→C, BC → A, AC→ B , B → D , D→...
0
votes
1answer
36 views
Third Normal Form and Boyce Code normal form
I know that this is not a question answer site but for sake of explaining my doubt I have to post the entire question..
Consider the following statements.
...
1
vote
0answers
79 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
86 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
92 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 ...
1
vote
1answer
178 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
1answer
44 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
67 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
464 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
62 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
54 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
30 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
1k 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
670 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
46 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
472 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
141 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
58 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 ...