edu.buffalo.nsf.xmlcqa.data.dtd
Class DTD

java.lang.Object
  extended byedu.buffalo.nsf.xmlcqa.data.dtd.DTD

public class DTD
extends java.lang.Object

A class representing Document Type Definition. DTD expresses the structure of an XML documents using regular expression. For every a tag the method getDefinition(Tag tag) returns the regular expression which the labels of children of the given tag should conform to. The init() method is used to initialize memoization in every regular expression that is stored by the object of this class. The method getMinTreeSize(Tag tag) returns the size of a minimal XML document whose root is labeled with tag. The values returned by this method are computed once, during creation of the object, and then stored in an array. This array can be accessed by method getMST(). It is assumed that when using this array, its values will not be changed. Any violation of this contract may result in an undefined behaviour. The method getMT(TreeNode parent, Tag tag, Query path, OperationManager mgr) returns the set of tree facts rooted at syntetic child of parent w.r.t. the query path that are present in every minimal tree conforming the DTD, which root is labeled with tag. For efficiency resons, we memoize the result of previous calls of this method. The freshness of the memoized values is established by pointer-wise comparing of the attributes path and mgr.

Author:
staworko

Nested Class Summary
static class DTD.DTDCycleDetected
          A standard class indicating improper DTD definition.
 
Field Summary
protected  java.util.List defs
           
protected  boolean[] memoized
           
protected  OperationManager mgr
           
protected  int[] mst
           
protected  NodeCollector[] mt
           
protected  Query path
           
 
Constructor Summary
DTD(java.util.Map defsMap)
          Standard constructor.
 
Method Summary
protected  int[] findMST()
           
protected  int findMST(NDFA e, int[] res, boolean[] visited, boolean[] found)
           
 NDFA getDefinition(Tag tag)
          Returs specification of children lables of a node labeled with tag.
 int getMinTreeSize(Tag tag)
          Return the size of a minimal tree satisfing the DTD whose root node is labeled with tag.
 int[] getMST()
          Returs the whole array of values suplied by the method getMinTreeSize(Tag).
 NodeCollector getMT(TreeNode parent, Tag tag, Query path, OperationManager mgr)
          Computes a minimal set of tree facts w.r.t.
 DTD init()
          A method initializing the given object.
 java.lang.String toString()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

defs

protected java.util.List defs

memoized

protected boolean[] memoized

mgr

protected OperationManager mgr

mst

protected int[] mst

mt

protected NodeCollector[] mt

path

protected Query path
Constructor Detail

DTD

public DTD(java.util.Map defsMap)
Standard constructor. The parameter defsMap is expected to map tags to regular expressions. By definition the label assigned to Tag.PCDATA_TAG is equal to NDFA.EPSILON. During the construction of DTD the sizes of minimal trees are being computed for every tag and stored for further usage.

Method Detail

findMST

protected int[] findMST()

findMST

protected int findMST(NDFA e,
                      int[] res,
                      boolean[] visited,
                      boolean[] found)

getDefinition

public NDFA getDefinition(Tag tag)
Returs specification of children lables of a node labeled with tag.


getMinTreeSize

public int getMinTreeSize(Tag tag)
Return the size of a minimal tree satisfing the DTD whose root node is labeled with tag.


getMST

public int[] getMST()
Returs the whole array of values suplied by the method getMinTreeSize(Tag). The returned array is an internal array storing all the values. It should not be modified.


getMT

public NodeCollector getMT(TreeNode parent,
                           Tag tag,
                           Query path,
                           OperationManager mgr)
Computes a minimal set of tree facts w.r.t. path, for trees whose root is labeled with tag rooted at a synthetic child of parent. The NodeCollector instance is created using supplied OperationManager.


init

public DTD init()
A method initializing the given object. This method forces all the preprocessing associated with construction of transition tables for the regluar expressions. No execution of this method is necessary for a proper functioning of DTD. However, this method allows to separate the cost of DTD preprocesing from other time costs of the system.


toString

public java.lang.String toString()