I will be showcasing progress of the work I’ve done using the Virtools Development Platform. I had a class that taught this tool at OSU called NMC 487 in Spring 2007.

“The Virtools development platform has been widely used in the video game market (prototyping and rapid development), as well as for other highly interactive 3D experiences, in web marketing, virtual product maintenance.”

No tags

I presented my final project for CS440 last Wednesday. Here are the slides my group used.

Sky Express (pdf)

Final Write-Up

No tags

I had a homework question that asked me to implement left outer join for the Sort-Merge Join algorithm for external sorting.

To compute a left outer join, we use the left relation as the outer loop or single-loop because every tuple in the left relation must appear in the result. If there are matching tuples in the other relation, the joined tuples are produced and saved in the result. However, if no matching tuple is found, the tuple is still included in the result but is padded with NULL values.

sort the tuples in R on attribute A;   ## assume R has n tuples (records)

sort the tuples in S on attribute B;    ## assume S has m tuples (records)

set i <- 1, j <- 1;

while (i <= n) and (j <= m)

## Use the left relation as the outer loop or single-loop because every tuple in the left relation must appear in the result.

do { if R(i)[A] > S(j)[B]  ##…Use the left outer join, because we don’t care about the right side.

                then set j <- j + 1

        elseif R(i)[A] < S(j)[B]

                then set i <- i + 1

else   {  ## If there are matching tuples in the other relation, the joined tuples are produced and     

             ##  saved in the result.

       ## R(i)[A] = S(j)[B], so we output a matched tuple

                       output the combined tuple <R(i), S(j)> to T;

                       ## output other tuples that match R(i), if any;

                       set l <- j + 1;

                       while (l <= m) and (R(i)[A] = S(l)[B])

                       do {  output the combined tuple <R(k), S(j)> to T;

                                 set k <- k + 1;

       }

       set i <- k, j <- l

                       ## for every tuple t_r from R that does not match any tuple in S

                       output the combined tuplpe <R(i), S(j)> to T PADDED WITH NULLS;

       }

}

No tags

In a database management system it is essential that a query be optimized as much as possible to eliminate redundant data that could slow down the system. Query Optimization is used to eliminate expensive paths of execution for a query graph (or tree); e.g, find the lowest cost.

Example of Transforming a Query:
Consider the query Q that states “Find the last
names of employees born after 1957 who work
on a project named ‘Aquarius’.”

In SQL, this query can be specified as:
SELECT LNAME
FROM EMPLOYEE, WORKS_ON, PROJECT
WHERE PNAME=‘Aquarius’ AND ESSN=SSN
AND PNUMBER=PNO
AND BDATE > ‘1957-12-31’;

One way the tree can be shown:

You need to use certain heuristics to step through the tree and optimize.

General Summary of the algorithm to achieve this:

Summary of Heuristics for Algebraic Optimization:
- The main heuristic is to apply first the operations that reduce the
size of intermediate results.
- Perform select operations as early as possible to reduce the
number of tuples and perform project operations as early as
possible to reduce the number of attributes. (This is done by
moving select and project operations as far down the tree as
possible.)
- The select and join operations that are most restrictive should be
executed before other similar operations. (This is done by
reordering the leaf nodes of the tree among themselves and
adjusting the rest of the tree appropriately.)

No tags