BNF of
the input conjunctive query text file
We designed and implemented
an algorithm optkdecomp for computing
optimal hypertree decompositions of conjunctive
queries (or CSP instances). Formally, given a query Q and a bound k>0,
optkdecomp computes a hypertree decomposition of width k' for Q, if
the hypertree width of Q is k' and k'
<= k; otherwise (i.e., if the width of Q is not bounded by k),
it returns failure.
optkdecomp has been implemented in C++. Note
that the project is flexible enough to be easily modified for searching for decompositions
that are optimal with respect to various preference criteria. For instance, we
are currently extending our algorithm in order to take into account also
quantitative information on the data, if available.
optkdecomp
optkdecomp can be executed from the command
line and its mandatory parameters are the bound k on the decompositions
we are interested in, and a text file containing input query with the following
syntax:
|
BNF of
the input conjunctive query text file |
|
The output of optkdecomp is a description of the outcome of
the search process and an output file containing the hypertree
decomposition computed by the algorithm (if any). This decomposition is in GML
(Graph Modeling Language), so that it can be easily
visualized and possibly modified by using any graph-drawing and management tool
that supports this standard, e.g., VGJ (that you can download below).
REQUIREMENTS
Win32 (Windows 9x,
Windows ME, Windows NT, Windows 2000)
Java 2 (for executing VGJ)
CPU and memory requirements depend on the input query size, the bound k,
and your patience.
SETUP
Unzip okdwin32.zip,
(preserving the structure of directories) into a new directory, say okdwin32
STARTING WITH optkdecomp
|
1. |
Open a dos window and go to the
directory okdwin32 (if you chose this name) |
|
2. |
Execute optkdecomp
without parameters for obtaining the usage syntax and the full list of
optional parameters |
|
3. |
Practice with optkdecomp
following the examples described in the Section Examples |
|
4. |
Execute vis
[OUTPUTFILE] to start VGJ and visualize hypertree decompositions |
RELEVANT OPTIONS
Choice of the desired representation for the
computed hypertree decomposition:
|
standard
(each vertex
contains a set of variables and a set of atoms, representing its labels) |
(default) |
|
|
non-verbose (similar to standard, but atoms'
arguments are not shown) |
-nv |
|
|
atom representation (each vertex is labeled just by a set of atoms: arguments corresponding
to variables not included in the (variable) label are replaced by
'_' |
-ar |
You can force the algorithm
to compute just complete hypertree decompositions:
|
any decomposition |
(default) |
|
|
a complete decomposition |
-cd |
The directory Query
contains some queries for testing optkdecomp.
Please, find below some examples of calls to optkdecomp.
Example 1
[Query hdq5: 9 atoms and 12 variables]
execute: optkdecomp 2 Query\hdq5.txt -of
test.gml
execute: vis test.gml
Example 2
execute: optkdecomp 4 Query\hdq5.txt -nv -of test.gml
execute: vis test.gml
Example 3
execute: optkdecomp 2 Query\hdq5.txt -nv -cd
-of test.gml
execute: vis test.gml
Example 4
execute: optkdecomp 3 Query\hdq5.txt -ar -cd
execute: vis
Example 5
execute: optkdecomp 1 Query\hdq5.txt
-cd
Example 6
[Query v13: 63 atoms and 136 variables]
execute: optkdecomp 2 Query\v13.txt -nv -cd
execute: vis
The zipped file okdwin32.zip contains
|
optkdecomp.exe |
executable for the Win32 platform console |
|
|
directory Query |
example queries |
|
|
directory VGJ |
||
|
vis.bat |
batch file to execute VGJ on the default
output-file of optkdecomp |
