Recursion and Trees~ Divide and Conquer

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 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 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”