queryutil.java

数字图书馆的互操作接口

package dli2fe.helpers;

/**
 * Title:        Digial Library Interoperable Interface Fudan Edition
 * Description:  This project contains all the classes required for DLI2FE interface. Developers use these classes to implement the wrapper and client side codes. The basic functions of DLI2FE is as follows:
 * Search: Search a digital library source site.
 * Metadata: Fetch metadata for a site.
 * ResultAccess: Get results for a given query.
 * DLI2FE uses Dublin Core as the basic attribute model, DAV/DASL as the general XML-based query language and CORBA as distributed object transportation mechanism.
 * Copyright:    Copyright (c) 2001
 * Company:      Fudan University
 * @author Carl Tao
 * @version 1.0
 */

import dli2fe.xml.*;
import org.w3c.dom.*;
import org.omg.CORBA.IntHolder;
import dli2fe.DAV;

/**
 * This class provides functions to
 * manipulate boolean queries in DAV/DASL format.
 */

public class QueryUtil {

  /** tests whether elements is an AND operator */
  public static boolean isAND(Element q) {
    return (q.getNamespaceURI() == null || DAV.Namespace.equals(q.getNamespaceURI())) && DAV.and.equals(q.getTagName());
  }
  /** tests whether elements is an OR operator */
  public static boolean isOR(Element q) {
    return (q.getNamespaceURI() == null || DAV.Namespace.equals(q.getNamespaceURI())) && DAV.or.equals(q.getTagName());
  }
  /** tests whether elements is an NOT operator */
  public static boolean isNOT(Element q) {
    return (q.getNamespaceURI() == null || DAV.Namespace.equals(q.getNamespaceURI())) && DAV.not.equals(q.getTagName());
  }
  /** tests whether elements is a boolean operator */
  public static boolean isBoolean(Element q) {
    return isAND(q) || isOR(q) || isNOT(q);
  }
  /** tests whether query evaluates to true */
  public static boolean isTrue(Element q) {
    return (q.getNamespaceURI() == null || DAV.Namespace.equals(q.getNamespaceURI())) && DAV.TRUE.equals(q.getTagName());
  }
  /** tests whether query evaluates to false */
  public static boolean isFalse(Element q) {
    return (q.getNamespaceURI() == null || DAV.Namespace.equals(q.getNamespaceURI())) && DAV.FALSE.equals(q.getTagName());
  }

  /**
   * Translates boolean query into disjunctive normal form
   */
  public static Element DNF(Element q) {

    //    long l = System.currentTimeMillis();
    q = flattenNOT(q, false);
    //    System.err.println("Flatten NOT:\n " + DOMWriter.prettyPrint(q));
    q = flattenORAND(q);
    //    System.err.println("Flatten OR, AND:\n " + DOMWriter.prettyPrint(q));
    IntHolder h = new IntHolder(1);
    while(h.value > 0) {
      h.value = 0;
      q = flattenORAND(distribute(q, h));
      //      System.err.println("Distributed: " + h.value);
    }
    q = simplify(q);
    //    System.err.println("--- DNF took " + (System.currentTimeMillis() - l) + " ms");
    return q;
  }

  /**
   * Translates boolean query into disjunctive normal form
   * whereas every path from root to leaf or negated leaf is or length 2.
   */
  public static Element canonicalDNF(Element q) {

    q = DNF(q);
    if(isTrue(q) || isFalse(q))
      return q;

    Element or = q.getOwnerDocument().createElementNS(DAV.Namespace, DAV.or);
    if(isAND(q)) {
      // AND(X,Y) -> OR(AND(X,Y))
      or.appendChild(q.cloneNode(true));
    } else if (isOR(q)) {
      // OR(X,AND(Y),Z) -> OR(AND(X),AND(Y),AND(Z))
      NodeList list = DOMUtil.getChildElements(q, "*");
      for(int i=0; i < list.getLength(); i++) {
	Element ch = (Element)list.item(i);
	if(isAND(ch))
	  or.appendChild( ch.cloneNode(true) );
	else {
	  Element and = q.getOwnerDocument().createElementNS(DAV.Namespace, DAV.and);
	  or.appendChild(and);
	  and.appendChild( ch.cloneNode(true) );
	}
      }
    } else {
      // X -> OR(AND(X))
      Element and = q.getOwnerDocument().createElementNS(DAV.Namespace, DAV.and);
      or.appendChild(and);
      and.appendChild( q.cloneNode(true) );
    }
    return or;
  }

  /**
   * Checks whether two elements are syntactically equivalent.
   * Assumption: there is no whitespace in XML tree,
   * guaranteed by using dli2fe.xml.dom.DOMParser (or XMLObject)
   */
  public static boolean equals(Node a, Node b) {

    if(a == b)
      return true;
    if(a == null || b == null || a.getNodeType() != b.getNodeType())
      return false;

    if(a.getNodeType() == Node.ELEMENT_NODE) {

      if (a.getNamespaceURI() != null && b.getNamespaceURI() != null
        && (!a.getNamespaceURI().equals(b.getNamespaceURI())))
        return false;
      if(!a.getLocalName().equals(b.getLocalName()))
	return false;
      Node chA = a.getFirstChild();
      Node chB = b.getFirstChild();
      while(true) {
	if(chA == chB)
	  return true; // only possible when both are null
	if(chA == null || chB == null)
	  return false; // one of them is non null
	if(!equals(chA, chB))
	  return false;
	chA = chA.getNextSibling();
	chB = chB.getNextSibling();
      }
    } else
      return a.getNodeValue().equals(b.getNodeValue());
  }

  /**
   * returns the single child of an element
   */
  public static Element inside(Element q) {
    return DOMUtil.getChild(q, "*");
  }

  static void flattenORAND(Element q, Element cont) {

    boolean andOr = isAND(q) || isOR(q);
    NodeList children = DOMUtil.getChildElements(q, "*");
    for(int i=0; i < children.getLength(); i++) {
      Element ch = (Element)children.item(i);
      if(andOr && ch.getTagName().equals(q.getTagName()))
	flattenORAND(ch, cont);
      else if(andOr) {
	Element dest = (Element)ch.cloneNode(false);
	cont.appendChild(dest);
	flattenORAND(ch, dest);
      } else
	cont.appendChild( ch.cloneNode(true) );
    }
  }

  static Element flattenORAND(Element q) {

    Element res = (Element)q.cloneNode(false);
    flattenORAND(q, res);
    return res;
  }

  /** moves NOT to the leaves, removes AND and OR when unary operators */
  static Element flattenNOT(Element q, boolean insideNOT) {

    //    System.err.println("FLATTEN: " + q.getTagName() + ", " + insideNOT);

    if(!isBoolean(q)) {
      if(!insideNOT)
	return (Element)q.cloneNode(true);
      else {
	Element not = q.getOwnerDocument().createElementNS(DAV.Namespace, DAV.not);
	not.appendChild(q.cloneNode(true));
	return not;
      }
    }
    if(isNOT(q))
      return flattenNOT(inside(q), !insideNOT);
    // q can be OR or AND only; if NOT ( AND ) -> cont=OR; if NOT ( OR ) -> cont=AND; else same
    String contTag = q.getTagName();
    if(insideNOT && isAND(q))
      contTag = DAV.or;
    if(insideNOT && isOR(q))
      contTag = DAV.and;
    Element cont = q.getOwnerDocument().createElementNS(DAV.Namespace, contTag);

    NodeList children = DOMUtil.getChildElements(q, "*");
    if(children.getLength() > 1) {
      for(int i=0; i < children.getLength(); i++) {
	Element ch = (Element)children.item(i);
	cont.appendChild( flattenNOT(ch, insideNOT) );
      }
    } else if(children.getLength() == 1)
      return flattenNOT( (Element)children.item(0), insideNOT );
    else
      throw new RuntimeException("Empty " + q.getTagName() + " operator.");
    return cont;
  }

  static Element simplify(Element q) {

    if(!(isOR(q) || isAND(q)))
      return (Element)q.cloneNode(true);

    Element q1 = (Element)q.cloneNode(false);
    NodeList children = DOMUtil.getChildElements(q, "*");
    for(int i=0; i < children.getLength(); i++) {
      Element ch = (Element)children.item(i);
      if(isAND(q) || isOR(q)) {
	Element s = simplify(ch);
	if(!isFalse(s) && !isTrue(s)) // OR -> true, AND -> false
	  q1.appendChild(s);
      }
    }
    // remove duplicates
    Element q2 = (Element)q.cloneNode(false);
    children = DOMUtil.getChildElements(q1, "*");
    for(int i=0; i < children.getLength(); i++) {
      Element ch = (Element)children.item(i);
      boolean found = false;
      NodeList resList = DOMUtil.getChildElements(q2, ch.getTagName());
      for(int j = 0; j < resList.getLength(); j++) {
	if(equals((Element)resList.item(j), ch)) {
	  found = true;
	  break;
	}
      }
      if(!found)
	q2.appendChild(ch);
    }
    // A op ~A?
    children = DOMUtil.getChildElements(q2, "*");
    for(int i=0; i < children.getLength(); i++) {
      for(int j = i+1; j < children.getLength(); j++) {
	Element chA = (Element)children.item(i);
	Element chB = (Element)children.item(j);
	if( ( DAV.not.equals(chA.getTagName()) && equals(inside(chA), chB) ) ||
	    ( DAV.not.equals(chB.getTagName()) && equals(inside(chB), chA) ) ) {
	  // contradiction
	  return q.getOwnerDocument().createElementNS(DAV.Namespace, isOR(q) ? DAV.TRUE : DAV.FALSE );
	}
      }
    }
    return q2;
  }

  static Element distribute(Element q, IntHolder h) {

    if(isAND(q)) {
      // contains OR?
      Element or = DOMUtil.getChild(q, DAV.or);
      if(or == null)
	return (Element)q.cloneNode(true);
      else {
	// group remaining nodes if necessary
	Element remainingAND = null;
	NodeList children = DOMUtil.getChildElements(q, "*");
	boolean multiAND = children.getLength() > 2;
	if(multiAND)
	  remainingAND = (Element)q.cloneNode(false); // and
	for(int i=0; i < children.getLength(); i++) {
	  Element ch = (Element)children.item(i);
	  if(ch != or)
	    if(multiAND)
	      remainingAND.appendChild( ch.cloneNode(true) );
	    else {
	      remainingAND = ch;
	      break;
	    }
	}
	// distribute
	Element topOR = (Element)or.cloneNode(false);
	NodeList children2 = DOMUtil.getChildElements(or, "*");
	for(int i=0; i < children2.getLength(); i++) {
	  Element ch = (Element)children2.item(i);
	  Element andInOR = (Element)q.cloneNode(false); // new AND
	  andInOR.appendChild(ch);
	  andInOR.appendChild(remainingAND.cloneNode(true));
	  topOR.appendChild(andInOR);
	}
	h.value++;
	return topOR;
      }
    } else if(isOR(q)) { // OR

      Element or = (Element)q.cloneNode(false);
      NodeList children = DOMUtil.getChildElements(q, "*");
      for(int i=0; i < children.getLength(); i++)
	or.appendChild( distribute( (Element)children.item(i), h ) );
      return or;

    } else { // other
      return (Element)q.cloneNode(true);
    }
  }

  public static void main(String args[]) throws Exception {

    XMLObject obj = new XMLObject("<basicsearch xmlns='DAV:' xmlns:dc='http://purl.org/metadata/dublin_core#'> <where> <eq> <prop><dc:Creator/></prop> <literal>larson</literal> </eq> </where> </basicsearch>");
    Element queryBody = obj.getElement();
    System.out.println("Query body is:\n" + obj.getString());
    Element eWhere = DOMUtil.getChild(queryBody, DAV.where);
    System.out.println("a"+eWhere.getNamespaceURI());
    eWhere = (Element)eWhere.cloneNode(true);
    System.out.println("a"+eWhere.getNamespaceURI());
    obj.setElement(QueryUtil.canonicalDNF(queryBody));
    System.out.println("Translated is:\n" + obj.getString());
  }
}