7月30日到8月2日 本人参加了在上海国际会议中心举行的2007 Oracle OpenWorld 会议!

1. 数据不断增加的挑战
2. 软件版本升级, 功能不多增加的这些改变的挑战
3. 如何充分利用成为鸡肋的备用数据库 (Standby DB)

   下面具体讲一下Oracle11g对这些挑战给出的新功能

• 数据不断增加的挑战

   现在随着信息系统的不段运行, 一个数据库以每年三倍的量在增加, 这对数据库在,管理和成本上提出了

很大的挑战.   

    Oracle11g提出了信息生命周期管理的概念(Information Lifecycle management(ILM)), 她把数据分为三类和

它门占总体数据的比例如下 

1.  活跃的数据 (5%)
2. 不大活跃的数据 (35%)
3. 历史数据(60%)

     利用Oracle的分区技术, 把这些数据放在不同性能的磁盘上, 而不是象原来的一样把所有数据都放在高性能的磁盘上, 这样的

ILM显然可以大大降低存储的成本(大约可降低70%).

    Oracle 11g还提供了压缩功能, 也可降低存储成本.

• 应对改变的挑战

   软件有以下一个特点:

1.  她是有bug的, 会经常发布Patch包的
2. 她是不短发布新版本的, 增加新功能

    这些, 对拥护利用这写改变出很到挑战, 主要是改变的时间成本和改变的安全性提出很大挑战. 

Oracle提出了改变生命周期管理的概念(Change lifecycle management). 为此有

1.  Real appliction Test

      通过捕获(capture)实际数据库系统操作的,在测试系统中重演(replay)这个过程的, 对测试系统进行测试

微调的功能! 大大改进了传统数据库的测试效率

    2. 在线更新和补丁(Online Upgrade and patch)

    这个显然是提高改变的可用性.

   3. 继续增强Oracle的自管理功能

• 充分利用成为鸡肋的备用数据库

    以前, 对Oracle的Log, 和Standby 数据库, 只有在数据备份回复, 和数据库崩溃的时候有用. 显然这样的情况是少数

造成资源的浪费.

   Oracle 11g提出了高可用性体系构架, 把log, 产品数据库和备用数据库, 做为一个体系来考虑, 充分利用这些部件. 显然这

是一个开扩思路的方式. 在这思路上, Oracle  给出以下功能

1.  Total Recall

      提供了Select   from tablename as of date, 这样的查询语句, 对以前表的内容查询.

   2.Data guard 是Standby 数据库有以下功能

• 使用备份数据库用于查询, 做各种Report的功能
• 备份备用数据库,而不是产品数据库的方式, 实现备份. 降低产品数据库的work load

以上就是在Oracle Open world 对Oracle 11g的体会. 对与数据库或其它软件增加新功能, Oracle11g给出了她的一个方法

就是面对实践的压力, 提出具有指导意义的思路, 在这个思路下逐进和不断增加新功能.

1. 枚举法

    就是利用计算机快速运算的特点, 遍历所有的可能情况最后得到需要的解. 它是一种朴素的直接算法(brute force),看起来显得有点笨,而且它的效率是N!, 但不要小看着种算法!

• 它的实现很简单, 对于问题一般可以直接给出实现 
• 就算不使用该方法设计的算法, 也可以用该方法设计的算法, 做为高效算法的验证程序. 这个对程序测试很重要!

    2. 贪心算法

      每次选择一个局部最优策略进行实施, 最好成绩得到结果. 由于每次决策不考虑对整体的影响, 它可能得到的不是最优解.

    如果能用贪心算法, 我们可以大大提高算法的效率!

• 什么样的问题可以用贪心算法

           有一类叫矩阵胚(matriod)的子集系统的优化问题可用贪心算法. 矩阵胚就是极大独立子集的具有相同基数的

• 利用贪心算法设计著名的算法
  1. huffman 编码
  2. 最小生成树(minmum span tree)的Prim算法
  3. 最短路径 (minmum path) 的Dijkstra算法

   3. 递归和分治法(divide and conquer)

    如果一个问题可以转化成一个结构相同, 规模更小的问题, 就可以通过递归来解决. 递归法思路清晰, 编成简单,但有时难以想到.

    最重要的是递归是一种分析方法, 可以帮助我们看清问题的本质.

• 利用递归算法设计著名的算法

   4. 递推

   5. 动态规划法(dynamic programming)

     动态规划发是解决多阶段问题决策最优化问题的一种思想方法.  它有两种动机.

•  利用递归的重叠子问题,进行记忆化求解, 即先用递归发解决问题, 在利用重叠子问题转化成动态规划. 其实就是以空间换时间.
•  也可以自底向上递推

•  最大背包问题
•  还有一系列高级的算法常用

   6.状态空间搜索发

1. 盲目搜索
2. 启发式搜索
3. 分枝定界法

• 简介(Introduction)

    通过介绍并查集(union-find set)介绍如何实现朴素算法,到给出各种优化的算法, 以及如何评价算法的基本方法.

• 算法分析基础(Principle of alogrithm analysis)

    介绍算法的两种分析方法经验分析(empirical analysis)和数学分析(mathematical anaysis),及其优缺点

• 基本数据结构(elementary data structures)

    介绍计算机世界的三个基本数据结构(Array, LinkedList, String). 所有的数据结构可以说都是这三个数据结构的组合.

• 抽象数据结构(Abstract data types)

    以面向对象编程的角度, 总结出一些基本抽象数据结构(Stack, FIFO), 它们都是可以用上面的基本数据结构做Field, 来实现的

• 递归和树(Recursive and trees)

    递归思想是编成重要思想, 如果熟练掌握它, 可以大大提高我们的编程能力, 提高代码的效率, 使代码简洁, 可读性好.

    介绍了Trees的类型和定义(Tree, rooted-tree, ordered -tree, M-ary tree, Binary tree), 上面后一类树是前类树的特例

   具体分析了binary Tree,  有以下几个性质:

1.  ordered forest和一个binary tree 有一一对应关系
2. N个internal Node, external node 有N+1
3. N个internal Node 有 N+1个link指向external Node, N-1 个link指向internal Node
4. N个internal Node的path比它的external node的path小2N
5. N个internal Node 的高度最高是N , 最低是lg(N)
6. N个internal Node 的internal node tree path length 最大是N*(N-1)/2  最小是N*lg(N/4)

• 基本的排序算法(elementary sorts)
• 快速排序(quik-sort)
• 归并和归并排序(merge and merge-sort)
• 优先队列和堆排序(priority queue and heap sort)
• Radix 排序(Radix sort)
• 特殊目的排序(Special purpose Sort)

   In place 排序, 就是要求空间复杂度最小的拍序, 很有意思

• 基本结构
• 平衡搜索树(Balanced BST)

   考虑从三个思路实现平衡( randomized, optimized, amortized), 并介绍相应的BST( Splay Tree, red-black tree, 2-3-4 树)

•  哈希和哈希搜索(hash and hash search)，　才用以下两种思路进行分类
  • 采用什么hash涵数
    1. 素数取余法，　具体最多用universal hash fucntion
  • 如何解决hash碰撞(collision resolution)
    1. 用list方法
    2. 线性hash(linear hash)
    3. 动态hash(dynamic hash)
• Radix搜索

      著名的有trie

• 外部搜索(External Search)

    主要介绍了基本的外部搜索结构但是没有展开, 有以下两种

    BTree 和External Hash

•  图的定义和性质
• 图搜索(Graph search)
• 有向图和DAG图(Digraph和DAG)
• 最小生成树(minimum span tree)
• 最短路径(Shortest path)
• 网络流(netWork flow)

1. 经验分析（empirical analysis）

   它的就是写一个算法正确的完整的实现，产生输入的测试数据，然后测试实现的性能， 对算法进行评价.

  根据测试数据可分下面三种:

• 实际输入数据
• 随机数据
• perverse 数据

   经验分析，还是比较容易实现。缺点是，复杂的算法实现起来非常费时，对整个算法的总体性能，不能够完整的给出

   2. 数学分析(mathematical analysis)

     数学分析，我们得到算法最坏情况(worst case)和平均情况（average case）的时间复杂读T(n)和空间复杂度S(n).

   T（n), S(n)就是个涵数，给出n情况下，所需的时间和空间

   显然数学分析是我们对算法运用于实际更有把握， 分析出来更具有信息性. 缺点是对复杂的算法，得到T(n)和S(n)比是一见容易的事情

二、大O表示法

     定义: 对于个涵数g(n)是O(f(n)) ,如过存在c > 0 n0 > 0, 如果对于任意n > n0 有g(n) < cf(n). 称函数g(n)以f(n)为界或者称g(n)囿于f(n)。记作g(n)=O(f(n))。

   我们常用大O表示法表示一个算法时间复杂性。大O表示有上界， 由定义T(n) = O(n), 显然T(n) = O(n^2). 它给了一个上界， 不是一个上确界。但是人们习惯当然用前者。 此外一个问题本身有起复杂性， 当算法的复杂性达到问题复杂性的的下界， 这个算法就是最优算法了

三、常用算法的复杂度

1. T(n) = T(n-1) + n ; T(1) = 1;

        T(n) = O(n(n+1)/2)

         具有此特征的典型算法就是Selection Sort

2. T(n) = T(n/2) + 1 ; T(1) = 1

      T(n) = O(lg(n))

     具有此特征的典型算法就是Binary Search

3. T(n) = T(n/2) + n; T(1) = 0

      T(n) = O(2n)

4. T(n) = 2T(n/2) + n; T(1) = 1;

      T(n) = O(nlg(n))

    具有此特征的典型算法就是merge sort

5. T(n)  = 2T(n/2) +1; T(1) = 1;

     T(n) = 0(n)

    具有此特征的典型算法就是

 6. Harmony 数

   T(n) = 1 + 1/2 + 1/3 + ... + 1/n, 那么T(n)就叫和谐数

   T(n) = ln(n) + O(1);

7. Fibonacci数

   T(n) = T(n-1) + T(n -2)

8. N!  数

   T(n) = n!

   T(n) = (n/e) ^n

四、Guarantee、Predicate、Limitation

   这三个是非常有意思的概念

1.Guarantee

    如果一个算法在最坏的情况下, 时间复杂度是O(f(n)), 显然对每一次运算, 我们保证(guarantee)它的时间是不O(f(n)), 所以

我们也就找到下界了

2. Limitation

1. CPU的高速缓存（Ｌcache)和普通内寸的折衷
2. 普通内存，和硬盘的折衷
3. 数据库中，数据内存的缓存和硬盘的数据
4. 数据结构中，　部分的内存Hash和磁盘Hash

  显然这是一种很好的解决问题的模式．

　那么如何在软件算法上实现这种解决模式呢？　当然我们可以想出解决问题的完美模式！　

但这样会增加难度，增加bugs的风险！　如果时间紧，要求不高，下面的方式就很直接．

下面以可回存在硬盘上的Hash结构为例. 有以下几步;

1. 写一个内存的hash数据结构
2. 写一个磁盘的hash数据结构
3. 写个程序，简单的把两个对象结合一下，　就是先把数据放如内存对象，　超过限制就放入磁盘. 查询的时候先到内存，找不到，到磁盘找!

这是一个简单的思路，　看起来不起眼，但是确实能解决问题！　

对于沉迷于技术的人来说，　这个应该给我们一个很好的思考！　

就是用技术的时候，应该考虑结合技术的方法和模式．　

另外不是先进的技术越好. 技术是为应用和解决问题而生的，　不能为技术而技术啊

1. 实现localize的功能

               eclipse 提供功能,使我们轻易的从源程序中提取常量的String信息放如 properies文件中, 轻松实现localization

          2. refactor功能

• 类改名
• 提取Interface

1.  IDE的功能,分为四个部分
   • Npt

                       具体叫Notation processing tool, 针对 java提供的源文件的的说明信息的格式, 使用方法, 和一写关键字.

                        这个不是很重要.

• Core

                      充分理解, Eclipse 提供 的开发功能的核心. 尤其要理解它的incremental build的原理. 使我门编写大型程序,

                      尽量少用build, 因为一次全体build, 要耗费半个小时, 大大影响开发, 而且影响开发心情. 如果不小心弄的全体

                     build 一两次, 一天的工夫就没.

• Debugger

                      充分理解 它提供的debugger功能.

1. 断点的形式,
2. remote debug功能                 
• UI
1. AOP
2. ANT

• introduction

1. 加入调试信息
2. 测算执行时间

     对与数据库编成,更有意义了比如

1. 加入权限检查
2. 实现事物功能
3. 实现日志管理

    目前我们编成时,对方法调用,常用的方法是

1. 仔细检查每个函数,并细心的插入预处理,和后处理
2. 编写一个代理类,实现这些接口, 然后委派原来的实现.

 后者是一个简洁的办法,因为预处理,和后处理代码和实现是分离的,但是她需要大量重复的编码工作.

下面介绍的利用java.lang.reflection包提供的接口InvocationHandler和Proxy类实现代理, 可以大大减轻编码的工作

• Implementation

      看下面我实现的一个代码:

       package beasts;

public interface DogInterface {

 /* (non-Javadoc)
  * @see beasts.DogInterface#walk()
  */
 public int walk();

 /* (non-Javadoc)
  * @see beasts.DogInterface#bark()
  */
 public String bark();

}

////////////////////////////////////////////////////

package beasts;

import java.lang.reflect.InvocationHandler;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;

public class DogInvocationHandler implements InvocationHandler {

 protected Object dog;
 
 public DogInvocationHandler(Object dog){
  this.dog = dog;
 }
 
 public Object invoke(Object proxy, Method method, Object[] args)
   throws Throwable {
  Object result = null;
  try{
   System.out.println("Stanley send command: ");
   result = method.invoke(dog, args);
  } catch(InvocationTargetException e){
   e.printStackTrace();
  } finally{
   System.out.println("Command finished:" + result);
  }
  return result;
 }

}

////////////////////////////////////////////////////////////

package beasts;

import java.lang.reflect.Proxy;

public class Dog implements DogInterface {
 
 private String name;
 public Dog(String name){
  this.name = name;
 }
 /* (non-Javadoc)
  * @see beasts.DogInterface#walk()
  */
 /* (non-Javadoc)
  * @see beasts.DogInterface#walk()
  */
 public int  walk(){
  System.out.println(name +" start walking ");
  return 3;
 }

 /* (non-Javadoc)
  * @see beasts.DogInterface#bark()
  */
 /* (non-Javadoc)
  * @see beasts.DogInterface#bark()
  */
 public String bark(){
  return name + " barking";
 }
 
 public static void main(String[] arg){
  DogInterface dog = new Dog("snoopy");
      DogInterface pdog = (DogInterface)Proxy.newProxyInstance(dog.getClass().getClassLoader(), Dog.class.getInterfaces(), new DogInvocationHandler(dog));
  pdog.walk();

 }
}
/////////////////////////////////////////////////////////////////

• conclusion

     显然动态代理, 使我们不必为每个实现写一个proxy,大大减轻我们的工作, 而且使我们的程序更加简洁.

    当然有些缺陷了

• 要是实现动态代理,再嵌套动态代理,可能不行
•  newProxyInstance(ClassLoader loader,
         Class[] interfaces,
         InvocationHandler h)的第二个参数必须是Interface, 如果实现没有Interface就不行, 这是一个问题