Questions tagged [database-theory]
the analytic study of ways in which information is efficiently and effectively stored to and retrieved from computer systems.
263
questions
0
votes
0
answers
17
views
Secondary Memory Data Structures and allocation strategies for intermediate query results
Despite a huge amount of literature regarding table representation and indexing in secondary memory (also including database books), I found no information on how relational databases represent ...
- 101
0
votes
0
answers
16
views
Proof that 2 phase locking produces order preserving Conflict serializable schedules
In the book Transactional information systems: theory, algorithms, and the practice of concurrency control and recovery there is a theorem stating that Gen(2PL) ⊂ OCSR. Can some one help to guide on ...
- 25
0
votes
1
answer
33
views
ER model cant understand where I am wrong?
I am studying this ERD:
The bank and the customer are obviously strong entities because they are a bank and a person.The bank branch is clearly a weak entity because it depends on the bank ...
- 97
1
vote
1
answer
144
views
How are blind writes recoverable in a transaction schedule?
Consider the following schedule -
T1 T2
R(A)
W(A)
R(A)
W(A)
Commit
Commit
I understand that this schedule is non-recoverable, because if ...
-4
votes
1
answer
62
views
Real world example of complex foregin key references
Give a real world, normalized example where table T1 has primary key (A, B), T2 has primary key (B, C) and T3 has primary key (A, C) and table 4 has a primary key (A, B, C) where (A,B) is a foregin ...
- 75
0
votes
0
answers
37
views
0
votes
0
answers
20
views
Practical applications of finite model theory to databases
I have heard that finite model theory has connections to database theory. Is there an example of where this database theory could be used by programmers developing database applications?
- 287
0
votes
1
answer
55
views
Can a CPU instruction be split into 2 inputs?
Let's say there was a CPU with an input bus of 4 bits and the 4 bits are the opcode then the next 4 bits are the operand. It would just be an 8-bit instruction split in two. Is this possible and how ...
- 9
-1
votes
1
answer
39
views
2NF decompositions are dependency preserving?
I have read that 1NF, 2NF and 3NF decompositions are lossless and dependency-preserving.
Consider this example on a relation $R(A,B,C,D)$ with functional dependencies set as $FD =${ $AB \rightarrow CD,...
- 108
0
votes
1
answer
47
views
Check whether a decomposition is in 3nf
In a database systems course, we have been presented with the following definition for third normal form (3NF):
A relation $R$ is in 3NF means:
a nontrivial dependency $A_1,\dots,A_n\to B_1,\dots B_m$...
0
votes
0
answers
23
views
Implement this as Attribute or Entity Set?
I am creating a database on students' interests using the Entity-Relationship Model for a University assignment.
Should I implement the circled stuff as attribute, or an entity set?
0
votes
1
answer
78
views
Checking if Schedule is recoverable
Consider the following schedule S.Is S conflict–serializable? Append the commit operations of these transactions at the end of the
schedule in an appropriate order such that S is recoverable. How many ...
- 13
0
votes
1
answer
83
views
Efficient storage of overlapping sets
I have a bag of sets which overlap, and I am looking for an efficient (if possible, optimal) way to leverage that overlap to store those sets with minimal space requirements. For example, consider ...
- 101
1
vote
4
answers
63
views
How to index a table for fast intersection?
For example (and this is not my use case), imagine there is a set of 50 000 random natural numbers represented in decimal with 8 digits (in the range 00 000 000 to 99 999 999). We could index the set ...
- 13
-1
votes
1
answer
47
views
How to derive selections from a series of numbers
I am sure this question has been asked, but I was unable to search for it in a manner that would give me the solution. So I will present it here.
I seen this in another database years ago, and I want ...
0
votes
1
answer
68
views
Way to call and explain: "potentially infinite set of attributes" in databases
This is a bit of a theoretical question. I would like to know how to call the principle described below, in proper computer science terms, or math terms.
Let's say we have a database in which one ...
2
votes
0
answers
32
views
How can we reduce the spatial complexity of intermediate indexes in relational databases at execution time?
In relational databases, what are the practical or theoretical ways to reduce the size and spatial complexity of intermediate indexes or tables* at execution time (so for example to reduce the size of ...
- 21
0
votes
0
answers
31
views
Which normal form is it in and How can we change it to 3rd and BC normal form
There is a relational schema :-
person (id, name, phone no, address, email, position)
so there will be the following functional dependencies
...
0
votes
0
answers
21
views
Primary key's all field should contain value or not?
After reading a lot of materials related to the Primary key and Unique key, I am in doubt. Let us consider a primary key (AB) in table R (ABCDE). AB together can not be null as AB is a primary key. ...
- 178
1
vote
2
answers
364
views
How do SQL databases query non-indexed columns?
I'm looking for some resources on what happens on the low-level with databases.
I've found that indexed data is looked up using b+ trees, but could not find anything on non-indexed columns.
Is there ...
- 11
0
votes
0
answers
68
views
Is this decomposition in 3NF?
I have the following question:
Consider relation R(A, B, C, D, E, F, H) with the following functional dependencies:
A --> D, AE --> H, DF --> BC, E --> C, H --> E
Consider three ...
2
votes
0
answers
36
views
Primary File Organization in DBMS - Files of ordered records (sorted files)
"Fundamental of Database Systems", 3rd ed. by Elmasri and Navathe, page 136 says:
"We can physically order the records of a file on disk based on the values of one of their fields [...]&...
- 21
0
votes
1
answer
101
views
What are other alternatives to version control on structured or large and highly volatile data?
Say you are editing a document like a 1000 page book. There are 20 authors all working furiously to edit the book. Every day they are merging their changes 2 or 3 times with the main branch. According ...
- 2,163
2
votes
1
answer
121
views
How do distributed joins work in a distributed relational database system?
I have been looking around for a few days trying to find a clear and concise description of how, at a technical/implementation level, how distributed joins work, but haven't found much. The best so ...
- 2,163
0
votes
1
answer
113
views
decomposition to BCNF
Given $R$=($A,B,C,D,E,G$),
And $F_c$={$A$$\rightarrow$$E$ ,$E$$\rightarrow$$ACD$ ,$BD$$\rightarrow$$E$, $CD$$\rightarrow$$B$}
Candidate keys are: $GA, GE, GDB, GCD$
Lets say I pick the FD $A$$\...
- 29
1
vote
0
answers
35
views
Advantages to create Male and Female entities separate from User rather than making gender a property in a database?
The screenshot is from Georgia Tech's CS-6400. The instructor was talking about inheritance of Sub-Types and Super-Types.
My question is, why are Male and ...
- 13
0
votes
1
answer
67
views
How does partial word lookup work in an inverted index?
I know that an inverted index is a mapping from words -> documents. In the database I'm using, I'm able to do a search for ...
- 3
1
vote
1
answer
73
views
Histogram representation of a database
I'm reading though The Algorithmic Foundations
of Differential Privacy and the authors define a database in a mathematically convenient way. Unfortunately I'm a little confused about what the ...
3
votes
1
answer
89
views
Automated Query Equivalence Solver (MongoDB)
The query-equivalence problem is undecidable. However there are theorem provers that attempt to solve instances of undecidable problems. I am curious how I could go about using an automatic theorem ...
- 31
1
vote
0
answers
72
views
Understanding the behavior of Conflict Serializability and View Serializability with respect to blind writes
I have seen that most standard college textbooks of Database Management Systems use this method to classify whether a schedule is view serializable or not.
I know the definitions of Conflict ...
- 1,092
1
vote
0
answers
573
views
Division in tuple relational calculus
$ \newcommand{\Set}[2]{%
\{\, #1 \mid #2 \, \}%
}$
I've been trying to find how to express relational division operation in tuple relational calculus. The only thing I found is this presentation ...
- 129
-1
votes
1
answer
313
views
Intuition for a projection in tuple relational calculus
Let's have a relation $R = (name, surname, age)$. I want to obtain a new relation with only the $name$ attribute. In relational algebra I would simply do $\Pi_{\mathrm{name}}(R)$ but in relational ...
- 129
2
votes
1
answer
127
views
Using B+Tree to implement index, when the index-key size and the data-block size are of the same order
I want to implement an Index using a B+Tree as the underlying data structure. The index will have to support key sizes which are of order of my block size, what means I cannot save all the key as a ...
- 249
0
votes
1
answer
142
views
Figuring out the equivalence between two definitions of "transitive functional dependencies" and intuition behind the intended meaning of definition
The definition given below is present in the exercise of the text Database System Concepts by Korth et. al.
Let $\alpha$ and $\beta$ be sets of attributes such that $\alpha \rightarrow \beta$ holds, ...
- 1,092
1
vote
1
answer
80
views
Is this a mistake in the textbook? Fundamentals of Database Systems 7th ed
Aggregation is an abstraction concept for building composite objects from their
component objects. ... the possibility of combining objects
that are related by a particular relationship instance into ...
0
votes
1
answer
142
views
Order of query execution in the SQL
When a user writes a SQL query it needs to be scanned, parsed and validated. The question is in which order these three operations occurs in the process?
Scanning, Parsing, Validation or any other ...
- 17
1
vote
0
answers
757
views
Is it possible to convert any relational algebra expression into a relational calculus expression?
Let's for the sake of simplicity only focus on tuple relational calculus.
Every relational algebra query can be broken down into the 5 atomic operations - projection, selection, set union, set ...
- 129
0
votes
2
answers
320
views
Can databases use data structures/algorithms to respond to arbitrary queries?
Let's say that I am interested in discovering the smallest 5 numbers in a set of numbers.
In SQL, this would work:
...
- 111
0
votes
1
answer
70
views
In database buffering why is it important : no writes to a block (which is to be moved from the disk buffer section of main memory) be in progress?
I was going through the concept of database buffering from the Database System Concepts text by Korth et. al where I came across the excerpt below.
The rules for the output of log records limit the ...
- 1,092
0
votes
1
answer
119
views
WAL rule requires only the undo information in the log have been output to stable storage, and permits the redo information to be written later
I was going through the "write-ahead logging (WAL) rule" from the Database System Concepts text by Korth et. al, where I came across the following excerpt:
Strictly speaking, the WAL rule ...
- 1,092
2
votes
1
answer
87
views
Why does CLRS refer to the disk parts as pages rather than blocks?
I recently decided to review the B-tree chapter (chapter 18, p 486 in 3ed) in Introduction Algorithms, and found that they call pages what I always referred to as blocks or clusters:
In order to ...
- 121
0
votes
0
answers
93
views
How to efficiently search a list of data structures with filtering support
I'm working on a project where I need to create search functionality that can efficiently search a list of data structures like:
...
0
votes
1
answer
59
views
Is this relation in Boyce-Codd's Normal Form?
I thought I understood BCFN until I bumped into this example from my course slides.
A relation in a library database contains what books are currently borrowed by what users.
The relation contains ...
- 163
1
vote
0
answers
38
views
Which of the query approaches are more efficient?
There are two relations, registered(participant,topic) and fee(participant,amount).
The primary key for registered is (participant, topic) and the primary key for fee is participant.
The premise is ...
1
vote
2
answers
40
views
Are joins/pullbacks of bloom filters possible?
An interesting advantage of bloom filters over hash tables, that they share with bitarrays, is that they support taking unions & intersections of sets by simply doing bitwise or & bitwise and ...
- 131
1
vote
0
answers
19
views
Why two phase locking requires second phase not able to acquire lock for another object?
I wonder why two phase locking is designed in a way that as long as you release a lock, you cannot acquire any lock anymore, even for a lock on a different database object.
Can't the scheme be relaxed ...
- 183
0
votes
0
answers
27
views
Hash tables for storing data in an application that supports partial search
Is a hash table a good data structure for storing data in an application that support partial search such as "select * from MyTable where name like 'John%'. If not, what is?
I would have thought ...
- 143
2
votes
0
answers
27
views
Optional filters in relational database
I'm trying to create a procedure in MySQL/MariaDB with optional filters for each participating table. Assuming the tables are $A, B, C, \ldots$, each table may or may not be filtered, and the result ...
- 1,111
1
vote
1
answer
75
views
Data model and database schema
I need to test my understanding of the difference between the data model and database schema. According to my understanding, the data model is a description of how the data will be stored and the ...
- 43
2
votes
0
answers
77
views
Database Access Cost Estimate - Linear Search over non-key attribute
How does one estimate the access cost for the below query given that the data is sorted according to a non-key attribute, that the data is not uniformly distributed across all possible values of said ...
- 123