private List < QueryAtomGroupImpl > findComponents ( QueryAtomGroupImpl group ) { List < QueryAtom > atoms = new LinkedList <> ( ) ; atoms . addAll ( group . getAtoms ( ) ) ; List < QueryAtomGroupImpl > components = new LinkedList <> ( ) ; // if we have no atoms at all we simply return the same query as a single component if ( atoms . isEmpty ( ) ) { components . add ( group ) ; return components ; } // find all atoms containing no variables // and build a component QueryAtomGroupImpl component = new QueryAtomGroupImpl ( ) ; for ( QueryAtom atom : atoms ) { boolean noVar = true ; for ( QueryArgument arg : atom . getArguments ( ) ) { if ( arg . isVar ( ) ) { noVar = false ; break ; } } if ( noVar ) { component . addAtom ( atom ) ; } } component . getAtoms ( ) . forEach ( atoms :: remove ) ; if ( ! component . isEmpty ( ) ) { components . add ( component ) ; } // find connected components UnionFind < QueryArgument > unionFind = new UnionFind <> ( ) ; for ( QueryAtom atom : atoms ) { QueryArgument firstVar = null ; for ( QueryArgument arg : atom . getArguments ( ) ) { if ( arg . isVar ( ) ) { if ( firstVar == null ) { firstVar = arg ; } else { unionFind . union ( firstVar , arg ) ; } } } } while ( ! atoms . isEmpty ( ) ) { component = new QueryAtomGroupImpl ( ) ; QueryAtom nextAtom = atoms . get ( 0 ) ; atoms . remove ( nextAtom ) ; component . addAtom ( nextAtom ) ; QueryArgument args = null ; for ( QueryArgument arg : nextAtom . getArguments ( ) ) { if ( arg . isVar ( ) ) { args = unionFind . find ( arg ) ; break ; } } for ( QueryAtom atom : atoms ) { QueryArgument args2 = null ; for ( QueryArgument arg : atom . getArguments ( ) ) { if ( arg . isVar ( ) ) { args2 = unionFind . find ( arg ) ; break ; } } if ( args . equals ( args2 ) ) { component . addAtom ( atom ) ; } } for ( QueryAtom atom : component . getAtoms ( ) ) { atoms . remove ( atom ) ; } components . add ( component ) ; } return components ; }
Split the query into individual components if possible to avoid cross - products in later evaluation . The first component will contain all atoms with no variables if there exist some .