 | Level: Introductory Paul BrownIBM
Chris Bosch, Contributing Author, IBM
20 Dec 2001 Creates an Informix DataBlade with a new type that solves hierarchical data queries. Includes C source code.
© 2001 International Business Machines Corporation.
All rights reserved.
Overview This demonstration DataBlade™ module implements a variable-length
opaque data type (Node), its support routines, and other user-defined
routines for accessing and manipulating data elements of that type.
The Node data type is intended to resolve one of the hardest
problems in relational databases; transitive closure. It doesn't
resolve the problem completely, but it does get us 80% of the way. The
transitive closure problem is endemic to data management problems, and
not particularly well addressed by the relational model. The same
basic problem is found modeling organizational hierarchies, networks,
manufacturing and process control databases. There are a couple of optimizations for addressing the transitive
closure problem, dealt with at length in Joe Celko's "SQL For Smarties"
(Morgan Kaufmann, 1995). However, all of these optimizations introduce
one of several kinds of anomalies, requiring that the database change
more than one tuple in response to more than one fact. Also, the SQL
needed to write the operations over the tree are complex, difficult to
optimize and execute and -- even at their very best -- slow.
The Node data type introduced in this document and implemented by this
demonstration DataBlade module provides a quite lateral solution to this
problem. The basic idea is to create a type and operations over
that type which models the tree structure itself and to represent the
facts of the tree structure in that way, rather than reduce these
facts to overly simple relations. The external representation of the Node data type is an ordinal number (integer greater than 0), followed by either a single .0 or a set of ordinal numbers separated by dots. Examples of valid and invalid Node data elements are presented below.
Valid Nodes
{ 1.0, 1.1, 1.1.1, 1.2, 1.2.1, 999.0, 999.1.999 }
Invalid Nodes
{ 0, 0.0, 0.1, 1.0.1, 1.1.0, 1.-1.2, 1.A.4 }
There are several things to note about this type. First, it isn't
enough to treat this as a simple string. The ordering of a set of Node
objects is not the same as the conventional string ordering of their
representations. Nor is it possible to define a collation sequence
which would result in the correct ordering. This makes is impossible to
use this kind of approach with a DBMS which does not support extensible
types. The sorting algorithms necessary can be written outside the
database, and client applications can make use of the approach when
comparing two values. However, this has obvious limitations. Included
below is an example showing the how data elements are ordered
differently when they are treated as Nodes rather than as strings.
T is the following unordered set of data elements;
T := { 1.2, 1.0, 1.12, }
T ordered as strings;
T := { 1.0, 1.12, 1.2 }
T ordered as Nodes;
T := { 1.0, 1.2, 1.12 }
Secondly, incrementing elements of the Node data type is more
complex than incrementing elements of a totally-ordered discrete data
type such as the set of integers. Incrementing a Node (adding one to
the least significant value in the Node) does not guarantee that the
resulting data element will be the smallest Node greater than the
original as would be guaranteed by the increment operation for integers. For example, given the following set of Node objects, T := { 1.0, 1.2,
1.2.1, 1.2.2 }, we find there are Nodes between Node 1.2 and
Increment (1.2) = 1.3.
1.2 < 1.3
1.2 < 1.2.1 < 1.3
1.2 < 1.2.2 < 1.3
|
In general, there may be Nodes in any given set of Nodes which are
between a Node and its increment. Furthermore, note that the Nodes
which are 'BETWEEN' Node N and Increment(N) are 'Under' Node N. That
is, both Nodes 1.2.1 and 1.2.2 are 'Under' 1.2. This 'Under' relation
is the same as saying that the Node is BETWEEN the Node and its
Increment. This is an extremely interesting and valuable property of
the Node data type described here. There are many other interesting properties of the Node data type
that can be exploited in a variety of applications. To learn more
about the functionality provided by the Node data type, download this
demonstration DataBlade module and experiment with it. The sections to
follow describe the software required for working with the Node
DataBlade module as well as the procedures for downloading the
distribution, building the shared object library, installing the
DataBlade module, and registering the DataBlade module in a database.
Examples demonstrating most of the Node DataBlade module's User-Defined
Routines (UDRs) are included at the end of this document.
Software Requirements
To build and run Node.1.0, you need a C compiler to
build the shared object and Informix® Dynamic Server with
Universal Data Option (IDS-UD) 9.14 or higher. Node.1.0 was tested with the software releases
listed below:
UNIX:
Solaris 2.5.1 IDS/UDO 9.14.UC6 SUNpro C Compiler
NT:
NT 4.0, Service Pack 3 IDS/UDO 9.14.TC4 Microsoft Visual C++ 6.0
Getting Started
Download the distribution
Download the Node.1.0.tar.Z
distribution file, found in the Download section, and uncompress and unarchive it using utilities
available for your platform as follows:
UNIX:
To uncompress and unarchive the distribution file under UNIX, enter the
following command at the shell prompt:
zcat Node.1.0.tar.Z | tar xvf -
|
NT:
To uncompress and unarchive the distribution file under NT, use WinZip
or a similar utility that can handle compressed UNIX tar files.
The distribution is extracted into a directory hierarchy under
Node.1.0. The directory contents, summarized below,
can be viewed on-line by clicking
here.
demo/
Demo scripts that exercise the UDRs.
scripts/
SQL registration scripts. The contents of this directory should be
copied to
$INFORMIXDIR/extend/Node.1.0.
src/c
Source code for the UDRs.
Node.ibs
BladeSmith project generated with BladeSmith version 3.70.TC1.
Build the shared object library The distribution for this demo DataBlade comes with pre-built shared
object libraries for Solaris 2.5.1 and Windows NT 4.0. If you are not
on one of those platforms or if you make modifications to the demo
source code, you must recompile for your platform using the
instructions provided below.
UNIX:
To build your DataBlade module on UNIX, first transport the
generated files to your UNIX machine. On your UNIX machine, set the
TARGET environment variable to the location/filename of the
platform-specific make include file. For Solaris, this is
"$INFORMIXDIR/incl/dbdk/makeinc.solaris".
UNIX.mak is the makefile used to build the DataBlade module under UNIX.
To build the DataBlade module, type:
Detailed instructions for building a UNIX shared object library are
included in the "DataBlade Developers Kit User Guide".
NT:
If you intend to compile your DataBlade module for NT, you may use either
the WinNT.mak or Node.mak makefiles.
To build your DataBlade module from the command line, type
nmake -s -nologo -f WinNT.mak
|
To load your DataBlade module's source files into Microsoft Visual C++
version 4.1, select "Open Workspace..." from the menus. When using
versions 4.2 or later, select "Open Workspace..." from the menus. For
the project name, type Node.mak. For version 5.0 and later,
the makefile is automatically converted.
Detailed instructions for building an NT dynamically-linked library
(DLL) are included in the "DataBlade Developers Kit User Guide".
Install the DataBlade module Login as user informix, change to the Node.1.0 directory in which
the distribution has been unarchived, and follow the steps outlined
below for your platform.
UNIX:
mkdir $INFORMIXDIR/extend/Node.1.0
cp ./scripts/* $INFORMIXDIR/extend/Node.1.0
cp ./src/solaris-sparc/Node.bld $INFORMIXDIR/extend/Node.1.0
|
NT:
mkdir %INFORMIXDIR%\extend\Node.1.0
cp .\scripts\* %INFORMIXDIR%\extend\Node.1.0
cp .\src\WinNT-i386\Node.bld %INFORMIXDIR%\extend\Node.1.0
|
Register the DataBlade module in a database Start BladeManager from either the UNIX system prompt or the MS-DOS
command prompt as appropriate for your platform and register the demo
DataBlade module as shown in the example below.
blademgr
shm>register Node.1.0 demodb
Register module Node.1.0 into database demodb? [Y/n]y
Registering DataBlade module... (may take a while).
DataBlade Node.1.0 was successfully registered in database demodb.
shm>bye
Disconnecting...
|
User-Defined Types (UDTs)
This demonstration DataBlade module defines a variable-length opaque
data type as follows:
create opaque type Node(
internallength = variable,
maxlen = 64,
alignment = 4
);
|
User-Defined Routines (UDRs)
Basic Text Input/Output User-defined routines supporting basic text input/output for the
Node data type are listed below. Binary Send/Receive User-defined routines supporting binary send/receive with clients for the
Node data type are listed below. Text File Import/Export User-defined routines supporting text file import/export for the
Node data type are listed below. Binary File Import/Export User-defined routines supporting binary file import/export for the
Node data type are listed below. Type Compare and B-tree Indexing Support User-defined routines supporting type comparison and b-tree indexing
operations for the Node data type are listed below. Compare (Node,Node) returns integer Equal (Node,Node) returns boolean NotEqual (Node,Node) returns boolean LessThan (Node,Node) returns boolean GreaterThan (Node,Node) returns boolean LessThanOrEqual (Node,Node) returns boolean GreaterThanOrEqual (Node,Node) returns boolean
Other UDRs Other user-defined routines for accessing and manipulating
Node data elements are listed below. Length (Node) returns integer GetMember (Node,integer) returns integer GetParent (Node) returns Node Increment (Node) returns Node Increment (Node,integer) returns Node IsParent (Node,Node) returns boolean IsChild (Node,Node) returns boolean IsAncestor (Node,Node) returns boolean IsDescendant (Node,Node) returns boolean Ancestors (Node) returns Node NewLevel (Node) returns Node Graft (Node,Node,Node) returns Node
Examples of Use
Type compare support functions
SELECT
a.n a,
b.n b,
compare(a.n,b.n) compare_a_b,
a.n = b.n eq_a_b,
a.n != b.n neq_a_b
FROM
nodes a,
nodes b;
a b compare_a_b eq_a_b neq_a_b
-----------------------------------------------------------------
1.0 1.0 0 t f
1.2 1.0 1 f t
1.2.1 1.0 1 f t
3.0 1.0 1 f t
3.1 1.0 1 f t
1.0 1.2 -1 f t
1.2 1.2 0 t f
1.2.1 1.2 1 f t
3.0 1.2 1 f t
3.1 1.2 1 f t
1.0 1.2.1 -1 f t
1.2 1.2.1 -1 f t
1.2.1 1.2.1 0 t f
3.0 1.2.1 1 f t
3.1 1.2.1 1 f t
1.0 3.0 -1 f t
1.2 3.0 -1 f t
1.2.1 3.0 -1 f t
3.0 3.0 0 t f
3.1 3.0 1 f t
1.0 3.1 -1 f t
1.2 3.1 -1 f t
1.2.1 3.1 -1 f t
3.0 3.1 -1 f t
3.1 3.1 0 t f
25 rows affected by select command
|
B-tree indexing support functions
SELECT
a.n a,
b.n b,
a.n >= b.n gte_a_b,
a.n > b.n gt_a_b,
a.n < b.n lt_a_b,
a.n <= b.n lte_a_b
FROM
nodes a,
nodes b;
a b gte_a_b gt_a_b lt_a_b lte_a_b
------------------------------------------------------------------------------
1.0 1.0 t f f t
1.2 1.0 t t f f
1.2.1 1.0 t t f f
3.0 1.0 t t f f
3.1 1.0 t t f f
1.0 1.2 f f t t
1.2 1.2 t f f t
1.2.1 1.2 t t f f
3.0 1.2 t t f f
3.1 1.2 t t f f
1.0 1.2.1 f f t t
1.2 1.2.1 f f t t
1.2.1 1.2.1 t f f t
3.0 1.2.1 t t f f
3.1 1.2.1 t t f f
1.0 3.0 f f t t
1.2 3.0 f f t t
1.2.1 3.0 f f t t
3.0 3.0 t f f t
3.1 3.0 t t f f
1.0 3.1 f f t t
1.2 3.1 f f t t
1.2.1 3.1 f f t t
3.0 3.1 f f t t
3.1 3.1 t f f t
25 rows affected by select command
|
Length function
SELECT
a.n a,
length(a.n) len_a
FROM
nodes a;
a len_a
--------------------------
1.0 1
1.2 2
1.2.1 3
3.0 1
3.1 2
5 rows affected by select command
|
GetMember function
SELECT
a.n a,
getmember(a.n, 1) getmem_a_1,
getmember(a.n, 2) getmem_a_2,
getmember(a.n, 3) getmem_a_3
FROM
nodes a;
a getmem_a_1 getmem_a_2 getmem_a_3
----------------------------------------------------
1.0 1 0 NULL
1.2 1 2 NULL
1.2.1 1 2 1
3.0 3 0 NULL
3.1 3 1 NULL
5 rows affected by select command
|
GetParent function
SELECT
a.n a,
getparent(a.n) getpar_a
FROM
nodes a;
a getpar_a
--------------------------
1.0 NULL
1.2 1.0
1.2.1 1.2
3.0 NULL
3.1 3.0
5 rows affected by select command
|
Increment functions
SELECT
a.n a,
increment(a.n) incr_a,
increment(a.n,1) incr_a_1,
increment(a.n,2) incr_a_2,
increment(a.n,3) incr_a_3
FROM
nodes a;
a incr_a incr_a_1 incr_a_2 incr_a_3
-----------------------------------------------------------------
1.0 2.0 2.0 1.1 NULL
1.2 1.3 2.0 1.3 NULL
1.2.1 1.2.2 2.0 1.3 1.2.2
3.0 4.0 4.0 3.1 NULL
3.1 3.2 4.0 3.2 NULL
5 rows affected by select command
|
IsAncestor, IsParent, IsChild, IsDescendant functions
SELECT
a.n a,
b.n b,
isancestor(a.n,b.n) isanc_a_b,
isparent(a.n,b.n) ispar_a_b,
ischild(a.n,b.n) ischi_a_b,
isdescendant(a.n,b.n) isdes_a_b
FROM
nodes a,
nodes b;
a b isanc_a_b ispar_a_b ischi_a_b isdes_a_b
------------------------------------------------------------------------------
1.0 1.0 f f f f
1.2 1.0 f f t t
1.2.1 1.0 f f f t
3.0 1.0 f f f f
3.1 1.0 f f f f
1.0 1.2 t t f f
1.2 1.2 f f f f
1.2.1 1.2 f f t t
3.0 1.2 f f f f
3.1 1.2 f f f f
1.0 1.2.1 t f f f
1.2 1.2.1 t t f f
1.2.1 1.2.1 f f f f
3.0 1.2.1 f f f f
3.1 1.2.1 f f f f
1.0 3.0 f f f f
1.2 3.0 f f f f
1.2.1 3.0 f f f f
3.0 3.0 f f f f
3.1 3.0 f f t t
1.0 3.1 f f f f
1.2 3.1 f f f f
1.2.1 3.1 f f f f
3.0 3.1 t t f f
3.1 3.1 f f f f
25 rows affected by select command
|
Ancestors iterator function
EXECUTE FUNCTION ancestors('1.2.3.4.5.6.7.8.9');
(expression)
---------------
1.2.3.4.5.6.7.8
1.2.3.4.5.6.7
1.2.3.4.5.6
1.2.3.4.5
1.2.3.4
1.2.3
1.2
1.0
8 rows affected by execute function command
|
NewLevel function
SELECT
a.n a,
newlevel(a.n) newlvl_a
FROM
nodes a;
a newlvl_a
--------------------------
1.0 1.1
1.2 1.2.1
1.2.1 1.2.1.1
3.0 3.1
3.1 3.1.1
5 rows affected by select command
|
Graft function
SELECT
a.n a,
b.n b,
c.n c,
graft(a.n,b.n,c.n) graft_a_b_c
FROM
nodes a,
nodes b,
nodes c
WHERE
isancestor(a.n, c.n);
a b c graft_a_b_c
----------------------------------------------------
1.0 1.0 1.2 1.2
1.0 1.2 1.2 1.2.2
1.0 1.2.1 1.2 1.2.1.2
1.0 3.0 1.2 3.2
1.0 3.1 1.2 3.1.2
1.0 1.0 1.2.1 1.2.1
1.0 1.2 1.2.1 1.2.2.1
1.0 1.2.1 1.2.1 1.2.1.2.1
1.0 3.0 1.2.1 3.2.1
1.0 3.1 1.2.1 3.1.2.1
1.2 1.0 1.2.1 1.1
1.2 1.2 1.2.1 1.2.1
1.2 1.2.1 1.2.1 1.2.1.1
1.2 3.0 1.2.1 3.1
1.2 3.1 1.2.1 3.1.1
3.0 1.0 3.1 1.1
3.0 1.2 3.1 1.2.1
3.0 1.2.1 3.1 1.2.1.1
3.0 3.0 3.1 3.1
3.0 3.1 3.1 3.1.1
20 rows affected by select command
|
IBM, DB2, Informix, and WebSphere are trademarks or registered trademarks of IBM Corporation in the United States, other countries, or both. Windows and Windows NT are registered trademarks
of Microsoft Corporation in the United States, other countries,
or both.
Java and all Java-based trademarks and logos
are trademarks or registered trademarks of Sun Microsystems, Inc.
in the United States, other countries, or both. Other company, product, and service names may
be trademarks or service marks of others. IBM
copyright and trademark information
Download | Description | Name | Size | Download method |
|---|
| Distribution file | Node.1.0.tar.Z | 200 KB | HTTP |
|---|
Resources Learn
Get products and technologies
-
Build your next development project with
IBM
trial software, available for download directly from developerWorks.
Discuss
About the authors | | | Paul Brown is an IBM contributing author. |
| | | Chris Bosch is an IBM contributing author. |
Rate this page
| |
