Questions tagged [databases]
The databases tag has no usage guidance.
216
questions
20
votes
6
answers
3k
views
Why must uncommitted transactions be undone in backwards order?
I have a database log where some transactions win (they are committed before crash) and some lose (not committed yet). We learned in class that the losers' actions have to be undone backwards.
Is ...
- 201
13
votes
3
answers
4k
views
Who needs linearizability?
I've been reading about the differences between serializability and linearizability, which are both consistency criteria for replicated systems such as replicated databases. However, I don't know in ...
- 235
12
votes
2
answers
2k
views
Good snapshottable data structure for an in-memory index
I'm designing an in-memory object database for a very specific use case. It is single writer, but must support efficient concurrent reads. Reads must be isolated. There is no query language, the ...
- 223
9
votes
1
answer
216
views
Fixed-length decision-tree-like feature selection to minimize average search performance
I have a complex query $Q$ used to search a dataset $S$ to find $H_\text{exact} = \{s \in S \mid \text{where $Q(s)$ is True}\}$. Each query takes on average time $t$ so the overall time in the linear ...
- 221
8
votes
1
answer
2k
views
What is the difference between a R-tree and a BVH?
I've just read about R-Trees:
The key idea of the data structure is to group nearby objects and represent them with their minimum bounding rectangle in the next higher level of the tree; the "R" in ...
- 2,340
8
votes
1
answer
720
views
A relational algebra extended to model the full DML ("CRUD") domain
There are multiple references about the relational algebra for modeling queries (SELECT) but I have found very very little on the expanded algebra that would ...
- 547
8
votes
2
answers
4k
views
Linearizability and Serializability in context of Software Transactional Memory
I've been trying to grasp serializability and linearizability in the context of software transactional memory. However, I think both notions can be applied to transactional memory in general.
At this ...
6
votes
2
answers
134
views
5
votes
1
answer
298
views
How to find a basis which is guaranteed to need 9 or less characters to represent a 12 digits number?
I'm trying to map a 12 digit number into a fixed width file. For a number of reasons, it must be compressed in such a way that it is guaranteed to be less than or equal to 9 characters (alpha numeric ...
- 59
5
votes
1
answer
2k
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. ...
- 161
5
votes
4
answers
4k
views
When should you use the existential and universal quantifiers for Relational Calculus?
Could someone explain to me WHEN do you use existential and universal quantifiers for Relational Calculus?
Given this schema:
Hotel(hotelNo, hotelName, city)
...
- 201
5
votes
1
answer
566
views
blockchain database - why so redundant
I've become interested in blockchain databases. Everywhere I've read it said that each user has to have his/her own copy of database.
Why can't distributed blockchain database be 'distributed' to ...
- 151
5
votes
1
answer
868
views
n closest points in a set of lat/long coordinates
Here's my problem:
I have a website where people can search based on their location (which is converted to lat/long coordinates). I have many products stored in a database with their lat/long ...
- 205
5
votes
1
answer
116
views
Anonymization of dataset preserving unique identities
The $k$-anonymization paradigm (and its refinements) means to create datasets where every tuple is identical with $k-1$ others.
However I'm in a situation where people are in the dataset many times. ...
- 1,783
5
votes
1
answer
415
views
Differences between the OS and DB buffer pool?
How does the DB manage a pool of buffers when the operating system ends up controlling what's really in memory? For example, couldn't the operating system decide to evict a page frame from a DB's ...
- 151
4
votes
2
answers
199
views
Measuring availability from CAP theorem
I wonder how to check availability property from CAP theorem.
Consistency check is conceptually easy: if at least once somehow same query at the same time returns different results, then the system ...
- 103
4
votes
1
answer
27k
views
Difference between data duplication and data redundancy
My Computing teachers talk about data duplication and data redundancy in terms of databases as different things, but I'm struggling to differentiate them. The context is database normalisation, and in ...
- 217
4
votes
1
answer
3k
views
Time Complexity of Sort-Merge Join
According to this German Wikipedia article, the time required to merge relations $R$ and $S$ is $\in \mathcal{O}(|R| + |S|)$ if both relations are already sorted.
[Note: You don't really need to read ...
- 177
4
votes
2
answers
115
views
Is there a fundamental CS problem in ORMs that leads to N+1?
Many of us are familiar with N+1 problem when working with database queries. The problem was known before ORMs (Object-relational mapping frameworks) came around, but it seems that ORMs exacerbated it....
- 211
4
votes
1
answer
652
views
What actually is the concept of transparency? Why not call it Abstraction?
I searched this over Google few times but ended up with articles on transparency rather than an answer.
With relation to distributed database study(or distributed OS), what is the concept of ...
- 221
4
votes
1
answer
600
views
How to determine if a database schema violates one of the less known normal forms?
In database normalization, 1NF (no multivalued attributes), 2NF (all non-PK attributes depending only on PK attributes) and 3NF (all non-PK attributes depending on all of the PK attributes) are widely ...
4
votes
1
answer
247
views
Computing number of block reads given relational algebra statement
So I'm just starting to learn about query processing and such in databases and I'm having some trouble. I don't really understand how to compute the minimum number of block reads given a relation and ...
user7233
4
votes
1
answer
127
views
Algorithm for automatic/optimal database joins?
I'm curious if there is existing literature or well known algorithms out there for a problem I am working on.
Given a normalized relational database with valid foreign key constraints and a list of ...
- 205
4
votes
2
answers
12k
views
"At least one" clause in Relational Algebra
I'm fairly new to the syntax of relational algebra, and I'm having a hard time understanding how I could set a "at least one" clause.
Example: I have:
a table with books (listing the title, year ...
- 143
4
votes
0
answers
43
views
Any elegant approach to search where users have permissions on subset of records?
I work in Search and have seen following problem appear in different forms. There are many users in an enterprise; they have ability to create records. Each user has variable level of access to some ...
- 151
3
votes
1
answer
744
views
Are all databases reducible to this ultimate abstract database design?
I've designed a few databases in my time, and on more than one occasion the drive to abstract common elements from specific tables has led me to create generic top-level tables which contain those ...
- 133
3
votes
2
answers
7k
views
B-Tree and how it is used in practice
I understand what a B-Tree is (I already implemented a B-Tree in Java with insert and delete methods that preserve the invariant).
However I do not understand exactly how it is used for example for ...
- 121
3
votes
3
answers
2k
views
What is the difference between Transitive Closure and Join?
In database theory, there is a notion of transitive closure over relations. I am wondering if join operator over relations is also a special case of transitive closure?
- 31
3
votes
2
answers
1k
views
What are the different types of databases?
Is there is a study or classification available on different types of databases? (Examples include structured, unstructured, semi structured relational, object oriented, folksonomies, etc.)
- 175
3
votes
1
answer
975
views
Fastest way to search a word in a word list?
I have a word list like "English Open Word List" used to create word games.
The list is in txt file with space between words, like;
aa
aah
aahed
.........and so on.
I want to search it while typing ...
- 33
3
votes
1
answer
814
views
How to evaluate relations in a DAG?
To begin with: what I know of computer science is what friends have told me and what I've read on Wikipedia. Please correct me if I'm using some term wrongly, or if there is something I can clarify.
...
3
votes
1
answer
2k
views
Find similar vector by Locality Sensitive Hashing
I have many vectors in my database. They are in high dimensions such as:
$v_1$ : $\langle 23, 23, 1, 33, 103, 219, \dots \rangle$
$v_2$ : $\langle 92, 83, 1, 33, 239, 192, \dots \rangle$
...
I will ...
- 133
3
votes
2
answers
365
views
The finer details of Meek's STV
Meek's version of the Single Transferable Vote system [.pdf] is used in multiple big elections including those of New Zealand and Stack Exchange.
Demonstration (with thanks to the Department of ...
- 133
3
votes
1
answer
702
views
How to generate globally unique timestamps for transactions in distributed database systems?
According the paper [1] (Section 4), timestamp ordering (T/O) is a technique whereby a serialization order is selected a priori and transaction execution is forced to obey this order. In the following,...
- 9,441
3
votes
2
answers
1k
views
Rollback and Timestamp Ordering in Database
If we use the Timestamp Ordering for concurrency control in the following scheduling:
My TA says $T_2,T_3,T_5$ is Run and $T_4,T_5$ is Rollback. I think it's false. Is there any expert who could help ...
- 103
3
votes
1
answer
1k
views
Can a schedule with cyclic precedence graph still be serialisable?
We know Every conflict serializable schedule is serializable, but not all serializable schedules conflict-serializable. (*) so it means there is at least one serializable schedule that not conflict ...
- 381
3
votes
1
answer
79
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
2
votes
2
answers
106
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 ...
- 121
2
votes
1
answer
2k
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 ...
- 453
2
votes
2
answers
56
views
Restricting capabilities of admin role in database schema
Suppose I have to design database for learning management system. Which will going to have user having roles such as admin, teacher, tutor, student etc. In a system student can submit solution for an ...
- 83
2
votes
1
answer
125
views
Are there any types of distributed databases which allows untrusted peers, like Blockchain?
Are there any types of distributed databases which allows untrusted peers, like Blockchain?
If it exist, can I look its whitepapers and/or implementations?
- 165
2
votes
2
answers
2k
views
What is semantic closure?
In the context of database theory, what does semantic closure mean (linguistically speaking, i.e. not the mathematical definition)
If X is the set of attributes of $F$, then the semantic closure $F^+$...
- 23
2
votes
1
answer
26
views
How to simplify the query qualification?
Given the following DB and query :
Now if we need to simplify the query qualification, here is the answer from the book (Principle of distributed database systems, third edition) :
My question is in ...
- 23
2
votes
1
answer
624
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 ...
- 21
2
votes
1
answer
674
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 ...
- 55
2
votes
1
answer
494
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 ...
- 219
2
votes
2
answers
46
views
If a user confirmed a booking or transaction on the database system, but it failed and it falls over to the replica, what if the transaction is lost?
This is an overall system design and DBMS question:
If the user books a ticket or an item on a website, how do we solve the issue of confirming a ticket is sold to the user, but the main Database ...
2
votes
1
answer
144
views
How to do compare-and-increment different locations with in memory MVCC?
I'm reading the paper An Empirical Evaluation of
In-Memory Multi-Version Concurrency Control which is about implementations of MVCC for in-memory databases. Section 3.3 on Two-phase Locking (MV2PL) ...
- 205
2
votes
2
answers
37
views
Inferring used fields in return type
A common issue in app development is avoiding over-fetching of data, such as in this naive (pseudocode) example:
...
- 123
2
votes
1
answer
209
views
Does "serializable" also mean that it's lockable
Here's an final exam question for a Database Fundamentals class. I've read the book, stuff online.. I can't figure out if "serializable" also means that the schedule is ...
- 123