Computer Science notes ⇒ Relational Databases and Query Languages

Different types of system exist based on their main focus:

• Processing systems - these were mainly covered in MSD last term (e.g., the mobile phone case study)
• Information systems - data is a central artefact and is the most important aspect of the system (e.g., payroll systems)
• Control systems - exist to monitor/control a piece of equipment, e.g., a lift. They have very different types of concerns to other types of systems and are covered in modules such as RTS.

RDQ is primarily concerned with information systems. We can consider two components of information systems: the database - supported by a DBMS, the database is always in a valid state and does more than just holding data (e.g., it performs validation and verification); and transactions, which are atomic operations (which is challenging, as you have to deal with crashing and errors, as well as handling concurrency), defined using basic operations and are based on data constraints and business rules.

Data needs to exist by itself, not just as part of a program.

		Data Content and Structure	Database Applications
Phase 1	Requirements collection and analysis	Data Requirements	Processing Requirements
Phase 2	Conceptual Database Design	Conceptual Schema Design (DBMS-independent)	Transaction and Application Design (DBMS-independent)
Phase 3	Choice of DBMS
Phase 4	Data Model Mapping	Logical Schema and View Design (DBMS-dependent)
Phase 5	Physical Design	Internal Schema Design (DBMS-dependent)
Phase 6	System Implementation and Tuning	DDL (Data definition language) and SDL statements	Transaction and Application Implementation

Database were traditionally specified using an entity-relationship diagram, but modern specifications use conceptual class models with restrictions, although we refer to class models in a database context as an entity and associations become relationships. Transactions are specified using collaboration diagrams, which are rarely complex.

All entities must have the basic operations of create, remove, modify attribute and link, and inheritence can only be of attributes and associations, not methods. Inheritence is either total, where the parent class is only used for inheritence or partial, which is normal inheritence. Multiplicities are traditionally restricted to 0, 1 and * to give us one-to-one, one-to-many and many-to-many relationships. To allow other UML multiplicities, we use participation limits.

When considering attributes, we can consider composite attributes, ones that can be broken down further (e.g., an address) and also multi-valued attributes, where several pieces of data can exist for one attribute (e.g., telephone number, could have daytime, evening, mobile, etc...).

Data integrity exists to define what it means for data to be valid. Data integrity rules can be expressed in OCL, B, Z or using structured English. We can consider three types of integrity concerns: structural integrity, such as multiplicity and participation limits; business rules - constraints that arise from the way a business works; and inherent integrity, which is related to the database paradigm, and are only relevant during design.

Different types of constraints for business rules exist:

• Domain - Although it is too early to give specific type constraints, we can give high level abstractions of the types allowed, e.g., say that age has a maximum value of 26, rather than age is an int.
• Inter-attribute - A restriction on the values of an attribute in terms of the values of one or more attributes of the same class. The inclusion of derived attributes generally lead to this kind of constraint.
• Class - This is limitations on a class, e.g., on how many instances of the class may be allowed.
• Inter-class - The is similar to inter-attribute constraints, but involve attributes of different entities.

Verification and validation are important components of any high quality engineered solution. The kinds of quality control issues that can arise in information systems specification are summarised in the V-model, as studied in MSD. Here, we only deal with validation and verification of specification models.

As we use direct translation to approach the construction of the database, it is essential that the models produced are verified internally and checked against each other, as well as against the requirements. The whole topic of validation can be discussed under requirements engineering, but here we only look at it from the point of view of data modelling.

Data models represent the requirements for a system's data structure, and should represent all of the data required by the system. Data models should aim to reduce redundancy - ideal data models should not have any redundant structures or data. Class diagram checks are based on traditional data model checks, and uses a technique called resolution and the following check list:

• Component checks:
  • Is every class linked to at least one other?
  • Are all multiplicities defined?
  • Are all names unique?
• Relationship checks:
  • Are only simple associations and simple subtyping used?
  • Apply resolution checks to all many-to-many associations to pick up missing or misplaced attributes
• Redundancy checks:
  • Check that all classes and associations are needed
  • Ensure there is a good reason that classes linked by associations with multiplicity 1 or 0..1 at both ends cannot be merged
  • Where two classes are linked by more than one sequence of associations, that some of the associations are not redundant
  • Subclasses of a single class are not disjoint

Some checks can be carried out automatically with a tool, but others require insight into the application.

Resolution Checks

Transaction model checking simply is ensuring that:

• all necessary components are represented
• all class operations are called by the manager
• indirect messages relate to the creation and deletion of links
• messages that call set-based operations have sets as targets
• consistency of guards.

Finally, model cross checking of the class and collaboration models leads to elaboration of, at least, the class model. It checks that there are enough transactions to handle the data and there is enough data to carry out the transactions. The basic checking processes are that all called operations are available in the classes and all data in guards and parameters must be available. Extra checks such as general checks, integrity checks and navigation checks could also be used.

To check there are enough transactions, you need to ensure that every class has transactions to create, delete and change the attributes of an instance, and every association has transactions to create and delete links. Therefore, for every role whose multiplicity does not include 0, any transaction that creates an instance of the opposite class must also create a link to that instance and any transaction that deletes the last or only link to the opposite class must also delete the instance of the opposite class.

Integrity checks ensure that business rules are properly expressed, and the simplest of them are the structural integrity rules imposed by the diagram, so you have to ensure that the structural integrity is correctly captured in the class model and the collaboration diagrams enforce structural integrity.

Navigation checks ensure that all possible questions can be answered by the data model. Connection traps occur when the structure looks fine, but does not yield answers to the needed navigations. Navigation checks consist of considering each of the required transactions of the system, and making sure that they can all be implemented in the system. You do need to make sure that by solving connection traps, unjustifiable closed loops are not introduced.

Quality of Information Systems

There are many different definitions of a database. Most focus on the features of the universe of discourse (what the database is holding), purpose, related sets of data, organised persistent data, shared access and central control and transactions.

Databases need not necessarily be computerised (the first ones for example were paper based), but for the context of this module, we will only consider computerised databases. Early non-computerised databases used manual catalogues and procedures, and in addition to the obvious inconveniences, there was the major problem of duplication, and there was no established database theory.

With the rise of computing in the 1970s, limited computing resources became available and database theory became developed. Databases were typically implemented in files using file handling programs, but duplications and manual checks were still needed. Maintenance was also difficult and there is very little support for security.

Moving into the 1980s, some theory became established and relational databases were introduced. Simple networks of computers became available and DBMSs are a hot topic in research.

ANSI/SPARC Architecture

We can consider the components of a DBMS as demonstrated in the diagram below:

DDL (the data definition language) can be considered as an unofficial entry point to the DBMS as it provides us with direct access to the data dictionary. Most applications communicate using DML and DQL (data manipulation and data query languages). A second raw DQL approach is often used by database administrators where they need quick access to data that a transaction does not necessarily exist for. The only "official" access to the data should be through application programs using transactions.

Ultimately, the goals of a DBMS are:

• persistent storage of programs and data structures in a common format
• controlled, minimal redundancy
• representation of complex data structures (with integrity constraints)
• controlled multi-user access
• prevention of unauthorised access
• management of security features
• provision of backup and recovery facilities

Users of a DBMS

Relational Databases

Relational algebra is used in the design of transactions, and forms the conceptual basis for SQL. It consists of operators and manipulators, which apply to relations and give relations as a result, but do not change the actual relation in the database.

The operators come from the mathematical operators od dealing with sets:

Relational Operator	Meaning
union(R1, R2) → R3	R3 has all the tuples from R1 and R2
difference(R1, R2) → R3	R3 has all the tuples of R1 which are not tuples of R2
intersection(R1, R2) → R3	R3 has all the tuples that are in both R1 and R2
product(R1, R2) → R3	The intension of R3 is the concatenation of those of R1 and R2. The tuples of R3 are those of the cross product of R1 and R2

We can also consider the manipulators of relational algebra:

Relational Manipulator	Meaning
restrict(R1; predicate) → R2	R2 is a relation comprising only of the tuples of R1 for which the predicate is true
project(R1; predicate) → R2	R2 is a relation comprising only the attributes of R1 specified in the predicate
join(R1, R2; predicate) → R3	R3 is a relation comprising of tuples from R1 and R2 joined according to a condition on common attributes specified in the predicate
divide(R1, R2; predicate) → R3	R3 is a relation formed by identifying tuples in R1 which match the values of attributes in R2, according to the predicate, and returning the values of all other attributes of the identified tuples; R3 is the relational image of R2 on R1

These operations can be joined to be able to give more interesting queries, e.g., "What are the numbers of the flights that go to Bangkok?" could be represented by: project(restrict(FLIGHT; Destination = Bangkok); FlightNo).

It is often simpler to represent complex queries diagramatically, such as for "What are the identifiers of the holidays that Ana has booked?":

Another type of query to consider is the existential query, where we look for the existance of a connection between two relations. The solution for this is to restrict, then join and project. This is not very efficient, however, as joins and products create huge relations. A good approach to use is to get the queries correct and then think about adding projects and restricts before joining to optimise the operation. For existance between multiple relations, existantial queries can be included in one another.

In the case of universal queries, we are not interested in specific customers or packages (for example), and we can use the divide manipulator to implement these. For divide(R, S) to be well-defined, the intension of S must be a proper subset of the intension of R. The resulting relation has an intention of the attributes a of R that are not in S and an extension of the tuples t of the projection of R to a such that, for every tuple u of S, tu is in R.

Some queries can be handled as either an existential or universal query, however.

Relational algebra is not computationally complete, however (you can not write general queries), and other problems can occur - such as finding out the number of tuples in a relation.

See LPA for
predicate calculus

Relational calculus is an alternative to relational algebra and forms another conceptual basis to SQL. We can think of relational algebra as being prescriptive (how - a procedural style similar to programming languages), whereas relational calculus can be thought of as descriptive (what - a nonprocedural style based on predicate calculus). Which form you use is a matter of style.

The relational algebraic expression project(restrict(FLIGHT; Destination = Bangkok); FlightNo) can be expressed as relational calculus using a set comprehension: f : FLIGHT f.FlightNo where f.Destination = Bangkok, or perhaps the more familiar notation { f : FLIGHT | f.Destination = Bangkok ∧ f.FlightNo }.

The basic syntax of relational calculus is tuple-specification where predicate. The tuple specification and the predicate use range variables, and the tuple specification is a list of range variables and attribute selections and the predicate is over the range variables in the tuple specification. The result of this is a relation composed of the tuples of the form tuple-specification such that predicate is true.

Existential queries in relational calculus are implemented using a range variable for the target relation, an existential quantification, and one quantified variable per relation from the anchor up to, but not including the target relation and equalities to establish the starting points and links.

To do universal queries, we use a universal quantifier with a range variable for the target relation, a quantified range variable for the anchor relation and a quantified predicate, which is an existential query to establish a connection between the anchor and the target.

We do however have the same problems as we had with relational algebra, where general search algorithms can not be implemented - this is due to a restriction in predicate calculus.

A variant of relational calculus is domain calculus, where predicate logic is defined over domains, rather than relations.

In conclusion, relational calculus is useful for defining relations and for optimisation (a huge number of algebraic laws exist). For the evaluation of language, relational calculus is relationally complete, and relational algebra is a convenient target to implement the calculus, and an algorithm exists which can transform any calculus expression into an algebra expression.

Normalisation is a technique to eliminate duplicated data and unnecessary attributes. It is applied during the design stage and ensures that all relations comply with restrictions imposed by normal forms - a succession of rules. Normalisation helps reveal relations and avoid inconsistency during transactions.

The result is not necessarily efficient (e.g., duplicated data might be used to speed up a search), and any changes in the physical design for efficiency reasons should be recorded.

Dependence among attributes needs to be controlled, and anomalous results when inserting, updating or deleting data need to be reduced, as well as eliminating spurious tuples when joining relations. Dependencies such as one value determining another (functional dependence) are not recorded in the design, which is a problem.

The need for normalisation was proposed by Codd very early after he recognised a need for a technique to remove dependencies. The first three levels of normalisation were suggested in 1972 and subsequently, Boyce and Codd added a further level (BCNF). Other research has produced further forms, although these are concerned with dependencies other than those the first three and BCNF (such as between tuples, relations and their projections), which are concerned with the dependencies between attributes of a tuple.

An attribute B is functionally dependent on another attribute, A, if, at any time, knowing the value of A uniquely determines the value of B. We write this as A → B, where A and B can be lists of attributes.

Functional dependencies exist between the primary key and other attributes, and normalisation removes any other functional dependency. To identify the functional dependencies, we use the domains and integrity constraints, rather than a particular extension - which can only show the absence of a functional dependency. In relational databases, we can consider a universal relation, which is a join of all relations in a database, and attribute names are prefixed by the name of their original relation.

Given a set of functional dependencies, we can infer others, known as Armstrong's axioms:

• Reflexivity - if Y ⊆ X, then X → Y
• Augmentation - if X → Y, then XZ → YZ
• Transitivity - if X → Y and Y → Z, then X → Z
• Composition - if X → Y and X → Z, then X → YZ
• Decomposition - if X → YZ, then X → Y and X → Z
• Pseudo-transivity - if X → Y and WY → Z, then WX → Z

This is sound and complete, and only reflexivity, augmentation and transitivity are enough. Any functional dependencies satisfied by the axiom of reflexivity are considered trivial, and do not say anything special about the application.

Derived attributes represent required calculations (e.g., age from birth date) and are recorded in the data dictionary. They characterise a functional dependency, but are not part of the relational model and prevent full normalisation.

To start normalisation, you need to determine non-trivial functional dependencies and at the end of each level of normalisation, relations should be presented complete with their primary and foreign keys.

First Normal Form

Second Normal Form

Third Normal Form

Boyce-Codd Normal Form

Algorithms for normalisation work by decomposing the non-normalised relations into two or more normalised relations using the methods explained above. Some authors propose the use of normalisation through decomposition as the central technique to design a relational model, starting from the universal relation and the functional dependencies. This preserves dependencies, as all dependencies of the universal relation can be inferred from the dependencies that only involve attributes of a single relation, and this is reasonably easy to enforce. This approach is not often taken in practice, though.

We can also consider the property of lossless-join, where decomposed relations can always be joined back using the join operator of relational algebra on the primary and foreign keys, to exactly the contents of the original relation, and no spurious tuples should be introduced by the join.

It is always possible to normalise a relation to 3NF to obtain a collective of relations that preserve depenency and the lossless-join property, and it is always possible to normalise a relationship to BCNF and maintain lossless-join, however it is not always possible to obtain relations that satisfy all the properties. When this occurs, the problem should be recorded and a compromise made.

SQL (Structured Query Language) is the most popular relational database language. It implements both a DDL and a DML and concerns itself with the creation, update and delation of relations and properties based on relational algebra and calculus. It is typically included in host applications, or conventional computer programs.

SQL is based on SEQUEL (Structured English QUEry Langauge) which was developed by IBM in the 1970s for System R. In 1986, ANSI developed a standardised version of SQL based on IBM's SEQUEL, and in 1987, ISO also released a version, which was updated with integrity enhancements in 1989, and then again in 1992 (SQL-92) and 2000 (SQL-99, sometimes referred to as SQL-3). The current version of SQL is SQL-2003 and adds object-relational features and XML, etc...

There are many variations and specialised versions of SQL, e.g., ORDBMS SQL for object-relational products was marketed by DB2, Oracle and Informix, Geo-SQL is used in various GIS products, and TSQL2 is a temporal query language much cited in research. They do all have a common core, but other varients include direct SQL and embedded SQL, differences in access privileges and concurrency and not stored SQL, which includes the usual control commands.

Tables

Integrity Constraints

Views

SQL Statements

SQL is used with other programming languages, so we need to consider how to distinguish SQL commands from our standard program and how to map data from the database to host-program data structures and how to determine the start and end of a transaction.

One implementation in C is the call level interface specification, which is where most of the database queries are handled in the preprocessor. Other languages, such as Java, PHP and modern implementations of C use the core library and drivers to access it (e.g., ODBC or JDBC).

CLI statements in C look like: EXEC SQL query. Shared variables are declared between EXEC SQL BEGIN DECLARE SECTION and EXEC SQL END DECLARE SECTION, and then are referenced in the query by prefixing it with a colon, e.g., EXEC SQL SELECT count(custno) INTO :numcust FROM booking. We need to make sure that we have correct data types (or weird things will happen when we start casting), and these need to be checked.

When we are dealing with multiple tuples, it is often easier to use a CURSOR, which is declared as EXEC SQL DECLARE ptr CURSOR FOR query, and then EXEC SQL OPEN ptr, FETCH FROM ptr into :var (repeated as many times as necessary) and then finally EXEC SQL CLOSE ptr.

Transactions in C are started by an EXEC SQL CONNECT host username IDENTIFIED BY password command and then either an EXEC SQL COMMIT command, or EXEC SQL ROLLBACK. Either way, the connection should then be released.

In other languages, which are based on an API (such as the JDBC in Java or mysqlclient in C), distinguishing SQL commands is not an issue as it is not compiled in advance. However, a more flexible and complex approach of processing results is needed. In JDBC, we can use commands such as DriverManager.getConnection(...), creating a statement is done with stmt = conn.createStatement(), and then the statement is executed using rs = stmt.executeQuery(...). The result set rs is then processed with command such as rs.getInt(i), rs.getString(i), etc. Finally, the result set is closed with stmt.close() and the connection closed using conn.close().

When designing security measures for databases, we should start from the assumption that agents (people) intend harm, this contrasts with safety, which exists to prevent accidents (although the two can complement each other in areas).

In databases, security stems from the need for military and commercial secrecy, and was typically implemented using encryption and physical isolation, however, with the rise of multi-user databases, this is not feasible. With the advent of Internet connected databases, there is even less control over who might try to access the database, the number and type of these concurrent accesses and what parts of the database can be accessed.

Threats are potential entries that could be used to cause harm, whereas an attack is the exploitation of a threat. Possible threats could come from authorised users abusing their privileges and the possibility of unauthorised access. The potential consequences of a successful attack include a breach of security, integrity and availability. One of the key tasks in database security is to identify threats. Countermeasures to attacks include access control, inference control, flow control and encryption.

Good database systems should have a security policy and mechanisms in place to implement the security policy. The security policy typically consists of a set of high-level guidelines and requirements based on user needs, the installation environment and any institutional and legal constraints. The mechanisms are a set of functions that apply the security policy and can be implemented in hardware, software and human procedures. Mechanisms could either be mandatory controls which can not be overridden and discretionary controls, which allows privleged users to bypass restrictions.

To capture mechanisms that address policies, we have objects (entities that need to be protected) classified by a scale of security. Subjects request access to objects, and they need to be controlled. Subjects are classified by a scale of truth.

Military Model

Security should be considered early on in the database development process, before the specification stage. General things that should be considered include questions such as:

• How private is the data?
• How robust and rigorous does the subject need to be?
• Are the requirements the same for all data?
• What is the security policy?
• What is the appropriate model to be applied?
• Does the development need tailoring?

If we know the DBMS at this stage, then the facilities of that should be considered as part of the analysis.

During the specification stage, we should consider access control. Groups who have common access rights need to be identified and assigned to roles, and then transactions should be annotated with access requirements. For each class, roles should be assigned responsibilities for creation, deletion and manipulation of data. When designing verification plans, testing should include cases to check that security is enforced and for each transaction that an intersection of roles is responsible for the constituent operations.

If any inconsistency does come up in the consultation (e.g., someone does not have the roles required to run all of the parts of a transaction - i.e., they do not have access to a class that needs data deleting when a transaction requires that data to be deleted), then further consultation with the client is needed, and it can often be worked around with, for example, views.

Relational theory contains nothing about security in databases, however SQL has implemented some access control facilities using the GRANT statement.

SQL

To implement this, support is needed from the host programming language, the DBMS and the OS. Good practice is to record the roles in a metatable.

For more information,
see Transactions in NDS.

When dealing with transactions, the introduction of concurrency into the system can bring efficiency gains, however the DBMS must ensure that integrity is not compromised by this. The safest route is sequential execution, but this is highly inefficient, so we need to introduce some form of transaction management.

We can consider transactions as a series of database operations that together move the database from one consistent state to another, although the database may be inconsistent at points during the transaction execution. It is desirable for transactions to exhibit the ACID properties to enforce this integrity when concurrency is involved. The ACID properties are:

• Atomicity - all steps must be completed before changes become permenant and visible, and if completion is not possible, then we must fail and updates are undone
• Consistency - transactions must maintain validity
• Isolation - transactions must not interfere with each other
• Durability - it must be possible to recover from system crashes

Lost Update Problem

Uncommitted Dependency Problem

Inconsistent Analysis

Schedulers

Locking

SQL

Recovery

Distributed databases typically consist of logically related data, but they are no longer centralised - the database is broken into fragments. Management is still central, which leads to a degree of transparency in the database system. The distributed database shares a common universe of discourse.

Distributed databases can afford us efficiency, reliability, and allow us to decentralise a business. Server farms consisting of many generic servers are now common, as opposed to purchasing a large mainframe. With the rise of fast networks and the acceptance of the Internet, distributed databases are now a common reality.

With distributed databases, we can have data where it is needed, with a more flexible growth route and a reduced risk of single point-of-failure, however management and control (the duplication ghost) adds additional complexity, and considerations need to be made for increased security threats and storage requirements. There are still no standards for distributed DBMSs, and in reality there is a long way to go to perfect this area of database theory.

A distributed DBMS keeps track of local and distributed data and performs query optimisation based on the best access strategy. Most DDBMSs provide an enhanced security, concurrency and recovery facility, as well as enhanced transaction management to decompose access requests.

The components of a DDBMS include computer workstations for the data and the clients, network hardware and software and then in the clients, a transaction processor and data manager are required. Both data and processing can happen either at a single or multiple sites with a distributed system, and a certain amount of heterogeneity is supported by most DDBMSs.

DDBMS Architecture

Transparency is required so that the end user feels that they are the only user of local data. Distribution transparency works on the principles of fragmenation, location and local mapping. SQL supports a special NODE clause to specify the location of a fragment and to implement local mapping. Updates on duplicates also become the responsibility of the programmer. For transaction transparency, a two-phase commit protocol is used, and we also have to consider failure transparency, performance transparency (query optimisation) and heterogeneity transparency.

Design Considerations

For election algorithms,
see NDS.

Distributed concurrency is based on an extension of the locking mechanism. A coordinator site exists which associates locks with distinguished copies at a primary site (with or without a backup site) and a primary copy. Coordinators are chosen using an election process, or a voting method.

Codd specified a set of twelve commandments for distributed databases - although none are implemented in modern DDBMSs, like the similar commandments for relational systems, they provide a framework for explanation and evaluation.

1. Local site independence
2. Central site independence
3. Failure independence
4. Location transparency
5. Fragmenation transparency
6. Replication transparency
7. Distributed query processing
8. Distributed transaction processing
9. Hardware independence
10. Operating system independence
11. Network independence
12. Database independence