In Recursion and Trees～ Recursive Algorithms we have discussed the relationship between mathematical recurrences and simple recursive programs, and we consider a number of examples of practical recursive programs. In this article we examine the fundamental recursive scheme known as divide and conquer, which we use to solve fundamental problems in several later sections. 继续阅读“Recursion and Trees～ Divide and Conquer”
Recursion and Trees～ Recursive Algorithms
The concept of recursion is fundamental in mathematics and computer science. The simple definition is that a recursive program in a programming language is one that calls itself (just as a recursive function in mathematics is one that is defined in terms of itself). A recursive program cannot call itself always, or it would never stop (just as a recursive function cannot be defined in terms of itself always, or the definition would be circular); so a second essential ingredient is that there must be a termination condition when the program can cease to call itself (and when the mathematical function is not defined in terms of itself). All practical computations can be couched in a recursive framework. The study of recursion is intertwined with the study of recursively defined structures known as trees. We use trees both to help us understand and analyze recursive programs and as explicit data structures. 继续阅读“Recursion and Trees～ Recursive Algorithms”
Database Design ~ Database Design and the E-R Model II
As we saw briefly in Database System Concepts ~ Introduction I, an E-R diagram can express the overall logical structure of a database graphically. E-R diagrams are simple and clear——qualities that may well account in large part for the widespread use of the E-R model. 继续阅读“Database Design ~ Database Design and the E-R Model II”
Database Design ~ Database Design and the E-R Model I
Up to this point in the text, we have assumed a given database schema and studied how queries and updates are expressed. We now consider how to design a database schema in the first place. In this section, we focus on the entity-relationship data model (E-R), which provides a means of identifying entities to be represented in the database and how those entities are related. Ultimately, the database design will be expressed in terms of a relational database design and an associated set of constraints. We show in this section how an E-R design can be transformed into a set of relation schemas and how some of the constraints can be captured in that design. 继续阅读“Database Design ~ Database Design and the E-R Model I”
Relational Databases ~ Advanced SQL III
Consider the instance of the relation prereq shown in Figure 1 containing information about the various courses offered at the university and the prerequisite for each course.
Figure 1 The prereq relation. 继续阅读“Relational Databases ~ Advanced SQL III”
Relational Databases ~ Advanced SQL II
We have already seen several functions that are built into the SQL language. In this section, we show how developers can write their own functions and procedures, store them in the database, and then invoke them from SQL statements. 继续阅读“Relational Databases ~ Advanced SQL II”
Relational Databases ~ Advanced SQL I
In previous series, we provided detailed coverage of the basic structure of SQL. In this series, we cover some of the the more advanced features of SQL. We address the issue of how to access SQL from a general-purpose programming language, which is very important for building applications that use a database to store database, either by extending the SQL language to support procedural actions, or by allowing functions defined in procedural languages to be executed within the database. We describe triggers, which can be used to specify actions that are to be carried out automatically on certain events such as insertion, deletion, or update of tuples in a specified relation. We discuss recursive queries and advanced aggregation features supported by SQL. Finally, we describe online analytic processing (OLAP) systems, which support interactive analysis of very large datasets. 继续阅读“Relational Databases ~ Advanced SQL I”
Relational Databases ~ Intermediate SQL III
In previous series, we covered a number of built-in data types supported in SQL, such as integer types, real types, and character types. There are additional built-in data types supported by SQL, which we describe below. We also describe how to create basic user-defined types in SQL. 继续阅读“Relational Databases ~ Intermediate SQL III”
Abstract Data Types～ Application-Based ADT Example
As a final example in ADT series, we consider in this section an application-specific ADT that is representative of the relationship between applications domains and the algorithms and data structures of the type that we consider in this series. 继续阅读“Abstract Data Types～ Application-Based ADT Example”