As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [databases]

The tag has no usage guidance.

216 questions
Filter by
Sorted by
Tagged with
36 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$...
31 views

### Is there an algorithm for finding rows that have same sum of column values up to a threshold value?

I have a table like this (more specifically a nested dictionary) img a b c d e img1 0 0 1 0 1 img2 3 1 0 0 2 img3 4 0 0 0 1 img4 2 2 0 0 0 img5 0 0 0 0 2 img6 2 2 0 0 0 img7 1 0 0 1 0 img8 0 ...
61 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 ...
17 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?
81 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 ...
757 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
349 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 ...
207 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 ...
26 views

### Is there a sorting program or formula to sort and place individuals in classes based on preferences

I am looking for a formula or program to help place people in classes based on their preferences. The elements of the problem are: There are 30 class choices a student can pick from. There are 400 ...
205 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?
394 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 ...
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 ...
217 views

### Lookup complexity in B-trees [Database]

Given that: B = n/R blocks in the file 2d index records per block (blocking factor): 2d > R an extra block access from the index to the datafile I am not able ...
39 views

### What is Triangular bottom database?

For algorithm design course, the teacher gave a question, but i don't understand it at all, specially the triangular bottom database which i searched about it but couldn't find any result. However the ...
15 views

### Trying to figure out how to model the structure of a multilingual dictionary for several constructed languages (basically Wiktionary for my conlangs)

Okay, so, this will be quite a bit, sorry. I'm working on several constructed languages for a worldbuilding project. Up until this point, I have been using a spreadsheet to store the vocab; each row ...
52 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....
114 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 ...
44 views

### Algorithm to calculate the period where cumulative days within a rolling period exceeds a threshold

I'm struggling to think of the algorithm to transform one data set to another. The problem I'm looking at is creating a dataset of periods of time where cumulative days absent within a period (eg 30 ...
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. ...
1 vote
3k views

### how to get rows with more than 1 appearance of a specific column in relational algebra

I have a table like this: ...
1 vote
30 views

### Relational calculus: "Find all X with at least y amount of Z"

Assuming I have two relations: Supplier [ID (PK), Name, City, Country] and Item [ID (PK), Name, Department, Price, Stock, Supplier_ID (FK)] What would be the easiest way to determine the following ...
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?
505 views

### Static access pattern in Distributed Databases

The access patterns of user requests may be static, so that they do not change over time, or dynamic. It is obviously considerably easier to plan for and manage the static environments than would ...
29 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 ...
1 vote
7k views

### Difference between conflict serializability and view serializability

In my understanding both of them can be converted to serial schedules. (This helps with consistency by isolation property while also giving the performance boost by concurrency). I'm unable to ...
180 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: ...
160 views

### Algorithm to generate unique suggestions for creating an ID

Let's say I have a service where I provide user registration. The user chooses a ID. Now if I already have someone who is registered against that ID, I will inform the user that this ID is already ...
20 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. ...
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,...
57 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 ...
35 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 [...]&...
28 views

### Mongodb database model for password manager app

I'm doing a school project where I have to design a password manager app. I was wondering what the data model would look like. I know that I will have the user database to store authentication ...
155 views

### How are data structures used along databases?

I just completed a Data structures and Algorithms course in my university. I know how data structures work and how different DS are used to solve specific and to improve efficiency. I have also ...
1 vote
32 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 ...
84 views

### Efficient data structure supporting search query with contains

Suppose I have a table with millions strings in it as keys. What data structure can I use in order to efficiently support only queries like that? ...
300 views

### AVL Tree rotations

What size is the largest AVL tree for which an insertion could trigger a double rotation?
17 views

### What does it mean to 'provide' an API call?

So I have a database pre-loaded with data related to food recipes and the assignment says: 'Provide an API call that allows us to specify an ingredient or set of ingredients and return full recipes ...
155 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.
116 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 vote
73 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 ...
1 vote
262 views

### What are the essential differences and similarities among "data", "Information" and "knowledge" in the context of Computer Science?

The terms "data", "information" and "knowledge" are quite interchangeably used in Computer Science. Strictly speaking, they do carry a very different meaning. I want to know their precise meanings and ...
17 views

### where to get detailed information about some file format?

i want to learn about the structure of a .blk file but the problem is I don't know where to look for detailed information of this sort, most of the google searches I made gave me links to viewers.
201 views

### Creating a database of math questions and of answers and a front end for them

Need some guidance on where to begin. I am just learning python if it has any bearing. I want to create a page on my site where users log in, choose multiple topics from a list, choose between levels ...
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 ...
1 vote
22 views

### First normal form

I am confused about an aspect of the definition of first normal form in relational database model. Codd 1970 ("A Relational Model of Data for Large Shared Data Banks") defines normalization (...
1 vote
58 views

### constant relation in the base case of relational algebra

in the base case of the inductive definition of the operations of the relational algebra there is also the so called "constant relation" (as for example found in the definition here https://...
54 views

### What is meant by A determine BC in functional dependency. How the validity of this statement will be checked

We use notation A determines BC in a database for functional dependency. Same way we use equations in mathematics which shows dependency of variables. We have inference rules in logics, functions in ...
64 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 ...