Monday, January 25, 2010

Normalization



[ Team LiB ]





Normalization


Once you have identified business entities and converted them to a logical model, the logical model needs to be normalized. Normalization is the process of identifying and eliminating redundant data elements in the logical design to avoid update and delete anomalies. The normalization process uses a series of forms (CODD,1970) that have defined rules, and these rules are applied to each entity in an iterative approach.


For our purposes, we will discuss five types of normal forms. They are First Normal Form (1NF), Second Normal Form (2NF), Third Normal Form (3NF), Boyce-Codd Normal Form (BCNF), and Domain/Key Normal Form (DK/NF). DBAs should also become familiar with Elementary Key Normal Form (EKNF) and Project-Join Normal Form (PJNF), but they are beyond the scope of this chapter.


Functional Dependencies


A functional dependency is a relationship between or among attributes. An example would be that if we are given the value of one attribute, we can obtain the value of another attribute. For example, if we know the value of STUDENT_ID we can find the value of GRADE_LEVEL. We can restate this using the following notation:



STUDENT_ID => GRADE_LEVEL

which can be read as the attribute STUDENT_ID determines the attribute GRADE_LEVEL or GRADE_LEVEL is determined by STUDENT_ID. The attributes on the left side of the arrow are called determinants.


We will see later in this section how functional dependencies can be used to normalize relations.


Key


A key is a group of one or more attributes that uniquely identifies a row. Every relation must contain a primary key. It should be noted that keys and functional dependencies are not determined by some arbitrary set of rules but are determined by the business rules of the organization.





    [ Team LiB ]



    Database History File



    [ Team LiB ]






    Database History File


    Recovery log files and the recovery history file are created automatically when a database is created. These log files are important if you need to recover data that is lost or damaged. You cannot directly modify a recovery log file or the recovery history file; however, you can delete entries from the recovery history file using the PRUNE HISTORY command. You can also use the rec_his_retentn database configuration parameter to specify the number of days that the recovery history file will be retained. The recovery history file is automatically updated whenever any of the following operations occur:


    • A database (or table spaces) is backed up.

    • A database (or table spaces) is restored.

    • A database (or table spaces) is rolled forward.

    • A table space is created.

    • A table space is altered.

    • A table space is quiesced.

    • A table space is renamed.

    • A table space is dropped.

    • A table is loaded.

    • A table is dropped.

    • A table is reorganized.


    The file contains a summary of the backup information that can be used in case all or part of the database must be recovered to a given point in time. The information in the file includes


    • The copied part of the database and how it was copied

    • The time the copy was made

    • The location of the copy

    • The last time a restore was done


    Every backup operation includes a copy of the recovery history file, which is linked to the database. Dropping a database deletes the recovery history file. Restoring data doesn't overwrite an existing history recovery file.


    If the current database is unusable or unavailable and the associated history file is damaged or deleted, you can follow these steps to restore the file:






    1. Open the Journal. Click on the Journal option in the Control Center's toolbar or choose Start Programs IBM DB2 General Administration Tools Journal.


    2. Click the Database History tab to see the Database History files, as shown in Figure 16.26.



      Figure 16.26. The Journal's Database History page.






    3. In the Restore Database Recovery History Wizard, select an entry, right-click it, and select Restore to invoke the Restore image.



    The recovery history file helps you locate information when you've performed a backup. For example, it can help you determine the location of a backup or in which backup a DB2 object can be found. If a backup is moved to different media�say, from disk to tape�this file can be updated to keep track of the new location of the backup.


    Every DB2 backup contains a copy of this file, and it can be restored from any backup. If you choose to restore it, use caution to avoid overwriting the database's existing history file.


    Note



    Although the recovery history file is an ASCII file, manually editing the file should be done only at your own risk and isn't recommended.




    Log files and the recovery history file are created automatically when a database is created. You cannot modify a log file or the recover history file; however, they are important should you need to use your database backup to recover lost or damaged data.






      [ Team LiB ]



      1.3 A Simple Database











       < Day Day Up > 







      1.3 A Simple Database





      Because this is a practical book, it contains

      numerous examples. Rather than fabricating different sets of tables

      and columns for every chapter or section in the book, we have decided

      to draw from a single, simple schema for most examples. The subject

      area that we chose to model is a parts distributor, such as an

      auto-parts wholesaler or medical device distributor, in which the

      business fills customer orders for one or more parts that are

      supplied by external suppliers. Figure 1-1 shows

      the entity-relationship model for this

      business.







      Figure 1-1. The parts distributor model







      If you are unfamiliar with



      entity-relationship

      models, here is a brief description of how they work. Each box in the

      model represents an entity, which correlates to

      a database table.[1] The

      lines between the entities represent the

      relationships between



      tables,

      which correlate to foreign keys. For example, the

      cust_order table holds a foreign key to the

      employee table, which





      signifies the salesperson responsible for

      a particular order. Physically, this means that the

      cust_order table contains a column holding

      employee ID numbers, and that, for any given order, the employee ID

      number indicates the employee who sold that order. If you find this

      confusing, simply use the diagram as an illustration of the tables

      and columns found within our database. As you work your way through

      the SQL examples in this book, return occasionally to the diagram,

      and you should find that the relationships start making sense.

      [1] Depending on the purpose of the

      model, entities may or may not correlate to database tables. For

      example, a logical model depicts business entities and their

      relationships, whereas a physical model

      illustrates tables and their primary/foreign keys. The model in Figure 1-1 is a physical model.

















         < Day Day Up > 



        Ability to Perform



        [ Team LiB ]









        Ability to Perform


        GP 2.2 Plan the Process


        Establish and maintain the plan for performing the configuration management process.


        Elaboration

        This plan for performing the configuration management process can be included in (or referenced by) the project plan, which is described in the Project Planning process area.




        GP 2.3 Provide Resources


        Provide adequate resources for performing the configuration management process, developing the work products, and providing the services of the process.


        Elaboration


        Examples of resources provided include the following tools:



        • Configuration management tools


        • Data management tools


        • Archiving and reproduction tools


        • Database programs






        GP 2.4 Assign Responsibility


        Assign responsibility and authority for performing the process, developing the work products, and providing the services of the configuration management process.



        GP 2.5 Train People


        Train the people performing or supporting the configuration management process as needed.


        Elaboration


        Examples of training topics include the following:



        • Roles, responsibilities, and authority of the configuration management staff


        • Configuration management standards, procedures, and methods


        • Configuration library system











          [ Team LiB ]



          The Animation Framework









          The Animation Framework


          JackPanel is a subclass of JPanel and implements the animation framework described in Chapters 2 and 3; JackPanel resembles the BugPanel class of Chapter 11.


          The JackPanel( ) constructor in Example 12-1 creates the game entities: the RibbonsManager, BricksManager, JumperSprite, and FireBallSprite objects. It prepares the explosion animation and the title/help screen.



          Example 12-1. The JackPanel constructor


          // some of the globals
          private JumpingJack jackTop;
          private JumperSprite jack; // the sprites
          private FireBallSprite fireball;
          private RibbonsManager ribsMan; // the ribbons manager
          private BricksManager bricksMan; // the bricks manager

          // to display the title/help screen
          private boolean showHelp;
          private BufferedImage helpIm;

          // explosion-related
          private ImagesPlayer explosionPlayer = null;
          private boolean showExplosion = false;
          private int explWidth, explHeight; // image dimensions
          private int xExpl, yExpl; // coords where image is drawn


          public JackPanel(JumpingJack jj, long period)
          {
          jackTop = jj;
          this.period = period;

          setDoubleBuffered(false);
          setBackground(Color.white);
          setPreferredSize( new Dimension(PWIDTH, PHEIGHT));

          setFocusable(true);
          requestFocus( ); // so receives key events

          addKeyListener( new KeyAdapter( ) {
          public void keyPressed(KeyEvent e)
          { processKey(e); }
          });

          // initialise the loaders
          ImagesLoader imsLoader = new ImagesLoader(IMS_INFO);
          clipsLoader = new ClipsLoader(SNDS_FILE);


          // initialise the game entities

          bricksMan = new BricksManager(PWIDTH, PHEIGHT, BRICKS_INFO, imsLoader);
          int brickMoveSize = bricksMan.getMoveSize( );

          ribsMan = new RibbonsManager(PWIDTH, PHEIGHT, brickMoveSize, imsLoader);

          jack = new JumperSprite(PWIDTH, PHEIGHT, brickMoveSize,
          bricksMan, imsLoader, (int)(period/1000000L) ); // in ms


          fireball = new FireBallSprite(PWIDTH, PHEIGHT,
          imsLoader, this, jack);


          // prepare the explosion animation

          explosionPlayer = new ImagesPlayer("explosion",
          (int)(period/1000000L), 0.5, false, imsLoader);
          BufferedImage explosionIm = imsLoader.getImage("explosion");
          explWidth = explosionIm.getWidth( );
          explHeight = explosionIm.getHeight( );
          explosionPlayer.setWatcher(this) // report anim end back here


          // prepare title/help screen

          helpIm = imsLoader.getImage("title");
          showHelp = true; // show at start-up
          isPaused = true;

          // set up message font
          msgsFont = new Font("SansSerif", Font.BOLD, 24);
          metrics = this.getFontMetrics(msgsFont);
          } // end of JackPanel( )




          The BricksManager object is created first, so a brickMoveSize variable can be initialized. This will contain the number of pixels that the bricks map is shifted when the sprite appears to move. brickMoveSize is used as the basis for the move increments employed by the Ribbon objects managed in RibbonsManager and is used by the JumperSprite. However, the fireball travels at its own rate, independent of the background, so it doesn't require the move size.


          JackPanel is in charge of a fireball's animated explosion and its associated audio, rather than FireBallSprite. The explosion animation in explosion.gif is loaded into an ImagesPlayer (see Figure 12-5 for its contents), and the dimensions of its first image are recorded. When the sequence is finished, ImagesPlayer will call sequenceEnded( ) back in JackPanel.



          Figure 12-5. The images strip in explosion.gif



          The title/help image (in title.gif; see Figure 12-6) is loaded into the global helpIm, and the values of the Booleans showHelp and isPaused are set. isPaused causes the game's execution to pause and was introduced in the basic game animation framework; showHelp is a new Boolean, examined by gameRender( ) to decide whether to draw the image.



          Figure 12-6. title.gif: the title/help screen in JumpingJack



          gameRender( ) displays the image centered in the JPanel, so the image should not be too large or its borders may be beyond the edges of the panel. If the image is the same size as the JPanel, it will totally obscure the game window and look more like a screen rather than an image drawn on the game surface.


          Clever use can be made of transparency to make the image an interesting shape though it's still a rectangle as far as drawImage( ) is concerned.



          Switching on isPaused while the help image is visible requires a small change to the resumeGame( ) method:



          public void resumeGame( )
          { if (!showHelp) // CHANGED
          isPaused = false;
          }



          This method is called from the enclosing JumpingJack JFrame when the frame is activated (deiconified). Previously, resumeGame( ) is always set isPaused to false, but now this occurs only when the help screen isn't being displayed.


          If the game design requires distinct title and help screens, then two images and two Booleans will be needed. For example, you would need showHelp for the help image and showTitle for the titles, which would be examined in gameRender( ). Initially, showTitle would be set to true and showHelp assigned a false value. When the titles or the help is on-screen, isPaused would be set to true.



          Dealing with Input


          Only keyboard input is supported in JumpingJack. A key press triggers a call to processKey( ), which handles three kinds of input: termination keys, help controls, and game-play keys:



          private void processKey(KeyEvent e)
          {
          int keyCode = e.getKeyCode( );



          // termination keys

          // listen for esc, q, end, ctrl-c on the canvas to
          // allow a convenient exit from the full screen configuration
          if ((keyCode==KeyEvent.VK_ESCAPE) || (keyCode==KeyEvent.VK_Q) ||
          (keyCode == KeyEvent.VK_END) ||
          ((keyCode == KeyEvent.VK_C) && e.isControlDown( )) )
          running = false;


          // help controls

          if (keyCode == KeyEvent.VK_H) {
          if (showHelp) { // help being shown
          showHelp = false; // switch off
          isPaused = false;
          }
          else { // help not being shown
          showHelp = true; // show it
          isPaused = true;
          }
          }


          // game-play keys

          if (!isPaused && !gameOver) {
          // move the sprite and ribbons based on the arrow key pressed
          if (keyCode == KeyEvent.VK_LEFT) {
          jack.moveLeft( );
          bricksMan.moveRight( ); // bricks and ribbons move other way
          ribsMan.moveRight( );
          }
          else if (keyCode == KeyEvent.VK_RIGHT) {
          jack.moveRight( );
          bricksMan.moveLeft( );
          ribsMan.moveLeft( );
          }
          else if (keyCode == KeyEvent.VK_UP)
          jack.jump( ); // jumping has no effect on bricks/ribbons
          else if (keyCode == KeyEvent.VK_DOWN) {
          jack.stayStill( );
          bricksMan.stayStill( );
          ribsMan.stayStill( );
          }
          }
          } // end of processKey( )



          The termination keys are utilized in the same way as in earlier examples. The help key (h) toggles the showHelp and isPaused Booleans on and off. The arrow keys are assigned to be the game play keys. When the left or right arrow keys are pressed, the scenery (the bricks and ribbons) is moved in the opposite direction from Jack. You'll see that the calls to moveLeft( ) and moveRight( ) in Jack don't cause the sprite to move at all.




          Multiple Key Presses/Actions


          A common requirement in many games is to process multiple key presses together. For example, it should be possible for Jack to jump and move left/right at the same time. There are two parts to this feature: implementing key capture code to handle simultaneous key presses and implementing simultaneous behaviors in the sprite.


          JumpingJack has the ability to jump and move left/right simultaneously: it was wired into the JumperSprite class at the design stage, as you'll see. If Jack is currently moving left or right, then an up arrow press will make him jump. A related trick is to start Jack jumping from a stationary position, causing him to rise and fall over 1 to 2 seconds. During that interval, the left or right arrow keys can be pressed to get him moving horizontally through the air or to change his direction in mid-flight!


          Though Jack can jump and move simultaneously, this behavior is triggered by distinct key presses. First, the left/right arrow key is pressed to start him moving, and then the up arrow key makes him jump. Alternatively, the up arrow key can be pressed first, followed by the left or right arrow keys. If you want to capture multiple key presses at the same time, then modifications are needed to the key listener code.


          The main change would be to use keyPressed( ) and keyReleased( ) and to introduce new Booleans to indicate when keys are being pressed. The basic coding strategy is shown here:




          // global Booleans, true when a key is being pressed

          private boolean leftKeyPressed = false;
          private boolean rightKeyPressed = false;
          private boolean upKeyPressed = false;


          public JackPanel(JumpingJack jj, long period)
          {
          ... // other code
          addKeyListener( new KeyAdapter( ) {
          public void keyPressed(KeyEvent e)
          { processKeyPress(e); }
          public void keyReleased(KeyEvent e)
          { processKeyRelease(e); }
          });
          ... // other code
          }


          private void processKeyPress(KeyEvent e)
          {
          int keyCode = e.getKeyCode( );


          // record the key press in a Boolean

          if (keyCode == KeyEvent.VK_LEFT)
          leftKeyPressed = true;
          else if (keyCode == KeyEvent.VK_RIGHT)

          rightKeyPressed = true;
          else if (keyCode == KeyEvent.VK_UP)
          upKeyPressed = true;


          // use the combined key presses

          if (leftKeyPressed && upKeyPressed)
          // do a combined left and up action
          else if (rightKeyPressed && upKeyPressed)
          // do a combined right and up action

          ... // other key processing code
          } // end of processKeyPress( )


          private void processKeyRelease(KeyEvent e)
          {
          int keyCode = e.getKeyCode( );


          // record the key release in a Boolean

          if (keyCode == KeyEvent.VK_LEFT)
          leftKeyPressed = false;
          else if (keyCode == KeyEvent.VK_RIGHT)
          rightKeyPressed = false;
          else if (keyCode == KeyEvent.VK_UP)
          upKeyPressed = false;
          } // end of processKeyRelease( )



          Key presses cause the relevant Booleans to be set, and they remain set until the user releases the keys at some future time. The combination of key presses can be detected by testing the Booleans in processKeyPress( ).


          This coding effort is only needed for combinations of "normal" keys (e.g., the letters, the numbers, and arrow keys). Key combinations involving a standard key and the shift, control, or meta keys can be detected more directly by using the KeyEvent methods isShiftDown( ), isControlDown( ), and isMetaDown( ). This coding style can be seen in the termination keys code in processKey( ):



          if (...||((keyCode==KeyEvent.VK_C) && e.isControlDown( ))) //ctrl-c
          running = false;





          The Animation Loop


          The animation loop is located in run( ) and is unchanged from earlier examples. For example, it's the same run( ) method seen in BugRunner in Chapter 11. Essentially, it is:



          public void run( )
          { // initialization code
          while (running) {

          gameUpdate( );


          gameRender( );

          paintScreen( );

          // timing correction code
          }
          System.exit(0);
          }



          gameUpdate( ) updates the various game elements (the sprites, the brick layers, and Ribbon objects):



          private void gameUpdate( )
          {
          if (!isPaused && !gameOver) {
          if (jack.willHitBrick( )) { // collision checking first
          jack.stayStill( ); // stop jack and scenery
          bricksMan.stayStill( );
          ribsMan.stayStill( );
          }
          ribsMan.update( ); // update background and sprites
          bricksMan.update( );
          jack.updateSprite( );
          fireball.updateSprite( );

          if (showExplosion)
          explosionPlayer.updateTick( ); // update the animation
          }
          }



          The new element here is dealing with potential collisions: if Jack is to hit a brick when the current update is carried out, then the update should be cancelled. This requires a testing phase before the update is committed, embodied in willHitBrick( ) in JumperSprite. If Jack is to hit a brick with his next update, it will be due to him moving (there are no animated tiles in this game), so the collision can be avoided by stopping Jack (and the backgrounds) from moving.


          The fireball sprite is unaffected by Jack's impending collision: it travels left regardless of what the JumperSprite is doing.


          The showExplosion Boolean is set to true when the explosion animation is being played by the ImagesPlayer (explosionPlayer), so updateTick( ) must be called during each game update.



          Rendering order

          gameRender( ) draws the multiple layers making up the game. Their ordering is important because rendering must start with the image farthest back in the scene and work forward. This ordering is illustrated in Figure 12-2 for JumpingJack:



          private void gameRender( )
          {
          if (dbImage == null){
          dbImage = createImage(PWIDTH, PHEIGHT);
          if (dbImage == null) {
          System.out.println("dbImage is null");
          return;

          }
          else
          dbg = dbImage.getGraphics( );
          }

          // draw a white background
          dbg.setColor(Color.white);
          dbg.fillRect(0, 0, PWIDTH, PHEIGHT);

          // draw the game elements: order is important
          ribsMan.display(dbg); // the background ribbons
          bricksMan.display(dbg); // the bricks
          jack.drawSprite(dbg); // the sprites

          fireball.drawSprite(dbg);


          if (showExplosion) // draw the explosion (in front of jack)
          dbg.drawImage(explosionPlayer.getCurrentImage( ),
          xExpl, yExpl, null);
          reportStats(dbg);
          if (gameOver)
          gameOverMessage(dbg);

          if (showHelp) // draw help at the very front (if switched on)
          dbg.drawImage(helpIm, (PWIDTH-helpIm.getWidth( ))/2,
          (PHEIGHT-helpIm.getHeight( ))/2, null);
          } // end of gameRender( )



          gameRender( ) relies on the RibbonsManager and BricksManager objects to draw the multiple Ribbon objects and the individual bricks. The code order means that Jack will be drawn behind the fireball if they are at the same spot, i.e., when the fireball hits him. An explosion is drawn in front of the fireball, and the game statistics, the Game Over message, and the help screen is layered on top.





          Handling an Explosion


          The fireball sprite passes the responsibility of showing the explosion animation and its audio clip to JackPanel, by calling showExplosion( ):



          // names of the explosion clips
          private static final String[] exploNames =
          {"explo1", "explo2", "explo3"};

          public void showExplosion(int x, int y)
          // called by FireBallSprite
          {
          if (!showExplosion) { // only allow a single explosion at a time
          showExplosion = true;
          xExpl = x - explWidth/2; // (x,y) is center of explosion
          yExpl = y - explHeight/2;

          /* Play an explosion clip, but cycle through them.
          This adds variety, and gets around not being able to

          play multiple instances of a clip at the same time. */
          clipsLoader.play( exploNames[ numHits%exploNames.length ],
          false);
          numHits++;
          }
          } // end of showExplosion( )



          The (x, y) coordinate passed to showExplosion( ) is assumed to be where the center of the explosion should occur, so the top-left corner of the explosion image is calculated and placed in the globals (xExpl, yExpl). These are used to position the explosion in gameRender( ).


          The use of a single Boolean (showExplosion) to determine if an explosion appears on-screen is adequate only if a single explosion animation is shown at a time. This means that if a fireball hits Jack while an explosion sequence is playing (as a result of a previous fireball that hit him), a second animation will not be rendered. This restriction allows me to use a single ImagesPlayer object instead of a set containing one ImagesPlayer for each of the current explosions.


          play( ) in ClipsLoader eventually calls start( ) for the Clip object. A design feature of start( ) is that when a clip is playing, further calls to start( ) will be ignored. This makes it impossible to play multiple instances of the same Clip object at the same time and means that while the explosion clip is playing (for 1 to 2 seconds), another explosion can't be heard. This absence is quite noticeable (more so than the lack of multiple explosion animations, for some reason). Also, the game just seems more fun if there's a crescendo of explosions as Jack gets pummeled.


          Therefore, I've gone for a set of explosion clips, stored in exploNames[], and the code cycles through them. A set of three seems enough to deal with even the highest rate of fireball hits to Jack. Since these names represent separate Clips stored in the ClipsLoader, they can be played simultaneously.


          The clips are different from each other, so there's a pleasing interplay of noises as multiple explosions go off. The order the sounds are played isn't relevant, at least in this game.


          I found the clips by searching for sound filenames containing the word "explosion," "bomb," and similar, using the FindSounds site (http://www.findsounds.com/). I looked for small clips, lasting 1-2 seconds, to roughly match the duration of the explosion animation.



          Once an explosion animation has finished playing, its ImagesPlayer object calls sequenceEnded( ) in JackPanel:



          public void sequenceEnded(String imageName)
          // called by ImagesPlayer when the expl. animation finishes
          {
          showExplosion = false;
          explosionPlayer.restartAt(0); // reset animation for next time


          if (numHits >= MAX_HITS) {
          gameOver = true;
          score = (int) ((J3DTimer.getValue( ) -
          gameStartTime)/1000000000L);
          clipsLoader.play("applause", false);
          }
          }



          sequenceEnded( ) resets the animation, so it's ready to be played next time, and checks the game over condition. If the number of fireball hits equals or exceeds MAX_HITS, then the game over flag is set, causing the game to terminate.


          The main question about sequenceEnded( ) is why it is being used at all. The answer is to make the game terminate at a natural time, just after an explosion has finished. For instance, if the game over condition was tested at the end of showExplosion( ), the game might have been terminated while ImagesPlayer was in the middle of displaying the explosion animation. This might seem a bit odd to a player, especially one who likes to see explosions run their course.










            Table of content



            [ Team LiB ]






              
            • Table of Contents
            Algorithms in Java, Third Edition, Part 5: Graph Algorithms
            By
            Robert Sedgewick
             
            Publisher: Addison Wesley
            Pub Date: July 15, 2003
            ISBN: 0-201-36121-3
            Pages: 528


               Copyright
               Preface
               
             
            Algorithms
               
             
            Scope
               
             
            Use in the Curriculum
               
             
            Algorithms of Practical Use
               
             
            Programming Language
               
             
            Acknowledgments
               Java Consultant's Preface
               Notes on Exercises
               
            Part V: 
            Graph Algorithms
               
             

             

            Chapter 17. 
            Graph Properties and Types
               
             

            Section 17.1. 
            Glossary
               
             

            Section 17.2. 
            Graph ADT
               
             

            Section 17.3. 
            Adjacency-Matrix Representation
               
             

            Section 17.4. 
            Adjacency-Lists Representation
               
             

            Section 17.5. 
            Variations, Extensions, and Costs
               
             

            Section 17.6. 
            Graph Generators
               
             

            Section 17.7. 
            Simple, Euler, and Hamilton Paths
               
             

            Section 17.8. 
            Graph-Processing Problems
               
             

             

            Chapter 18. 
            Graph Search
               
             

            Section 18.1. 
            Exploring a Maze
               
             

            Section 18.2. 
            Depth-First Search
               
             

            Section 18.3. 
            Graph-Search ADT Methods
               
             

            Section 18.4. 
            Properties of DFS Forests
               
             

            Section 18.5. 
            DFS Algorithms
               
             

            Section 18.6. 
            Separability and Biconnectivity
               
             

            Section 18.7. 
            Breadth-First Search
               
             

            Section 18.8. 
            Generalized Graph Search
               
             

            Section 18.9. 
            Analysis of Graph Algorithms
               
             

             

            Chapter 19. 
            Digraphs and DAGs
               
             
            Exercises
               
             

            Section 19.1. 
            Glossary and Rules of the Game
               
             

            Section 19.2. 
            Anatomy of DFS in Digraphs
               
             

            Section 19.3. 
            Reachability and Transitive Closure
               
             

            Section 19.4. 
            Equivalence Relations and Partial Orders
               
             

            Section 19.5. 
            DAGs
               
             

            Section 19.6. 
            Topological Sorting
               
             

            Section 19.7. 
            Reachability in DAGs
               
             

            Section 19.8. 
            Strong Components in Digraphs
               
             

            Section 19.9. 
            Transitive Closure Revisited
               
             

            Section 19.10. 
            Perspective
               
             

             

            Chapter 20. 
            Minimum Spanning Trees
               
             
            Exercises
               
             

            Section 20.1. 
            Representations
               
             

            Section 20.2. 
            Underlying Principles of MST Algorithms
               
             

            Section 20.3. 
            Prim's Algorithm and Priority-First Search
               
             

            Section 20.4. 
            Kruskal's Algorithm
               
             

            Section 20.5. 
            Boruvka's Algorithm
               
             

            Section 20.6. 
            Comparisons and Improvements
               
             

            Section 20.7. 
            Euclidean MST
               
             

             

            Chapter 21. 
            Shortest Paths
               
             
            Exercises
               
             

            Section 21.1. 
            Underlying Principles
               
             

            Section 21.2. 
            Dijkstra's Algorithm
               
             

            Section 21.3. 
            All-Pairs Shortest Paths
               
             

            Section 21.4. 
            Shortest Paths in Acyclic Networks
               
             

            Section 21.5. 
            Euclidean Networks
               
             

            Section 21.6. 
            Reduction
               
             

            Section 21.7. 
            Negative Weights
               
             

            Section 21.8. 
            Perspective
               
             

             

            Chapter 22. 
            Network Flow
               
             

            Section 22.1. 
            Flow Networks
               
             

            Section 22.2. 
            Augmenting-Path Maxflow Algorithms
               
             

            Section 22.3. 
            Preflow-Push Maxflow Algorithms
               
             

            Section 22.4. 
            Maxflow Reductions
               
             

            Section 22.5. 
            Mincost Flows
               
             

            Section 22.6. 
            Network Simplex Algorithm
               
             

            Section 22.7. 
            Mincost-Flow Reductions
               
             

            Section 22.8. 
            Perspective
               
             
            References for Part Five



            [ Team LiB ]




            Complete and Total Disaster











             < Day Day Up > 











            Complete and Total Disaster


            Disaster struck Horatio's Woodscrews on a particularly wet spring day. Rain had been falling steadily for weeks in the city. The DBA was sleeping soundly, dreaming of data protection systems, when his pager began to beep. He called the number groggily, looking at the clock. It was the middle of the night.


            A water main had busted near the Woodscrew building, and the basement had flooded. The basement held all of the database systems-the production Solaris box, the Sales RAC cluster, the test and dev servers, everything. The utility company was marking the area as a disaster area, and not letting anyone near the building.


            All the servers were lost. The DBA had to think fast. Did they move the tape backups off-site, as was proposed a few months back? He could not remember, so he called the backup administrator. Did they have those old Solaris boxes they'd retired last year someplace? The DBA dialed the system administrator.


            A conference call was put together in the middle of the night. Where were the archived tape backups? Were they moved to a different building? When was the last time the tapes were moved to the other location? How much data would be lost in the flood?


            The questions flew around to the system administrator-Where could they find new systems to install Oracle? Would there be enough disk space without the SAN device? Should they contact the vendors to get emergency hardware shipped in?


            Then the questions came to the DBA: Could we rebuild the data once the drives were salvaged from the flood? Could we hobble along on one of the older servers at the other office? How fast could he get Oracle installed, patched, and ready to start the file restore from the archive tapes?


            And, finally, the ultimate question: Who's going to call the CEO and tell him what happened?



















             < Day Day Up > 



            Section A.2.&nbsp; Acquisition and Implementation










            A.2. Acquisition and Implementation



            A.2.1. Identify Automated Solutions


            • Definition of information requirements

            • Formulation of alternative courses of action

            • Formulation of acquisition strategy

            • Third-party service requirements

            • Technological feasibility study

            • Economic feasibility study

            • Information architecture

            • Risk analysis report

            • Cost-effective security controls

            • Audit trails design

            • Ergonomics

            • Selection of system software

            • Procurement control

            • Software product acquisition

            • Third-party software maintenance

            • Contract application programming

            • Acceptance of facilities

            • Acceptance of technology




            A.2.2. Acquire and Maintain Application Software


            • Design methods

            • Major changes to existing systems

            • Design approval

            • File requirements definition and documentation

            • Program specifications

            • Source data collection design

            • Input requirements definition and documentation

            • Definition of interfaces

            • User-machine interface

            • Processing requirements definition and documentation

            • Output requirements definition and documentation

            • Controllability

            • Availability as a key design factor

            • IT integrity provisions in application program software

            • Application software testing

            • User reference and support materials

            • Reassessment of system design




            A.2.3. Acquire and Maintain Technology Infrastructure


            • Assessment of new hardware and software

            • Preventive maintenance for hardware

            • System software security

            • System software installation

            • System software maintenance

            • System software change controls

            • Use and monitoring of system utilities




            A.2.4. Develop and Maintain Procedures


            • Operational requirements and service levels

            • User procedures manual

            • Operations manual

            • Training materials




            A.2.5. Install and Accredit Systems


            • Training

            • Application software performance sizing

            • Implementation plan

            • System conversion

            • Data conversion

            • Testing strategies and plans

            • Testing of changes

            • Parallel/pilot testing criteria and performance

            • Final acceptance test

            • Security testing and accreditation

            • Operational test

            • Promotion to production

            • Evaluation of meeting user requirements

            • Management's post-implementation review




            A.2.6. Manage Changes


            • Change request initiation and control

            • Control of changes

            • Emergency changes

            • Documentation and procedures

            • Authorized maintenance

            • Software release policy

            • Distribution of software













            Program 6: Gotta Have My Space













            Program 6: Gotta Have My Space

            Here's a short experiential program written by someone the first week he was learning how to program. It's designed to print an simple answer. But things don't quite go right.




            1 /************************************************
            2 * Double a number. *
            3 ************************************************/
            4 #include <iostream>
            5
            6 int main(void)
            7 {
            8 int number; // A number to double
            9
            10 std::cout << "Enter a number:";
            11 std::cin >> number;
            12
            13 std::cout << "Twice" << number << "is" <<
            14 (number * 2) << '\n';
            15 return (0);
            16 }


            (Next Hint 247. Answer 23.)




















            Table of content



            [ Team LiB ]






              
            • Table of Contents
            • Index
            Sams Teach Yourself DB2® Universal Database™ in 21 Days, Second Edition
            By
            Susan Visser, Bill Wong
             
            Publisher: Sams Publishing
            Pub Date: August 20, 2003
            ISBN: 0-672-32582-9
            Pages: 624


               Copyright
               About the Author
               Acknowledgments
               We Want to Hear from You!
               Introduction
               
             
            Assumptions
               
             
            How to Use This Book
               
             
            Conventions Used in This Book
               
             
            About the CD-ROM
               Week 1. 
            At a Glance
               
             
            Day 1. 
            What DB2 Can Do for You
               
             
            What Is DB2 Universal Database?
               
             
            Understanding How DB2 Universal Database Works with Data
               
             
            DB2 Tools for Administering Databases
               
             
            Accessing Host Data from the Desktop
               
             
            Developing Applications with the DB2 Developer's Editions
               
             
            Accessing DB2 Data from the Web
               
             
            Using DB2 Parallelism
               
             
            Overview of the DB2 Enterprise Host Servers
               
             
            Summary
               
             
            What Comes Next?
               
             
            Q&A
               
             
            Workshop
               
             
            Day 2. 
            Exploring the Capabilities of DB2 Universal Database
               
             
            Major Components of DB2
               
             
            What Is a Relational Database?
               
             
            Data Integrity
               
             
            Application Programs
               
             
            System Management Facilities
               
             
            Summary
               
             
            What Comes Next?
               
             
            Q&A
               
             
            Workshop
               
             
            Day 3. 
            Installing and Configuring DB2 Server
               
             
            Preparing for the Install
               
             
            Performing a Typical Install
               
             
            Performing a Custom Install
               
             
            Performing a Compact Install
               
             
            Installing the Product Information library
               
             
            Modifying, Repairing, or Removing DB2
               
             
            Summary
               
             
            What Comes Next?
               
             
            Q&A
               
             
            Workshop
               
             
            Day 4. 
            Getting Started
               
             
            Logging On to the System
               
             
            Understanding the Desktop
               
             
            Changing Passwords
               
             
            Starting or Stopping DB2
               
             
            Using DB2 First Steps
               
             
            Granting Privileges to Other Users
               
             
            Summary
               
             
            What Comes Next?
               
             
            Q&A
               
             
            Workshop
               
             
            Day 5. 
            Setting Up DB2 Instances and Server Communications
               
             
            Working with DB2 Instances
               
             
            Modifying the DB2 Communication Configuration of Server Instances
               
             
            Viewing and Modifying Configuration Files
               
             
            Adding Systems Through the Control Center
               
             
            The DB2 Administration Server
               
             
            Server Profiles
               
             
            Summary
               
             
            What Comes Next?
               
             
            Q&A
               
             
            Workshop
               
             
            Day 6. 
            Installing and Configuring DB2 Clients
               
             
            Understanding the Different Types of DB2 Clients
               
             
            Preparing for the Install
               
             
            Performing a Typical Install
               
             
            Performing a Custom Install
               
             
            Performing a Compact Install
               
             
            Configuring Client-to-Server Communications with the Configuration Assistant
               
             
            Configuring Database Connections
               
             
            Summary
               
             
            What Comes Next?
               
             
            Q&A
               
             
            Workshop
               
             
            Day 7. 
            Ensuring Data Security
               
             
            Authentication
               
             
            Access to DB2 Universal Database
               
             
            Access Within DB2
               
             
            Windows Security Considerations
               
             
            Summary
               
             
            What Comes Next?
               
             
            Q&A
               
             
            Workshop
               Week 2. 
            At a Glance
               
             
            Day 8. 
            Designing the CDLIB Database
               
             
            Deciding What Data to Store in the Database
               
             
            Defining Tables for Each Type of Relationship
               
             
            Identifying the Primary Key
               
             
            Identifying Constraints and Foreign Keys
               
             
            Normalizing Your Table
               
             
            Summary
               
             
            What Comes Next?
               
             
            Q&A
               
             
            Workshop
               
             
            Day 9. 
            Creating Databases and Tables
               
             
            Creating a Simple Database
               
             
            Summary
               
             
            What Comes Next?
               
             
            Q&A
               
             
            Workshop
               
             
            Day 10. 
            Creating Table Spaces
               
             
            Managing Your Data in Table Spaces
               
             
            Using the Create Table Space Wizard
               
             
            Allocating Additional Space
               
             
            Creating a Buffer Pool
               
             
            Creating Table Spaces for Indexes and Large Data
               
             
            Creating Tables in Table Spaces
               
             
            Summary
               
             
            What Comes Next?
               
             
            Q&A
               
             
            Workshop
               
             
            Day 11. 
            Accessing the Data
               
             
            Accessing Data Through the Control Center
               
             
            Accessing Data Through the Command Center
               
             
            Using the Command Line Processor
               
             
            Accessing Data Through Microsoft Access
               
             
            Accessing Data Through Java Applications
               
             
            Accessing Data Through Your Own Applications
               
             
            Summary
               
             
            What Comes Next?
               
             
            Q&A
               
             
            Workshop
               
             
            Day 12. 
            SQL Concepts
               
             
            Data Manipulation Language
               
             
            How SQL Statements Are Invoked
               
             
            Developing Windows Applications
               
             
            Summary
               
             
            What Comes Next?
               
             
            Q&A
               
             
            Workshop
               
             
            Day 13. 
            Advanced SQL
               
             
            Object-Oriented SQL Concepts
               
             
            Development Center
               
             
            DB2 XML Extender
               
             
            DB2 Net Search Extender
               
             
            DB2 Spatial Extender
               
             
            Summary
               
             
            What Comes Next?
               
             
            Q&A
               
             
            Workshop
               
             
            Day 14. 
            Design Considerations
               
             
            System Resources
               
             
            General SQL Guidelines
               
             
            Managing Concurrency
               
             
            Index Considerations
               
             
            Complex Query Application Considerations
               
             
            Summary
               
             
            What Comes Next?
               
             
            Q&A
               
             
            Workshop
               Week 3. 
            At a Glance
               
             
            Day 15. 
            Using System Administration Tools
               
             
            Using the Task Center
               
             
            Using the Journal
               
             
            Customizing Tools Settings
               
             
            Making Your Database More Useful
               
             
            Working with Directories
               
             
            Managing Contacts
               
             
            Managing Licenses
               
             
            Summary
               
             
            What Comes Next?
               
             
            Q&A
               
             
            Workshop
               
             
            Day 16. 
            Recovery Concepts
               
             
            Log Management
               
             
            Backing Up Databases
               
             
            Recovering Data
               
             
            Database History File
               
             
            Summary
               
             
            What Comes Next?
               
             
            Q&A
               
             
            Workshop
               
             
            Day 17. 
            Moving Data
               
             
            Exporting Data
               
             
            Importing and Loading Data
               
             
            Loading Data
               
             
            Summary
               
             
            What Comes Next?
               
             
            Q&A
               
             
            Workshop
               
             
            Day 18. 
            Replicating Data
               
             
            Replication Concepts
               
             
            Creating a Replication Environment
               
             
            Summary
               
             
            What Comes Next?
               
             
            Q&A
               
             
            Workshop
               
             
            Day 19. 
            Database Monitoring Tools
               
             
            Health Monitor
               
             
            Database System Monitor
               
             
            Using Visual Explain
               
             
            Collecting Statistics
               
             
            Reorganizing a Table
               
             
            Storage Management Tool
               
             
            Summary
               
             
            What Comes Next?
               
             
            Q&A
               
             
            Workshop
               
             
            Day 20. 
            Tuning DB2 Universal Database Performance
               
             
            Controlling Your DB2 Environment
               
             
            Configuration Parameters
               
             
            Using the Configuration Advisor
               
             
            Using the Design Advisor
               
             
            Input/Output Performance
               
             
            Summary
               
             
            What Comes Next?
               
             
            Q&A
               
             
            Workshop
               
             
            Day 21. 
            Diagnosing Problems
               
             
            Accessing Documentation
               
             
            Error-Logging Facilities
               
             
            Error-Logging Facilities
               
             
            Configuration Files
               
             
            Tracing Facilities
               
             
            Updating DB2 Products
               
             
            Summary
               
             
            What Comes Next?
               
             
            Q&A
               
             
            Workshop
               Part 4. 
            Appendixes
               
             

            Appendix A. 
            Getting Certified
               
             
            What Is Certification?
               
             
            Benefits of Becoming Certified
               
             
            Am I Ready to Take the Exam?
               
             
            Taking a Certification Exam
               
             
            IBM Certified Database Associate DB2 UDB V8.1 Family Fundamentals
               
             
            Beyond Exam 700
               
             

            Appendix B. 
            Answers to Quiz Questions
               
             
            Day 1
               
             
            Day 2
               
             
            Day 3
               
             
            Day 4
               
             
            Day 5
               
             
            Day 6
               
             
            Day 7
               
             
            Day 8
               
             
            Day 9
               
             
            Day 10
               
             
            Day 11
               
             
            Day 12
               
             
            Day 13
               
             
            Day 14
               
             
            Day 15
               
             
            Day 16
               
             
            Day 17
               
             
            Day 18
               
             
            Day 19
               
             
            Day 20
               
             
            Day 21
               Index



            [ Team LiB ]