What: TclRAL
Where: http://tclral.sf.net/
Description: Tcl Relational Algebra Library is a C based
extension that introduces tuple and relation data types
and a set of commands that operate on them.
Currently at version 0.8.3 .
Updated: 06/2007
Contact: See web siteSee also Transitive Closure.
See also Relations as Stacks.
See also Relations as Object Oriented Stacks.
See also crosstab a la Relations.
AM - 1 Oct 2006
I recently released Version 0.8 of TclRAL and thought that now was an appropriate time to make this page a bit more active for anyone that may be interested in the extension and wish to ask questions or post examples.
Version 0.8 is a complete rewrite of the extension to improve the code base and lay in a more maintainable structure. The major new feature of 0.8 is referential integrity checking. My current vision for the future is (roughly):
I won't be so bold as to state a time frame for all of this, but as I use the extension myself I am as anxious to see it improve as anyone.
AM - 30 Jan 2007
This is small example that I worked up showing one of the more unusual operations in TclRAL, transitive closure. This is useful for dealing with hierarchical or graph structured data. In this small example, we deal with file include dependencies in "C" source.
# One common activity in building software is determining the include
# dependencies of files. Because one file can include another which can itself
# include other files, in general the dependencies form a graph. So one
# question that often needs to be answered is for a given file, what is the set
# of files that needs to be checked in order to determine if the given file is
# out of date with respect to its dependencies.
#
# This example shows a method of computing the dependencies of a "C" file using
# TclRAL. The strategy is to examine each file to determine just which other
# files it is dependent upon and add these binary dependencies into a relvar.
# Then computing the transitive close of the relation value will give us the
# list of dependencies.
package require ral
namespace import ::ral::*
# We need a relvar to hold the dependency information. Each tuple of the
# relvar value represents an edge in an implied graph of dependencies. The
# edge is denoted by the file names showing the "includes" dependency. N.B.
# that both attributes are used to form the single identifier of the relation.
# Also, "relation tclose" insists that the relation be binary (i.e. have only
# two attributes, which can always be achieved by projection, if necessary).
relvar create FileDep {
Relation
{FileName string DepFile string}
{{FileName DepFile}}
}
# Now we must populate the relvar. This proc is overly simplistic for
# "real world" use, but serves as a simple example. In practice we would
# probably need to worry about include paths, system includes, etc. etc.
# For this example, we will scan every line of the file looking for
# "# include" constructs.
package require fileutil
proc scanFile {filename} {
# Creating a relvar, creates an ordinary Tcl variable by the same name.
global FileDep
fileutil::foreachLine line $filename {
if {[regexp {#include\s+[<"](.*)[>"]} $line match inclFile]} {
# The "relvar insert" command throws an error when attempting to
# insert a duplicate. We catch this and go on since a duplicate
# here implies we are revisiting some previous dependency.
catch {relvar insert FileDep [list\
FileName [file tail $filename]\
DepFile $inclFile]} result
# Look to see if the file exists in the current directory and that
# we have not already scanned it. If all that is true, then we
# recursively look at what files it includes. We can tell if we
# have scanned the file by determining if there are any tuples in
# the "FileDep" relvar that have the FileName attribute set to the
# name of file that is included.
if {[file exists $inclFile] &&
[relation isempty [relation restrictwith $FileDep\
{$FileName eq $inclFile}]]} {
scanFile $inclFile
}
}
}
}
# Okay, pull a file name off the command line and scan it
set f [lindex $argv 0]
cd [file dirname $f]
set f [file tail $f]
scanFile $f
# The dependency graph has edges described by the tuples of the relvar.
puts [relformat $FileDep "File Dependencies"]
# The transitive closure algorithm, which came from Aho, Hopcroft and Ullman,
# has memory requirements that are O(N^2) and computation times O(N^3) where
# N is the number of nodes in the implied dependency graph. So large graphs
# can take some time. Here we time it just for fun.
puts [time {set closure [relation tclose $FileDep]} 1]
# The transitive close contains a tuple for every pair of file names where
# there is some path from the file to its included file. Thus if a --> b and
# b --> c and c --> d, then the transitive closure will contain a tuple for
# a --> d (among others). This implies the original relation value is a subset
# of the transitive closure.
puts [relformat $closure "Transitive Closure"]
# So a list of the ultimate dependencies of the file is a simple expression
# finding those tuples where the FileName attribute matches, projecting out
# the DepFile attribute and converting the result into a Tcl list.
set depList [relation list [relation project\
[relation restrictwith $closure {$FileName eq $f}] DepFile]]
# We could choose to put this out in "make" syntax, but a simple listing
# will do.
puts "$f depends upon:"
foreach depFile [lsort $depList] {
puts "\t$depFile"
}So if we run this on one of the source files to TclRAL, ral.c, we get:
+=====================+=====================+
|FileName |DepFile |
|string |string |
+=====================+=====================+
|ral.c |stdio.h |
|ral.c |string.h |
|ral.c |tcl.h |
|ral.c |ral_tuplecmd.h |
|ral_tuplecmd.h |tcl.h |
|ral_tuplecmd.h |ral_tupleobj.h |
|ral_tupleobj.h |tcl.h |
|ral_tupleobj.h |ral_utils.h |
|ral_utils.h |tcl.h |
|ral_tupleobj.h |ral_tupleheading.h |
|ral_tupleheading.h |ral_attribute.h |
|ral_attribute.h |tcl.h |
|ral_attribute.h |ral_utils.h |
|ral_tupleheading.h |ral_joinmap.h |
|ral_joinmap.h |ral_vector.h |
|ral_vector.h |stdio.h |
|ral_tupleheading.h |ral_vector.h |
|ral_tupleheading.h |stdio.h |
|ral_tupleobj.h |ral_tuple.h |
|ral_tuple.h |tcl.h |
|ral_tuple.h |ral_utils.h |
|ral_tuple.h |ral_attribute.h |
|ral_tuple.h |ral_tupleheading.h |
|ral_tuple.h |stdio.h |
|ral_tupleobj.h |ral_vector.h |
|ral.c |ral_relationcmd.h |
|ral_relationcmd.h |tcl.h |
|ral.c |ral_relationobj.h |
|ral_relationobj.h |tcl.h |
|ral_relationobj.h |ral_utils.h |
|ral_relationobj.h |ral_relationheading.h|
|ral_relationheading.h|ral_utils.h |
|ral_relationheading.h|ral_tupleheading.h |
|ral_relationheading.h|ral_vector.h |
|ral_relationheading.h|ral_joinmap.h |
|ral_relationheading.h|stdio.h |
|ral_relationobj.h |ral_relation.h |
|ral_relation.h |ral_utils.h |
|ral_relation.h |ral_relationheading.h|
|ral_relation.h |ral_tuple.h |
|ral_relation.h |ral_attribute.h |
|ral_relation.h |ral_vector.h |
|ral_relation.h |ral_joinmap.h |
|ral_relation.h |stdio.h |
|ral_relationobj.h |stdio.h |
|ral.c |ral_relvar.h |
|ral_relvar.h |tcl.h |
|ral_relvar.h |ral_vector.h |
|ral_relvar.h |ral_relation.h |
|ral_relvar.h |ral_joinmap.h |
|ral.c |ral_relvarobj.h |
|ral_relvarobj.h |tcl.h |
|ral_relvarobj.h |ral_relvar.h |
|ral_relvarobj.h |ral_relationheading.h|
|ral.c |ral_relvarcmd.h |
|ral_relvarcmd.h |tcl.h |
+=====================+=====================+
File Dependencies
-----------------
593 microseconds per iteration
+=====================+=====================+
|FileName |DepFile |
|string |string |
+=====================+=====================+
|ral.c |stdio.h |
|ral.c |string.h |
|ral.c |tcl.h |
|ral.c |ral_tuplecmd.h |
|ral.c |ral_tupleobj.h |
|ral.c |ral_utils.h |
|ral.c |ral_tupleheading.h |
|ral.c |ral_attribute.h |
|ral.c |ral_joinmap.h |
|ral.c |ral_vector.h |
|ral.c |ral_tuple.h |
|ral.c |ral_relationcmd.h |
|ral.c |ral_relationobj.h |
|ral.c |ral_relationheading.h|
|ral.c |ral_relation.h |
|ral.c |ral_relvar.h |
|ral.c |ral_relvarobj.h |
|ral.c |ral_relvarcmd.h |
|ral_tuplecmd.h |stdio.h |
|ral_tuplecmd.h |tcl.h |
|ral_tuplecmd.h |ral_tupleobj.h |
|ral_tuplecmd.h |ral_utils.h |
|ral_tuplecmd.h |ral_tupleheading.h |
|ral_tuplecmd.h |ral_attribute.h |
|ral_tuplecmd.h |ral_joinmap.h |
|ral_tuplecmd.h |ral_vector.h |
|ral_tuplecmd.h |ral_tuple.h |
|ral_tupleobj.h |stdio.h |
|ral_tupleobj.h |tcl.h |
|ral_tupleobj.h |ral_utils.h |
|ral_tupleobj.h |ral_tupleheading.h |
|ral_tupleobj.h |ral_attribute.h |
|ral_tupleobj.h |ral_joinmap.h |
|ral_tupleobj.h |ral_vector.h |
|ral_tupleobj.h |ral_tuple.h |
|ral_utils.h |tcl.h |
|ral_tupleheading.h |stdio.h |
|ral_tupleheading.h |tcl.h |
|ral_tupleheading.h |ral_utils.h |
|ral_tupleheading.h |ral_attribute.h |
|ral_tupleheading.h |ral_joinmap.h |
|ral_tupleheading.h |ral_vector.h |
|ral_attribute.h |tcl.h |
|ral_attribute.h |ral_utils.h |
|ral_joinmap.h |stdio.h |
|ral_joinmap.h |ral_vector.h |
|ral_vector.h |stdio.h |
|ral_tuple.h |stdio.h |
|ral_tuple.h |tcl.h |
|ral_tuple.h |ral_utils.h |
|ral_tuple.h |ral_tupleheading.h |
|ral_tuple.h |ral_attribute.h |
|ral_tuple.h |ral_joinmap.h |
|ral_tuple.h |ral_vector.h |
|ral_relationcmd.h |tcl.h |
|ral_relationobj.h |stdio.h |
|ral_relationobj.h |tcl.h |
|ral_relationobj.h |ral_utils.h |
|ral_relationobj.h |ral_tupleheading.h |
|ral_relationobj.h |ral_attribute.h |
|ral_relationobj.h |ral_joinmap.h |
|ral_relationobj.h |ral_vector.h |
|ral_relationobj.h |ral_tuple.h |
|ral_relationobj.h |ral_relationheading.h|
|ral_relationobj.h |ral_relation.h |
|ral_relationheading.h|stdio.h |
|ral_relationheading.h|tcl.h |
|ral_relationheading.h|ral_utils.h |
|ral_relationheading.h|ral_tupleheading.h |
|ral_relationheading.h|ral_attribute.h |
|ral_relationheading.h|ral_joinmap.h |
|ral_relationheading.h|ral_vector.h |
|ral_relation.h |stdio.h |
|ral_relation.h |tcl.h |
|ral_relation.h |ral_utils.h |
|ral_relation.h |ral_tupleheading.h |
|ral_relation.h |ral_attribute.h |
|ral_relation.h |ral_joinmap.h |
|ral_relation.h |ral_vector.h |
|ral_relation.h |ral_tuple.h |
|ral_relation.h |ral_relationheading.h|
|ral_relvar.h |stdio.h |
|ral_relvar.h |tcl.h |
|ral_relvar.h |ral_utils.h |
|ral_relvar.h |ral_tupleheading.h |
|ral_relvar.h |ral_attribute.h |
|ral_relvar.h |ral_joinmap.h |
|ral_relvar.h |ral_vector.h |
|ral_relvar.h |ral_tuple.h |
|ral_relvar.h |ral_relationheading.h|
|ral_relvar.h |ral_relation.h |
|ral_relvarobj.h |stdio.h |
|ral_relvarobj.h |tcl.h |
|ral_relvarobj.h |ral_utils.h |
|ral_relvarobj.h |ral_tupleheading.h |
|ral_relvarobj.h |ral_attribute.h |
|ral_relvarobj.h |ral_joinmap.h |
|ral_relvarobj.h |ral_vector.h |
|ral_relvarobj.h |ral_tuple.h |
|ral_relvarobj.h |ral_relationheading.h|
|ral_relvarobj.h |ral_relation.h |
|ral_relvarobj.h |ral_relvar.h |
|ral_relvarcmd.h |tcl.h |
+=====================+=====================+
Transitive Closure
------------------
ral.c depends upon:
ral_attribute.h
ral_joinmap.h
ral_relation.h
ral_relationcmd.h
ral_relationheading.h
ral_relationobj.h
ral_relvar.h
ral_relvarcmd.h
ral_relvarobj.h
ral_tuple.h
ral_tuplecmd.h
ral_tupleheading.h
ral_tupleobj.h
ral_utils.h
ral_vector.h
stdio.h
string.h
tcl.hAM - 6 Feb 2007
Released Version 0.8.1. This version is script compatible with 0.8 and includes some new commands and command options. Most notable is the ability to trace relvars in much the same manner that one can trace ordinary Tcl variables.
See Andrew Mangogna.
Category Package | Category Mathematics | Category Data Structure