[pagoda] Move project to Scala

This commit includes a few changes:
- The repository still uses Maven to manage dependency but it is now a
  Scala project.
- The code has been ported from OWLAPI 3.4.10 to 5.1.20
- A proof of concept program using both RSAComb and PAGOdA has been
  added.

8 files changed, 734 insertions, 0 deletions

diff --git a/src/main/java/uk/ac/ox/cs/pagoda/constraints/BottomStrategy.java b/src/main/java/uk/ac/ox/cs/pagoda/constraints/BottomStrategy.java
new file mode 100644
index 0000000..4d25593
--- /dev/null
+++ b/src/main/java/uk/ac/ox/cs/pagoda/constraints/BottomStrategy.java
@@ -0,0 +1,19 @@
+package uk.ac.ox.cs.pagoda.constraints;
+
+import java.util.Collection;
+
+import org.semanticweb.HermiT.model.Atom;
+import org.semanticweb.HermiT.model.DLClause;
+import org.semanticweb.HermiT.model.Term;
+
+public interface BottomStrategy {
+
+        public Collection<DLClause> process(Collection<DLClause> clauses);
+        
+        public boolean isBottomRule(DLClause clause);
+        
+        public Atom[] getEmptyHead(Term t);
+
+        public int getBottomNumber(); 
+
+}
diff --git a/src/main/java/uk/ac/ox/cs/pagoda/constraints/DependencyGraph.java b/src/main/java/uk/ac/ox/cs/pagoda/constraints/DependencyGraph.java
new file mode 100644
index 0000000..d1615c7
--- /dev/null
+++ b/src/main/java/uk/ac/ox/cs/pagoda/constraints/DependencyGraph.java
@@ -0,0 +1,119 @@
+package uk.ac.ox.cs.pagoda.constraints;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.Map;
+import java.util.Queue;
+import java.util.Set;
+
+public abstract class DependencyGraph<T> {
+        
+        protected abstract void build(); 
+
+        protected Map<T, Set<T>> edges = new HashMap<T, Set<T>>();
+        protected Map<T, Set<T>> reverseEdges = new HashMap<T, Set<T>>(); 
+        
+        public void addLink(T subEntity, T superEntity) {
+                Set<T> dests = edges.get(subEntity);
+                if (dests == null)  
+                        edges.put(subEntity, dests = new HashSet<T>());
+                dests.add(superEntity);
+                
+                Set<T> srcs = reverseEdges.get(superEntity); 
+                if (srcs == null) 
+                        reverseEdges.put(superEntity, srcs = new HashSet<T>()); 
+                srcs.add(subEntity); 
+        }
+        
+        public void output() {
+                for (Map.Entry<T, Set<T>> pair: edges.entrySet()) {
+                        T src = pair.getKey(); 
+                        for (T dest: pair.getValue())
+                                System.out.println(src + " -> " + dest); 
+                }
+        }
+        
+        public int distance(Set<T> dsts, T src) {
+                Set<T> visited = new HashSet<T>(); 
+                if (dsts.contains(src)) return 0; 
+                visited.add(src); 
+                return distance(dsts, visited); 
+        }
+        
+        public int distance(Set<T> dsts, T src1, T src2) {
+                Set<T> visited = new HashSet<T>(); 
+                if (dsts.contains(src1)) return 0; 
+                if (dsts.contains(src2)) return 0; 
+                visited.add(src1); 
+                visited.add(src2); 
+                return distance(dsts, visited); 
+        }
+        
+        private int distance(Set<T> dsts, Set<T> visited) {
+                Queue<Entry> queue = new LinkedList<Entry>();
+                for (T src: visited)
+                        queue.add(new Entry(src, 0, visited));
+
+                Entry entry;
+                Set<T> edge; 
+                while (!queue.isEmpty()) {
+                        entry = queue.poll(); 
+                        edge = edges.get(entry.m_entity); 
+                        if (edge != null)
+                                for (T next: edge) {
+                                        if (dsts.contains(next)) return entry.m_dist + 1;
+                                        
+                                        if (!visited.contains(next)) 
+                                                queue.add(new Entry(next, entry.m_dist + 1, visited));
+                                }
+                }
+
+                return Integer.MAX_VALUE;
+        }
+        
+        public Set<T> getAncesters(T p) {
+                return getDependency(p, false); 
+        }
+        
+        public Set<T> getSuccessors(T p) {
+                return getDependency(p, true); 
+        }
+        
+        private Set<T> getDependency(T p, boolean succ) {
+                return succ ? getDependency(p, edges) : getDependency(p, reverseEdges); 
+        }
+        
+        private Set<T> getDependency(T p, Map<T, Set<T>> graph) {
+                Set<T> visited = new HashSet<T>(); 
+                Queue<T> queue = new LinkedList<T>();
+                visited.add(p);
+                queue.add(p);
+                Set<T> edge;
+                
+                while (!queue.isEmpty()) {
+                        if ((edge = graph.get(queue.poll())) != null)
+                                for (T next: edge) 
+                                        if (!visited.contains(next)) {
+                                                queue.add(next); 
+                                                visited.add(next); 
+                                        }
+                }
+                
+                return visited; 
+        }
+        
+        private class Entry {
+                
+                T m_entity; 
+                int m_dist; 
+                
+                public Entry(T entity, int distance, Set<T> v) {
+                        m_entity = entity; 
+                        m_dist = distance; 
+                        v.add(entity); 
+                }
+                
+        }
+        
+}
diff --git a/src/main/java/uk/ac/ox/cs/pagoda/constraints/NullaryBottom.java b/src/main/java/uk/ac/ox/cs/pagoda/constraints/NullaryBottom.java
new file mode 100644
index 0000000..16a9d45
--- /dev/null
+++ b/src/main/java/uk/ac/ox/cs/pagoda/constraints/NullaryBottom.java
@@ -0,0 +1,31 @@
+package uk.ac.ox.cs.pagoda.constraints;
+
+import java.util.Collection;
+
+import org.semanticweb.HermiT.model.Atom;
+import org.semanticweb.HermiT.model.DLClause;
+import org.semanticweb.HermiT.model.Term;
+
+public class NullaryBottom implements BottomStrategy {
+        
+        @Override
+        public Collection<DLClause> process(Collection<DLClause> clauses) {
+                return clauses;
+        }
+
+        @Override
+        public boolean isBottomRule(DLClause clause) {
+                return clause.getHeadLength() == 0;
+        }
+
+        @Override
+        public Atom[] getEmptyHead(Term t) {
+                return new Atom[0];
+        }
+
+        @Override
+        public int getBottomNumber() {
+                return 1;
+        }
+
+}
diff --git a/src/main/java/uk/ac/ox/cs/pagoda/constraints/OWLEntityDependency.java b/src/main/java/uk/ac/ox/cs/pagoda/constraints/OWLEntityDependency.java
new file mode 100644
index 0000000..60fea28
--- /dev/null
+++ b/src/main/java/uk/ac/ox/cs/pagoda/constraints/OWLEntityDependency.java
@@ -0,0 +1,195 @@
+package uk.ac.ox.cs.pagoda.constraints;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+
+import org.semanticweb.owlapi.model.OWLAnnotationAssertionAxiom;
+import org.semanticweb.owlapi.model.OWLAxiom;
+import org.semanticweb.owlapi.model.OWLClass;
+import org.semanticweb.owlapi.model.OWLClassAssertionAxiom;
+import org.semanticweb.owlapi.model.OWLClassExpression;
+import org.semanticweb.owlapi.model.OWLDataPropertyDomainAxiom;
+import org.semanticweb.owlapi.model.OWLDataPropertyRangeAxiom;
+import org.semanticweb.owlapi.model.OWLDeclarationAxiom;
+import org.semanticweb.owlapi.model.OWLDisjointClassesAxiom;
+import org.semanticweb.owlapi.model.OWLEquivalentClassesAxiom;
+import org.semanticweb.owlapi.model.OWLEquivalentObjectPropertiesAxiom;
+import org.semanticweb.owlapi.model.OWLFunctionalObjectPropertyAxiom;
+import org.semanticweb.owlapi.model.OWLInverseFunctionalObjectPropertyAxiom;
+import org.semanticweb.owlapi.model.OWLInverseObjectPropertiesAxiom;
+import org.semanticweb.owlapi.model.OWLLogicalEntity;
+import org.semanticweb.owlapi.model.OWLObject;
+import org.semanticweb.owlapi.model.OWLObjectProperty;
+import org.semanticweb.owlapi.model.OWLObjectPropertyAssertionAxiom;
+import org.semanticweb.owlapi.model.OWLObjectPropertyDomainAxiom;
+import org.semanticweb.owlapi.model.OWLObjectPropertyExpression;
+import org.semanticweb.owlapi.model.OWLObjectPropertyRangeAxiom;
+import org.semanticweb.owlapi.model.OWLOntology;
+import org.semanticweb.owlapi.model.OWLSubClassOfAxiom;
+import org.semanticweb.owlapi.model.OWLSubObjectPropertyOfAxiom;
+import org.semanticweb.owlapi.model.OWLSymmetricObjectPropertyAxiom;
+import org.semanticweb.owlapi.model.OWLTransitiveObjectPropertyAxiom;
+
+import uk.ac.ox.cs.pagoda.MyPrefixes;
+import uk.ac.ox.cs.pagoda.owl.OWLHelper;
+import uk.ac.ox.cs.pagoda.util.Utility;
+
+public class OWLEntityDependency extends DependencyGraph<OWLLogicalEntity> {
+        
+        OWLOntology m_ontology;
+        OWLClass m_nothing;
+        Map<String, OWLLogicalEntity> map = new HashMap<String, OWLLogicalEntity>(); 
+
+        public OWLEntityDependency(OWLOntology ontology) {
+                m_ontology = ontology;
+                m_nothing = ontology.getOWLOntologyManager().getOWLDataFactory().getOWLNothing(); 
+                build(); 
+        }
+
+        @Override
+        protected void build() {
+                for (OWLOntology o: m_ontology.getImportsClosure())
+                        for (OWLAxiom a: o.getAxioms()) 
+                                if (a instanceof OWLDisjointClassesAxiom)
+                                        addLinks((OWLDisjointClassesAxiom) a);
+                                else if (a instanceof OWLSymmetricObjectPropertyAxiom)
+                                        addLinks((OWLSymmetricObjectPropertyAxiom) a); 
+                                else if (a instanceof OWLFunctionalObjectPropertyAxiom)
+                                        ;               
+                                else if (a instanceof OWLInverseFunctionalObjectPropertyAxiom)
+                                        ;
+                                else if (a instanceof OWLTransitiveObjectPropertyAxiom)
+                                        addLinkes((OWLTransitiveObjectPropertyAxiom) a); 
+                                else if (a instanceof OWLInverseObjectPropertiesAxiom)
+                                        addLinks((OWLInverseObjectPropertiesAxiom) a); 
+                                else if (a instanceof OWLSubClassOfAxiom) 
+                                        addLinks((OWLSubClassOfAxiom) a); 
+                                else if (a instanceof OWLSubObjectPropertyOfAxiom)
+                                        addLinks((OWLSubObjectPropertyOfAxiom) a); 
+                                else if (a instanceof OWLEquivalentClassesAxiom) 
+                                        addLinks((OWLEquivalentClassesAxiom) a); 
+                                else if (a instanceof OWLEquivalentObjectPropertiesAxiom) 
+                                        addLinks((OWLEquivalentObjectPropertiesAxiom) a); 
+                                else if (a instanceof OWLObjectPropertyDomainAxiom) 
+                                        addLinks((OWLObjectPropertyDomainAxiom) a); 
+                                else if (a instanceof OWLObjectPropertyRangeAxiom)
+                                        addLinks((OWLObjectPropertyRangeAxiom) a);
+                                else if (a instanceof OWLDataPropertyDomainAxiom) 
+                                        addLinks((OWLDataPropertyDomainAxiom) a); 
+                                else if (a instanceof OWLDataPropertyRangeAxiom)
+                                        addLinks((OWLDataPropertyRangeAxiom) a);
+                                else if (a instanceof OWLDeclarationAxiom)
+                                        ;               
+                                else if (a instanceof OWLAnnotationAssertionAxiom)
+                                        ;
+                                else if (a instanceof OWLClassAssertionAxiom)
+                                        ;
+                                else if (a instanceof OWLObjectPropertyAssertionAxiom) 
+                                        ;
+                                else {
+                                        Utility.logError("Unknowledge OWL Axiom: " + a.getClass().getName() + "\n" + a); 
+                                }
+//              Utility.LOGS.info("DONE\n----------------------------"); 
+        }
+        
+        private void addLinks(OWLDisjointClassesAxiom a) {
+                for (OWLClassExpression exp: a.getClassExpressions())
+                        addLinks(exp, m_nothing); 
+        }
+
+        private void addLinks(OWLSymmetricObjectPropertyAxiom a) {
+                // TODO Auto-generated method stub
+                
+        }
+
+        private void addLinks(OWLInverseObjectPropertiesAxiom a) {
+                // TODO Auto-generated method stub
+                
+        }
+
+        private void addLinks(OWLDataPropertyRangeAxiom a) {
+                addLinks(a.getProperty(), a.getRange());                
+        }
+
+        private void addLinks(OWLDataPropertyDomainAxiom a) {
+                addLinks(a.getProperty(), a.getDomain()); 
+        }
+
+        private void addLinks(OWLEquivalentObjectPropertiesAxiom a) {
+                for (OWLObjectPropertyExpression exp1: a.getProperties())
+                        for (OWLObjectPropertyExpression exp2: a.getProperties())
+                                if(!exp1.equals(exp2))
+                                        addLinks(exp1, exp2); 
+        }
+
+        private void addLinkes(OWLTransitiveObjectPropertyAxiom a) {
+                addLinks(a.getProperty(), a.getProperty());             
+        }
+
+        private void addLinks(OWLObjectPropertyRangeAxiom a) {
+                addLinks(a.getProperty(), a.getRange());
+        }
+
+        private void addLinks(OWLObjectPropertyDomainAxiom a) {
+                addLinks(a.getProperty(), a.getDomain()); 
+                
+        }
+
+        private void addLinks(OWLEquivalentClassesAxiom a) {
+                for (OWLClassExpression exp1: a.getClassExpressions())
+                        for (OWLClassExpression exp2: a.getClassExpressions())
+                                if (!exp1.equals(exp2))
+                                        addLinks(exp1, exp2); 
+        }
+
+        private void addLinks(OWLSubObjectPropertyOfAxiom a) {
+                addLinks(a.getSubProperty(), a.getSuperProperty()); 
+        }
+
+        private void addLinks(OWLSubClassOfAxiom a) {
+                addLinks(a.getSubClass(), a.getSuperClass());
+                
+        }
+        
+        private void addLinks(OWLObject body, OWLObject head) {
+                Set<OWLLogicalEntity> bodyEntities = new HashSet<OWLLogicalEntity>();  
+                Set<OWLLogicalEntity> headEntities = new HashSet<OWLLogicalEntity>();
+                for (OWLClass c: body.getClassesInSignature()) {
+                        bodyEntities.add(c);
+                        map.put(c.toStringID(), c); 
+                }
+                for (OWLObjectProperty p: body.getObjectPropertiesInSignature()) {
+                        bodyEntities.add(p); 
+                        map.put(p.toStringID(), p); 
+                }
+                
+                for (OWLClass c: head.getClassesInSignature()) { 
+                        headEntities.add(c); 
+                        map.put(c.toStringID(), c); 
+                }
+                for (OWLObjectProperty p: head.getObjectPropertiesInSignature()) { 
+                        headEntities.add(p);
+                        map.put(p.toString(), p); 
+                }
+                
+                for (OWLLogicalEntity subEntity: bodyEntities)
+                        for (OWLLogicalEntity superEntity: headEntities)
+                                addLink(subEntity, superEntity); 
+        }
+
+        public OWLLogicalEntity getLogicalEntity(String iri) {
+                iri = MyPrefixes.PAGOdAPrefixes.expandIRI(iri); 
+                return map.get(iri);  
+        }
+        
+        public static void main(String[] args) {
+                args = ("/users/yzhou/ontologies/uobm/univ-bench-dl.owl").split("\\ ");
+                
+                OWLOntology onto = OWLHelper.loadOntology(args[0]); 
+                OWLEntityDependency dependency = new OWLEntityDependency(onto); 
+                dependency.output(); 
+        }
+        
+}
diff --git a/src/main/java/uk/ac/ox/cs/pagoda/constraints/PredicateDependency.java b/src/main/java/uk/ac/ox/cs/pagoda/constraints/PredicateDependency.java
new file mode 100644
index 0000000..70f841f
--- /dev/null
+++ b/src/main/java/uk/ac/ox/cs/pagoda/constraints/PredicateDependency.java
@@ -0,0 +1,215 @@
+package uk.ac.ox.cs.pagoda.constraints;
+
+import org.semanticweb.HermiT.model.*;
+import uk.ac.ox.cs.pagoda.rules.approximators.OverApproxExist;
+import uk.ac.ox.cs.pagoda.util.Namespace;
+import uk.ac.ox.cs.pagoda.util.Utility;
+
+import java.util.*;
+
+
+public class PredicateDependency extends DependencyGraph<DLPredicate> {
+
+        private static final DLPredicate equality = AtomicRole.create(Namespace.EQUALITY);
+        private static final DLPredicate inequality = AtomicRole.create(Namespace.INEQUALITY);
+        Collection<DLClause> m_clauses;
+        Map<PredicatePair, LinkedList<DLClause>> edgeLabels = new HashMap<PredicatePair, LinkedList<DLClause>>();
+        Set<DLPredicate> reachableToBottom = null;
+
+        public PredicateDependency(Collection<DLClause> clauses) {
+                m_clauses = clauses;
+                build();
+        }
+
+        @Override
+        protected void build() {
+                update(m_clauses);
+
+                addLink(equality, AtomicConcept.NOTHING);
+                addLink(inequality, AtomicConcept.NOTHING);
+        }
+
+        private void addEdgeLabel(DLPredicate body, DLPredicate head, DLClause clause) {
+                PredicatePair key = new PredicatePair(body, head);
+                LinkedList<DLClause> value;
+                if ((value = edgeLabels.get(key)) == null)
+                        edgeLabels.put(key, value = new LinkedList<DLClause>());
+                value.add(clause);
+        }
+
+        private void addLinks4Negation(AtomicConcept c, DLClause clause) {
+                addLink(c, AtomicConcept.NOTHING);
+                addEdgeLabel(c, AtomicConcept.NOTHING, clause);
+                String iri = c.getIRI();
+                addLink(c = AtomicConcept.create(iri.substring(0, iri.length() - 4)), AtomicConcept.NOTHING);
+                addEdgeLabel(c, AtomicConcept.NOTHING, clause);
+        }
+
+        public Set<DLPredicate> collectPredicate(Atom[] atoms) {
+                Set<DLPredicate> predicates = new HashSet<DLPredicate>();
+                for (Atom atom : atoms)
+                        predicates.addAll(getAtomicPredicates(atom.getDLPredicate()));
+                return predicates;
+        }
+        
+        private Set<DLPredicate> getAtomicPredicates(DLPredicate predicate) {
+                Set<DLPredicate> predicates = new HashSet<DLPredicate>();
+                if (predicate instanceof AtLeastConcept)
+                        predicates.addAll(getAtomicPredicates((AtLeastConcept) predicate));
+                else {
+                        if ((predicate = getAtomicPredicate(predicate)) != null)
+                                predicates.add(predicate);
+                }
+                return predicates;
+        }
+        
+        private Set<DLPredicate> getAtomicPredicates(AtLeastConcept alc) {
+                Set<DLPredicate> set = new HashSet<DLPredicate>();
+                if (alc.getOnRole() instanceof AtomicRole)
+                        set.add((AtomicRole) alc.getOnRole());
+                else
+                        set.add(((InverseRole) alc.getOnRole()).getInverseOf());
+
+                if (alc.getToConcept() instanceof AtomicConcept)
+                        if (alc.getToConcept().equals(AtomicConcept.THING)) ;
+                        else set.add((AtomicConcept) alc.getToConcept());
+                else
+                        set.add(OverApproxExist.getNegationConcept(((AtomicNegationConcept) alc.getToConcept()).getNegatedAtomicConcept()));
+                return set;
+        }
+        
+        private DLPredicate getAtomicPredicate(DLPredicate p) {
+                if (p instanceof Equality || p instanceof AnnotatedEquality)
+                        return equality;
+                if (p instanceof Inequality)
+                        return inequality;
+                if (p instanceof AtomicConcept)
+                        if (p.equals(AtomicConcept.THING))
+                                return null;
+                        else return p;
+                if (p instanceof AtomicRole)
+                        return p;
+                if (p instanceof AtLeastDataRange) {
+                        AtLeastDataRange aldr = (AtLeastDataRange) p;
+                        if (aldr.getOnRole() instanceof AtomicRole)
+                                return (AtomicRole) aldr.getOnRole();
+                        else
+                                return ((InverseRole) aldr.getOnRole()).getInverseOf();
+                }
+                Utility.logDebug("Unknown DLPredicate in PredicateDependency: " + p);
+                return null;
+        }
+        
+        public Set<DLClause> pathTo(DLPredicate p) {
+                Set<DLClause> rules = new HashSet<DLClause>();
+                Set<DLPredicate> visited = new HashSet<DLPredicate>();
+
+                Queue<DLPredicate> queue = new LinkedList<DLPredicate>();
+                queue.add(p);
+                visited.add(p);
+
+                Set<DLPredicate> edge;
+                Collection<DLClause> clauses;
+
+                while (!queue.isEmpty()) {
+                        if ((edge = reverseEdges.get(p = queue.poll())) != null) {
+                                for (DLPredicate pred: edge) {
+                                        if (!visited.contains(pred)) {
+                                                queue.add(pred);
+                                                visited.add(pred);
+                                        }
+                                        clauses = edgeLabelsBetween(pred, p);
+                                        if (clauses != null) rules.addAll(clauses);
+                                }
+                        }
+                }
+                return rules;
+        }
+
+        private LinkedList<DLClause> edgeLabelsBetween(DLPredicate p, DLPredicate q) {
+                PredicatePair pair = new PredicatePair(p, q);
+                return edgeLabels.get(pair);
+        }
+        
+        public Set<DLClause> pathToBottom(DLPredicate p) {
+                if (reachableToBottom == null) {
+                        reachableToBottom = getAncesters(AtomicConcept.NOTHING); 
+                        reachableToBottom.add(AtomicConcept.NOTHING); 
+                }
+                
+                Set<DLClause> rules = new HashSet<DLClause>(); 
+                Set<DLPredicate> visited = new HashSet<DLPredicate>(); 
+                
+                Queue<DLPredicate> queue = new LinkedList<DLPredicate>(); 
+                queue.add(p); 
+                visited.add(p);
+                
+                Set<DLPredicate> edge; 
+                Collection<DLClause> clauses; 
+                
+                while (!queue.isEmpty()) {
+                        if ((edge = edges.get(p = queue.poll())) != null) {
+                                for (DLPredicate next: edge) 
+                                        if (reachableToBottom.contains(next)) {
+                                                if (!visited.contains(next)) {
+                                                        queue.add(next); 
+                                                        visited.add(next); 
+                                                }
+                                                clauses = edgeLabelsBetween(p, next);
+                                                if (clauses != null) rules.addAll(clauses); 
+                                        }
+                        }
+                }
+                return rules; 
+        }
+
+        public void update(Collection<DLClause> clauses) {
+                Set<DLPredicate> headPredicates, bodyPredicates; 
+                
+                for (DLClause clause: clauses) {
+                        headPredicates = collectPredicate(clause.getHeadAtoms());
+                        bodyPredicates = collectPredicate(clause.getBodyAtoms()); 
+
+                        for (DLPredicate body: bodyPredicates)
+                                for (DLPredicate head: headPredicates) {
+                                        addLink(body, head);
+                                        addEdgeLabel(body, head, clause); 
+                                        
+                                        if (body instanceof AtomicConcept && body.toString().contains("_neg")) 
+                                                addLinks4Negation((AtomicConcept) body, clause); 
+                                        if (head instanceof AtomicConcept && head.toString().contains("_neg")) 
+                                                addLinks4Negation((AtomicConcept) head, clause); 
+                                }
+                        
+                        for (DLPredicate body: bodyPredicates)
+                                addLink(equality, body);
+                        
+                        for (DLPredicate head: headPredicates)
+                                addLink(equality, head);
+                }               
+        }
+
+}
+
+class PredicatePair {
+        
+        DLPredicate p, q; 
+        
+        public PredicatePair(DLPredicate p, DLPredicate q) {
+                this.p = p; this.q = q; 
+        }
+        
+        public int hashCode() {
+                return p.hashCode() * 1997 + q.hashCode(); 
+        }
+        
+        public boolean equals(Object o) {
+                if (!(o instanceof PredicatePair)) return false; 
+                PredicatePair thatPair = (PredicatePair) o; 
+                return p.equals(thatPair.p) && q.equals(thatPair.q); 
+        }
+        
+        public String toString() {
+                return "<" + p.toString() + "," + q.toString() + ">"; 
+        }
+}
diff --git a/src/main/java/uk/ac/ox/cs/pagoda/constraints/ToBeRemovedBottom.java b/src/main/java/uk/ac/ox/cs/pagoda/constraints/ToBeRemovedBottom.java
new file mode 100644
index 0000000..415119a
--- /dev/null
+++ b/src/main/java/uk/ac/ox/cs/pagoda/constraints/ToBeRemovedBottom.java
@@ -0,0 +1,36 @@
+package uk.ac.ox.cs.pagoda.constraints;
+
+import java.util.Collection;
+import java.util.LinkedList;
+
+import org.semanticweb.HermiT.model.Atom;
+import org.semanticweb.HermiT.model.DLClause;
+import org.semanticweb.HermiT.model.Term;
+
+public class ToBeRemovedBottom implements BottomStrategy {
+
+        @Override
+        public Collection<DLClause> process(Collection<DLClause> clauses) {
+                Collection<DLClause> ret = new LinkedList<DLClause>(); 
+                for (DLClause clause: clauses)
+                        if (clause.getHeadLength() != 0)
+                                ret.add(clause); 
+                return ret;
+        }
+
+        @Override
+        public boolean isBottomRule(DLClause clause) {
+                return false;
+        }
+
+        @Override
+        public Atom[] getEmptyHead(Term t) {
+                return null;
+        }
+
+        @Override
+        public int getBottomNumber() {
+                return 0;
+        }
+
+}
diff --git a/src/main/java/uk/ac/ox/cs/pagoda/constraints/UnaryBottom.java b/src/main/java/uk/ac/ox/cs/pagoda/constraints/UnaryBottom.java
new file mode 100644
index 0000000..5339c50
--- /dev/null
+++ b/src/main/java/uk/ac/ox/cs/pagoda/constraints/UnaryBottom.java
@@ -0,0 +1,67 @@
+package uk.ac.ox.cs.pagoda.constraints;
+
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.Set;
+
+import org.semanticweb.HermiT.model.Atom;
+import org.semanticweb.HermiT.model.AtomicConcept;
+import org.semanticweb.HermiT.model.DLClause;
+import org.semanticweb.HermiT.model.Individual;
+import org.semanticweb.HermiT.model.Term;
+import org.semanticweb.HermiT.model.Variable;
+
+public class UnaryBottom implements BottomStrategy {
+        
+        @Override
+        public Collection<DLClause> process(Collection<DLClause> clauses) {
+                Collection<DLClause> ret = new LinkedList<DLClause>(); 
+                for (DLClause clause: clauses) 
+                        if (clause.getHeadLength() == 0) {
+                                ret.add(DLClause.create(getEmptyHead(pickRepresentative(clause.getBodyAtoms())), clause.getBodyAtoms()));
+                        }
+                        else 
+                                ret.add(clause); 
+                return ret;
+        }
+
+        protected Term pickRepresentative(Atom[] atoms) {
+                Term rep = null; 
+                Set<Variable> vars = new HashSet<Variable>(); 
+                for (Atom atom: atoms) {
+                        atom.getVariables(vars);
+                        for (Variable v: vars)
+                                if (rep == null || ((Variable) rep).getName().compareTo(v.getName()) > 0)
+                                        rep = v;
+                        vars.clear(); 
+                }
+                if (rep != null) return rep; 
+                
+                Set<Individual> inds = new HashSet<Individual>(); 
+                for (Atom atom: atoms) {
+                        atom.getIndividuals(inds);
+                        for (Individual i: inds)
+                                if (rep == null || ((Individual) rep).getIRI().compareTo(i.getIRI()) > 0)
+                                        rep = i;
+                        inds.clear();
+                }
+                
+                return rep;
+        }
+
+        @Override
+        public boolean isBottomRule(DLClause clause) {
+                return clause.getHeadLength() == 1 && clause.getHeadAtom(0).getDLPredicate().equals(AtomicConcept.NOTHING);
+        }
+
+        public Atom[] getEmptyHead(Term t) {
+                return new Atom[] {Atom.create(AtomicConcept.NOTHING, t)};
+        }
+
+        @Override
+        public int getBottomNumber() {
+                return 1;
+        }
+
+}
diff --git a/src/main/java/uk/ac/ox/cs/pagoda/constraints/UpperUnaryBottom.java b/src/main/java/uk/ac/ox/cs/pagoda/constraints/UpperUnaryBottom.java
new file mode 100644
index 0000000..2b57a52
--- /dev/null
+++ b/src/main/java/uk/ac/ox/cs/pagoda/constraints/UpperUnaryBottom.java
@@ -0,0 +1,52 @@
+package uk.ac.ox.cs.pagoda.constraints;
+
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.LinkedList;
+import java.util.Map;
+
+import org.semanticweb.HermiT.model.Atom;
+import org.semanticweb.HermiT.model.AtomicConcept;
+import org.semanticweb.HermiT.model.DLClause;
+import org.semanticweb.HermiT.model.Term;
+import org.semanticweb.HermiT.model.Variable;
+
+public class UpperUnaryBottom extends UnaryBottom {
+        
+        static final Variable X = Variable.create("X"); 
+        
+        Map<DLClause, Integer> number = new HashMap<DLClause, Integer>(); 
+        
+        @Override
+        public Collection<DLClause> process(Collection<DLClause> clauses) {
+                Collection<DLClause> ret = new LinkedList<DLClause>(); 
+                for (DLClause clause: clauses) 
+                        if (clause.getHeadLength() == 0) {
+                                ret.add(DLClause.create(getEmptyHead(pickRepresentative(clause.getBodyAtoms()), clause), clause.getBodyAtoms())); 
+                                ret.add(DLClause.create(getEmptyHead(X), getEmptyHead(X, clause))); 
+                        }
+                        else 
+                                ret.add(clause); 
+                return ret;
+        }
+
+        @Override
+        public boolean isBottomRule(DLClause clause) {
+                return clause.getHeadLength() == 1 && clause.getHeadAtom(0).getDLPredicate().toString().contains(AtomicConcept.NOTHING.toString());
+        }
+
+        public Atom[] getEmptyHead(Term t, DLClause clause) {
+                Integer index = number.get(clause); 
+                if (index == null) {
+                        number.put(clause, index = number.size() + 1); 
+                }
+                
+                return new Atom[] {Atom.create(AtomicConcept.create(AtomicConcept.NOTHING.getIRI() + index), t)};
+        }
+        
+        @Override
+        public int getBottomNumber() {
+                return number.size() + 1; 
+        }
+
+}