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
0answers
20 views

A necessary condition for a relation to be in 2NF but not in 3NF is that some non-prime attribute must be determined by a non-prime attribute

I will state the complete question now, since it did not fit in the title. Is the statement given below correct? A necessary condition for a relation to be in 2NF but not in 3NF is that some non-...
0
votes
1answer
27 views

Relation is in 2NF or not?

Consider a relation R(A,B,C,D,E) and the only FDs, ABD->C BC->D CD->E These are the only 3 FDs. I want to know if the above relation is in 2NF or not. According to the definition of 2NF, a ...
1
vote
1answer
30 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
1answer
45 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
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
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
18 views

RDF | If something is a rdfs:subClassOf of :Q can you infer it is also rdf:type :Q?

Given: :P rdfs:subClassOf :Q Can you infer the following?: :P rdf:type :Q I do not think you can, but I am not fully sure. ...
1
vote
1answer
40 views

Why we don't consider cycles in path problems?

I'm working on my research and I found that for directed graphs, there are many algorithms trying to solve shortest path problem(like Dijkstra, Bellman‐Ford algorithm), but few is to get all paths(...
0
votes
0answers
35 views

How to find all tuples in which some attribute appears more than three times

im havin trouble with this exercise. I have a table like this and i can only use relational algebra without aggregate function like sum, count, etc. Name | x a ~~ 1 b ~~ 2 c ~~ 1 d ~~ ...
1
vote
0answers
17 views

Distributed Serializable Snapshot Isolation

I was wondering if there is any research on distributed transaction algorithms for Serializable Snapshot Isolation. I found Binnig, C. et al.: Distributed snapshot isolation: global transactions pay ...
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
0answers
204 views

Using count() in Relational Algebra

Sell (Bar, Beer) I want a table in which the first column has the name of the beer and the second has the total number of bars which sell that beer, but I have no idea how to use count () in the right ...
0
votes
0answers
14 views

why you couldn’t use mmap to manage a rdbms buffer pool - or the whole rdbms itself just like NoSql stores?

why you couldn’t use mmap to manage a rdbms buffer pool - or the whole rdbms itself just like NoSql stores? I see that Cassandra, Hbase, Elastic do use mmap so why not use the same strategy for an ...
1
vote
1answer
52 views

Are intersection and union redundant? Possibility to get smaller output without negation?

I've just started learning relational algebra, so I'm reading a lot of articles for this topic. Not so long ago I've encountered two statements that seem to be quite weird to me. ∩ and ∪ (...
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
29 views

How do we sort the chunk in the first pass of external merge sort?

Referring to the 9th page of a slide, when we use multi-pass multi-way external merge sort on a file with $N$ pages using $B$ buffer pages, in "pass 0" we'll read a chunk of $B$ pages into ...
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
0answers
19 views

Find candidate keys - What are the steps

I have these following functional dependencies I figured out: DM -> RA RDT -> AM AD -> RM I got with a software to calculate what the candidate keys were ...
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 ...
0
votes
0answers
12 views

Is view equivalence unidirectional?

I am learning about serializability and I am not sure that if view serializability bidirectional or unidirectional. What I am meaning that, if S is view equivalent to S', is it always true that S' is ...
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
38 views
0
votes
1answer
33 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
10 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
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
1answer
28 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 ...
3
votes
1answer
33 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
49 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
29 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....
1
vote
1answer
57 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
55 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
50 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
1answer
176 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. The tuple ...
-2
votes
1answer
225 views
1
vote
1answer
87 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
28 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
23 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
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
69 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 ...
3
votes
2answers
98 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
471 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
149 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
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
2 3 4 5