Databases & Relational Algebra
Theoretical background for SQL. RDMS, ANSI-SPARC Architecture, relational algebra. SQL is a relational language in that it is founded on the relational model – more specifically on relational algebra. However, it is not a pure implementation of it; some features of the relational model were left aside, whereas some features not belonging to the relational model were added. Good slides about b-tree indexes: http://users.informatik.uni-halle.de/~brass/dbi05/c4_index.pdf.
63 flashcards · Computer Science · by lakesare
What does DBMS stand for?
Database Management System
What does DBA stand for?
Database Administrator
What's meant by intensional and extensional definitions? (with definition for bachelor as an example)
These are 2 key ways in which objects a term refers to can be defined. intensional - gives the meaning of a term by specifying necessary and sufficient conditions for when the term should be used (bachelor - unmarried man) extensional - defines by listing everything that falls under that definition (bachelor - [a list of all bachelors]) In logic and mathematics, an intensional definition gives the meaning of a term by specifying necessary and sufficient conditions for when the term should be us…
What's database intension VS extension?
intension: database schema extension: database instance
What are 3 levels in ANSI-SPARC Architecture?
The database schema consists of three types of schemas, one for each level of abstraction: • External schemas - reports and screens designed to aid individuals in doing their specific jobs. • Conceptual schema - all the definitions should only take the logical structure of the data into consideration. Implementation aspects, and user views, should be disregarded. • Internal schema - defines the physical records, methods of representation, index implementation, etc. Examples: External: An outsid…
What does DCL stand for?
Data Control Language Controls access to data.
What does DDL stand for?
Data Definition Language Defines data types such as creating, altering, or dropping tables and the relationships among them.
What does DML stand for?
Data Manipulation Language Performs tasks such as inserting, updating, or deleting data occurrences.
What does DQL stand for?
Data Query Language Allows searching for information and computing derived information.
What's cardinality of a relation?
The number of rows (i.e. tuples) represents the cardinality of the relation.
What's degree of a relation?
The number of columns (i.e. attributes) represents the cardinality of the relation.
What 2 types of domains are there in DBMS?
Built-in, or system-defined data types – such as integer/real/string User-defined data types, or domains CREATE DOMAIN creates a new domain. A domain is essentially a data type with optional constraints (restrictions on the allowed set of values). The user who defines a domain becomes its owner.CREATE DOMAIN us_postal_code AS TEXT CHECK( VALUE ~ '^\d{5}$' OR VALUE ~ '^\d{5}-\d{4}$' ); CREATE TABLE us_snail_addy ( address_id SERIAL PRIMARY KEY, street1 TEXT NOT NULL, street2 TEXT, street3 TEXT,…
Definition for a relation in relational algebra. A relation cannot contain duplicate tuples. Each tuple is unique within a given relation. This also means that each tuple is uniquely identifiable. The smallest set of attributes that can be used to uniquely identify all the tuples in a relation is called a candidate key. Tuples are unordered. Statements like ‘the fifth tuple’ make no sense (this is also a reason why the uniqueness criterion is vital). Attributes are unordered.
Name 3 differences between relation (as in RM) VS table.
The relational model (RM) for database management is an approach to managing data using a structure and language consistent with first-order predicate logic, first described in 1969 by English computer scientist Edgar F. Codd, where all data is represented in terms of tuples, grouped into relations. In terms of the relational model (RM) of databases, a table can be considered a convenient representation of a relation, but the two are not strictly equivalent.
What SQL sublanguages are used here?
DDL (Data Definition Language) DML (Data Manipulation Language) Originally based upon relational algebra, SQL consists of many types of statements, which may be informally classed as sublanguages, commonly: a data control language (DCL),a data query language (DQL),a data definition language (DDL),a data manipulation language (DML).
What's a data dictionary of the database?
Data dictionary is tables that describe the database: schemas, integrity rules, security rules, etc. The data dictionary is itself a part of the database, and so it is also represented by means of relations (usually tables).They are called system tables, in order to differentiate them from user-defined tables. MySQLData dictionary tables are protected and may only be accessed in debug builds of MySQL. However, MySQL supports access to data stored in data dictionary tables through INFORMATION_SC…
When is language said to be relationally complete?
Language is relationally complete if any relational algebra query can be expressed in it. A database language is said to be relationally complete if it is at least as powerful as relational algebra, that is, if any expression from relational algebra can be implemented in the language. SQL is relationally complete; in fact, it has significantly more expressive power than relational algebra.
What is the candidate key?
Candidate key - is a set of attributes that uniquely identify a database record. Each table must have one or more candidate keys. Primary key - is one of the candidate keys we select to be the primary key. A table contains only one primary key, but it can contain several candidate keys.
What is entity integrity?
The entity integrity constraint specifies that each relation must have at least one candidate key. This constraint is always satisfied within the relational model. Every relation has at least one candidate key – since a relation cannot contain duplicate tuples, the complete set of attributes of a relation is always a possible candidate key.
If a candidate key consists of only one attribute, it is said to be simple. If it contains more than one, it is called _______.
composite
Primary key VS alternate key?
A table can have many candidate keys (simple or composite). We select one of the candidate keys to be our primary key. All other candidate keys are alternate keys. Technically, a primary key constraint is simply a combination of a unique constraint and a not-null constraint. Since a given relation can have more than one candidate key, there is a choice of which should be used for tuple addressing. The chosen key is called the primary key of the relation, with the others called alternate keys.
Name 2 properties a candidate key must have (in relational algebra).
The uniqueness property – no distinct tuples have the same value for CK. The irreducibility property – no proper subset of CK has the uniqueness property (which means that the set MUST be minimal). Keep in mind that even though these are the requirements in relational algebra, the primary key in postgresql e.g. doesn't need to be irreducible :-)
Here is a definition for the foreign key in Relational Algebra: What's meant by 'given two relations'? What's meant by 'defined on the same domains'? What's meant by 'in some tuple in R1'?
relation: is table domain: is type tuple: is row Note that the reverse of the second requirement above is not necessary – there may well exist values for the candidate key that are not matched by any value of foreign key.
What's functional dependency?
When in a single relation R, - there is a set of columns X, that predicts exactly the set of columns Y.
Find a functional dependency in this table. The situation modelled is that of college students visiting one or more lectures in each of which they are assigned a teaching assistant (TA)
We notice that whenever two rows in this table feature the same StudentID, they also necessarily have the same Semester values. StudentID → Semester. Note that if a row was added where the student had a different value of semester that the functional dependency, FD, would no longer exist. This means that the FD is implied by the data as it is possible to have values that would invalidate the FD. Other nontrivial functional dependencies can be identified, for example:{ StudentID, Lecture } → TA{…
What are the left-hand and right-hand side of the functional dependency (FD) and called? { StudentID, Lecture } → Semester
left-hand side: determinant right-hand side: dependent
What's multivalued dependency?
Multivalued dependency occurs when two attributes in a table are independent of each other but, both depend on a third attribute. A multivalued dependency exists when there are at least three attributes (like X,Y and Z) in a relation and for a value of X there is a well defined set of values of Y and a well defined set of values of Z. However, the set of values of Y is independent of set Z and vice versa. 1) Figure out if A determines a set of values for B, 2) Figure out if A determines a set o…
Name 2 types of partitioning.
Vertical partitioning - putting different columns into different tables Horizontal partitioning - putting different rows into different tables There are numerous advantages to the horizontal partitioning approach. Since the tables are divided and distributed into multiple servers, the total number of rows in each table in each database is reduced. This reduces index size, which generally improves search performance. A database shard can be placed on separate hardware, and multiple shards can be…
What's sharding in databases?
Sharding is a horizontal partitioning, but it does this across potentially multiple instances of the schema. Horizontal partitioning splits one or more tables by row, usually within a single instance of a schema and a database server. Each partition forms part of a shard, which may in turn be located on a separate database server or physical location.
Name 2 types of horizontal partitioning.
Range partitioning - selects a partition by determining if the partitioning key is within a certain range. An example could be a partition for all rows where the "zipcode" column has a value between 70000 and 79999. It distributes tuples based on the value intervals (ranges) of some attribute. In addition to supporting exact-match queries (as in hashing), it is well-suited for range queries. For instance, a query with a predicate “A between A1 and A2” may be processed by the only node(s) contai…
We wish to compute SELECT * FROM authors INNER JOIN books ON authors.id === books.author_id; What's inner and outer relations here?
authors: outer relation books: inner relation
[mechanisms of data protection] What's data recovery?
Data recovery of a database is the ability to restore its content and functionality following a system failure to an earlier and correct state. The mechanisms of data recovery are based on the concept of the transaction. Implementation. Most modern RDBMS implementations support transactions. However, there may be some restrictions. For example, to use transactions in MySQL, you will need to ensure that your tables use the InnoDB storage engine, not the older MyISAM. The DBMS (or a part of it) c…
What's transaction logs?
Transaction log (also transaction journal, database log, binary log or audit trail) is a history of actions executed by a database management system used to guarantee ACID properties over crashes or hardware failures. Physically, a log is a file listing changes to the database, stored in a stable storage format. In general, a DBMS is likely to copy some or all of any database into a buffer in volatile memory and perform operations on those copies – largely for reasons of speed. At certain point…
What's write-ahead logging?
In computer science, write-ahead logging (WAL) is a family of techniques for providing atomicity and durability (two of the ACID properties) in database systems. The changes are first recorded in the log, which must be written to stable storage, before the changes are written to the database. In a system using WAL, all modifications are written to a log before they are applied. Usually both redo and undo information is stored in the log. The purpose of this can be illustrated by an example. Ima…
What's database checkpoint?
A checkpoint writes the current in-memory modified pages (known as dirty pages) and transaction log information from memory to disk and, also records the information in the transaction log. For performance reasons, the Database Engine performs modifications to database pages in memory-in the buffer cache-and does not write these pages to disk after every change. Rather, the Database Engine periodically issues a checkpoint on each database. At certain points in time (at the checkpoint), the syst…
How to write a transaction in postgres?
In Postgres: In MySQL: -- 1. start a new transactionSTART TRANSACTION;-- 2. Get the latest order numberSELECT @orderNumber:=MAX(orderNUmber)+1FROM orders; -- 3. insert a new order for customer 145INSERT INTO orders(orderNumber, orderDate, requiredDate, shippedDate, status, customerNumber)VALUES(@orderNumber, '2005-05-31', '2005-06-10', '2005-06-11', 'In Process', 145);-- 4. commit changes COMMIT;
Imagine database resides on multiple machines. What technique is used to execute a transaction in such case?
Two-phase commit. The DBMS has to implement global COMMIT and ROLLBACK statements. When a global COMMIT is issued, the DBMS guarantees that all the operations are committed, even in the case of a crash somewhere in the network. If any single resource manager fails, then the global transaction must be rolled back. To achieve this global task, a special system component, the co-ordinator, is needed.
Describe 2 phases in the Two-phase commit transaction technique.
Phase 1: The co-ordinator prepares each resource manager that is involved in the transaction by sending a ‘get ready’ message. On receiving this message, each resource manager must force write in their log the description of all the operations it has performed. Once this information is recorded on non-volatile storage, it will be possible to commit or roll back the operations even if a crash occurs. If the force writing process is completed successfully, the resource manager sends an OK to the…
Which transactions needs to be undone, and which can we repeat?
T2, T4: repeat. T3, T5: undo. Transactions of type T2 and T4 have to be repeated based on the information in the log. This is because they completed successfully, but we cannot guarantee that the results of their operation were saved to permanent support.Transactions of type T3 and T5 must be undone, because they were not successfully completed at the time of the crash. The log does not contain sufficient information in order for them to be re-initiated. LSN - Log Sequence Number
Name 3 problems caused by the concurrent access to the same data.
Inconsistent analysis problem. Lost update problem. Uncommitted dependency problem.
[concurrent access] What's inconsistent analysis problem?
The inconsistent analysis problem is caused by a transaction querying data that another transaction is changing at the same time. Inconsistent analysis happens when a transaction reads a data which another transaction is still updating. It is almost the same problem with lost update, except that the final database state is actually consistent, because that other transaction does not modify the data. Nevertheless, the query result is still incorrect.
[concurrent access] What's lost update problem?
The lost update problem arises when two transactions update the same data, but each fails to take the action of the other into account.
[concurrent access] What's uncommitted dependency problem?
When we rely on the transaction that will be rollback. As-yet-uncommitted changes from one transaction are relied on by another transaction. This causes no problems if the transaction is successfully committed, but if it is rolled back, then the values used by the second transaction may never have been part of a consistent database state. Suppose today we have data that is being updated and eventually rolled back in a transaction. A dirty read occurs when another transaction, running concurrent…
What's a serialisable execution?
An interleaved execution of a set of transactions is serialisable if it produces the same result as some serial execution of the same set of transactions, one at a time. Nonetheless, there is one important aspect of this solution – it shows us that any method of carrying out a set of operations that has the same results as this concurrency-free solution is, by definition, free of concurrency problems.
The locking mechanism provides a means for preventing multiple transactions from accessing the same data in a way that might give rise to inconsistencies. What are these 2 types of locks: exclusive (write) locks shared (read) locks Before a transaction uses the data it refers to, it must acquire permission to use it. Permission may be granted or refused depending on the type of access required and whether the data is currently being used. If permission is granted, then the data will have a lock…
Exclusive lock - required for any transaction that needs to modify a certain tuple. Once a transaction has acquired an exclusive lock on a tuple, no other transaction can access it – even for reading. Shared lock - required by any transaction that needs to retrieve data from a tuple, but does not need to modify it. There can be any number of shared locks on a tuple at any given time. However, if a transaction requests an exclusive lock, the request will be refused if there are any shared locks…
A transaction that only needs to read the value of a tuple must first acquire a shared lock on that tuple. A transaction that needs to modify or update a tuple must first acquire an exclusive lock on that tuple. If a transaction is refused a lock on a tuple because another transaction has a lock on it already, then it goes into a ______ until the lock is released. All locks are normally held until the transaction they were granted for is completed – a COMMIT or ROLLBACK statement releases the l…
wait state When more than one transaction is waiting for a lock on the same tuple, a sub-module of the concurrency control module called the scheduler decides on the order in which to serve them. The scheduler should ensure that no transaction waits forever for its lock to be granted. Uncommitted dependency problem solved through locking.
What's a deadlock?
When 2 transactions wait on each other to complete. Lost update problem
How does the system resolve deadlocks?
System maintains a directed graph of which transaction waits for which transaction to complete. Since a deadlock will never break on its own, the system must identify such situations and resolve them. The most common way to detect deadlocks involves each system maintaining a directed graph that represents which transaction is waiting for which other ones to complete.
Will this deadlock resolve? wait-for directed graph
Yes. Transaction A depends on B and C to complete, C is waiting for D which in turn is waiting for B. In this case, the sequence B then D then C then A will complete without any need for intervention.
How will the system resolve these 2 deadlocks?
By rolling back some victim transaction. Once a deadlock is identified, the system terminates one of the transactions involved by rolling it back. The terminated transaction is called the victim. Rolling back the victim results in it releasing the locks that it holds, resolving the deadlock. Usually, the victim is automatically restarted after the deadlock has cleared. How the victim is chosen is outside the scope of this subject guide.
What's Discretionary Access Control (DAC) VS Mandatory Access Control (MAC)?
Discretionary Access Control - user with suitable access privileges can change the permissions of other users. Mandatory access control - access is controlled by the administrator, users can't override it. By contrast, discretionary access control (DAC), which also governs the ability of subjects to access objects, allows users the ability to make policy decisions and/or assign security attributes.MAC-enabled systems allow policy administrators to implement organization-wide security policies.…
A phone book is like having an index on someone's ___________?
Last name
[MySQL] How to get the execution plan?
Just add EXPLAIN to whatever query you're executing.
Clustered index VS non-clustered index?
Clustered index - leaf nodes contain actual rows, it's how the table is physically stored. In MySQL, a clustered index is automatically created if it does not already exist when we add a PRIMARY KEY constraint to some column/s. Non-clustered index - only store pointers to the rows in their leaf nodes.
The syntax to create index in PostgreSQL/MySQL is CREATE INDEX my_index_name ON my_table USING my_method (my_column_1, my_column_2); Name 2 methods of database indexing (my_method).
btree hash In PostgreSQL, my_method can take up values of: btree, hash, gist, and gin.In MySQL, my_method can take up values of: btree, hash (however, default storage engine InnoDB only allows btree index method). Both Postges, and default MySQL’s storage engine (InnoDB), use btree as their default index types.
[database indexing] What does 'btree' stand for?
Bayer and McCreight never explained what, if anything, the B stands for: Boeing, balanced, broad, bushy, and Bayer have been suggested. McCreight has said that "the more you think about what the B in B-trees means, the better you understand B-trees." Here are the properties of the Btree by Knuth’s definition: Every node has at most m children. Every non-leaf node (except root) has at least ⌈m/2⌉ child nodes. The root has at least two children if it is not a leaf node. A non-leaf node with k chi…
[btree] What's 7?
A key. One btree node contains multiple keys. Here is an example of the Btree, that could be an index on the students.age column.Each index key (this is what’s meant by ‘key’ in 4th property in Knuth’s definition, here it’s e.g. 7, 16, 1...) represents the value of the column we’re indexing by, - a particular age.
How many keys can this btree node have?
amount of children - 1 (=2). One of the properties of the btree by Knuth is: non-leaf node with k children contains k − 1 keys. Each internal node of a B-tree contains a number of keys. The keys act as separation values which divide its subtrees. For example, if an internal node has 3 child nodes (or subtrees) then it must have 2 keys: a1 and a2. All values in the leftmost subtree will be less than a1, all values in the middle subtree will be between a1 and a2, and all values in the rightmost s…
Name 3 places MySQL looks into to create a clustered index.
PRIMARY KEY defined by you first UNIQUE NOT NULL column defined by you if nothing works, - MySQL creates its own hidden index GEN_CLUST_INDEX.
[indexing] When to use b-tree indexing VS hash index?
Btree index: =, >, >=, <, <=, or BETWEEN operators, and for LIKE operator if it does not start from %. A B-tree index can be used for column comparisons in expressions that use the =, >, >=, <, <=, or BETWEEN operators. The index also can be used for LIKE comparisons if the argument to LIKE is a constant string that does not start with a wildcard character.Hash index: =. Hash indexes are used only for equality comparisons that use the = operators (but are very fast). They are not used for compa…
What is the drawback of creating an index on a table?
Each index defined on a table: slows down CREATE/UPDATE/DELETE operations takes up space on disk and in OS. Doesn't slow down SELECTs.
Super key Composite key Query optimization Functional Dependency Determinant
Super key is any set of columns that, taken together, reference a unique tuple. Composite key is a candidate key that consists of more than one field. Query optimization is a process by which the database tries to convert the query written by us into the most fast execution plan. Functional Dependency is when one set of fields (X) in a relation uniquely determines another set of fields (Y) in this relation. Determinant is a set of fields X in a functional dependency described above. Dependent i…
Primary key VS candidate key?
Candidate key is a MINIMAL set of fields that can be used to identify a tuple. Primary key is an app-specific concept, - we choose one of the candidate keys to serve as the primary key, in order to indicate which candidate key we should usually query the db by. Candidate key is a super key from which you cannot remove any fields. Can there be two tuples with identical primary keys in the same relation? No! Can there be two tuples with identical candidate keys in the same relation? No!