From ORACLE:
"In some cases, the optimizer can use a previously calculated value rather than executing a user-written function.
This is only safe for functions that behave in a restricted manner. The function must return the same output 
return value for any given set of input argument values.

The function's result must not differ because of differences in the content of package variables or the 
database, or session parameters such as the globalization support parameters. Furthermore, if the function 
is redefined in the future, then its output return value must be the same as that calculated with the prior 
definition for any given set of input argument values. Finally, there must be no meaningful side effects to 
using a precalculated value instead of executing the function again.

The creator of a function can promise to the Oracle server that the function behaves according to these 
restrictions by using the keyword DETERMINISTIC when declaring the function with a CREATE FUNCTION statement 
or in a CREATE PACKAGE or CREATE TYPE statement. The server does not attempt to verify this declaration--even 
a function that obviously manipulates the database or package variables can be declared DETERMINISTIC. It is 
the programmer's responsibility to use this keyword only when appropriate."


One of the requirements of creating a function based index is that the function be 'deterministic'.
What is a deterministic function? A deterministic function returns same value for the same input.
An example demonstrates how and why this is necessary.


SQL> select * from tyu;

        C1
----------
         0
         1
         2

SQL> show parameters rewrite

NAME                                 TYPE        VALUE
------------------------------------ ----------- ------------------------------
query_rewrite_enabled                string      TRUE
query_rewrite_integrity              string      TRUSTED
SQL> exec dbms_application_info.set_client_info(0);

PL/SQL procedure successfully completed.

SQL> create or replace function det_func(p1 number) return number
  2  deterministic
  3  as
  4  x number;
  5  begin
  6  dbms_application_info.read_client_info(x);
  7  return p1+x;
  8  end;
  9  /

Function created.

SQL> drop index det_func_idx;

Index dropped.

SQL> create index det_func_idx on tyu(det_func(c1));

Index created.

SQL> set autotrace on explain
SQL> select * from tyu where det_func(c1)=2;

        C1
----------
         2


Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=CHOOSE (Cost=1 Card=1 Bytes=2)
   1    0   TABLE ACCESS (BY INDEX ROWID) OF 'TYU' (Cost=1 Card=1 Byte
          s=2)

   2    1     INDEX (RANGE SCAN) OF 'DET_FUNC_IDX' (NON-UNIQUE) (Cost=
          1 Card=1)




SQL> select /*+ full(tyu) */ * from tyu where det_func(c1)=2;

        C1
----------
         2


Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=CHOOSE (Cost=2 Card=1 Bytes=2)
   1    0   TABLE ACCESS (FULL) OF 'TYU' (Cost=2 Card=1 Bytes=2)


-- Note that 2 different plans return the same result


SQL> set autotrace off
SQL> exec dbms_application_info.set_client_info(5);

PL/SQL procedure successfully completed.

SQL> select * from tyu where det_func(c1)=2;

        C1
----------
         2

SQL> select /*+ full(tyu) */ * from tyu where det_func(c1)=2;

no rows selected

SQL> 

-- Two differnet plans return different results.
-- This is why the function has to be deterministic. However, ORACLE can not determine if a function
-- is truely deterministic. It is up to the developer to make sure that a function is indeed deterministic.
-- The 'deterministic' key word serves as sort of a reminder to the developer about the deterministic
-- fact of the function.


-- This function is deterministic, since it returns same result for the same input

create or replace function func2_(c1 number) return number
  deterministic
  as
  x number;
  begin
  dbms_application_info.read_client_info(x);
  dbms_application_info.set_client_info(x+1);
  return c1+10;
  end;

-- The function used in this demo is NOT deterministic.