Mapping ORM to Datalog: An Overview <s> Mapping Derivation Rules <s> Formulating non-trivial queries in relational languages such as SQL and QBE can prove daunting to end users. ConQuer is a conceptual query language that allows users to formulate queries naturally in terms of elementary relationships. operators such as and, of', snot' and maybe contextual forclauses and object-correlation, thus avoiding the need to deal explicitly with implementation details such as relational tables, null values. outer joins, group-by clauses and correlated subqueries. While most conceptual query languages are based on the Entity-Relationship approach, ConQuer is based on Object-Role Modeling (ORM), which exposes semantic domains as conceptual object types. allowing queries to be formulated via paths through the information space. As a result of experience with the first implementation of ConQuer, the language has been substantially revised and extended to become ConQuer-II. and a new tool, ActiveQuery, has been developed with an improved interface. ConQuer-II's new features such as arbitrary correlation and subtyping enable it to be used for a wide range of advanced conceptual queries. <s> BIB001 </s> Mapping ORM to Datalog: An Overview <s> Mapping Derivation Rules <s> Several alternative semantics (or interpretations) of the relational (domain) calculus are studied here. It is shown that they all have the same expressive power, i.e., the selection of any of the semantics neither gains nor loses expressive power. <s> BIB002
The above acyclic constraint enforcement introduced a derived fact type under the covers. ORM users may also introduce derived fact types of their own, and have NORMA map these to Datalog LB . For implementation, we first capture the derivation rules in a role-calculus based structure, and then transform this to an intermediate, domain relational calculus structure, from which the Datalog LB code is generated. Derivation rules may be used to derive either subtypes or fact types. The NORMA screenshot in Figure 3 (a) includes two derived subtypes and one derived fact type. The derivation path for the subtype FastCarDriver starts with Person (the path root) and navigates via the drives predicate to Car and then onto the isFast predicate, performing a conceptual join on Car. NORMA generates the following verbalization for the derivation rule: *Each FastCarDriver is some Person who drives some Car that is fast. The role calculus form of the rule is translated to a named tree structure representing the following sorted, relational calculus formula {x:Person | ∃y:Car (x drives y & y is fast)}. This is then transformed to an equivalent version of the following Datalog LB rule, using standard techniques for reducing sorted to unsorted logic, and employing implicit quantification: FastCarDriver(x) <-Person(x), Car(y), person:car:drives(x, y), car:isFast(y). The derivation path for the NonDriver subtype starts with Person and then negates its entry into the drives predicate. This verbalizes as: *Each NonDriver is some Person who drives no Car. This maps to a named structure for the relational calculus formula {x:Person | ~∃y:Car x drives y}. For first-time users of datalog, the following rule may seem like an acceptable way to encode this rule: NonDriver(x) <-Person(x), !(Car(y), person:car:drives(x, y)). --error! However, the implicit existential quantification ∃y is before the negation rather than inside it, so the body is satisfied if x is a person, and there is anything that is not a car or is not driven by x. The range of y is unrestricted, so the rule is unsafe. In basic datalog, negands in the rule body are restricted to atoms, but in the above example the negand is a conjunction. Datalog LB allows negated conjunctions if the variables in the negand are range restricted outside the negation (which is not true of the y variable in the above example). One solution is to generate the code in two steps, first deriving the opposite predicate and then negating it as shown below. It can also be done in one rule simply as NonDriver(x) <-Person(x), !person:car:drives(x,_). Driver(x) <-Person(x), Car(y), person:car:drives(x, y). NonDriver(x) <-Person(x), !Driver(x). Figure 3 also includes the derived fact type in Person doesn't drive all cars. This is intended to return each person where there is at least one car not driven by that person. In this case, the derivation path starts with a car variable, and then uses negation to navigate to the person(s) who don't drive that car, and finally the derived role of Person is bound to that person variable. This verbalizes as: *Person doesn't drive all cars if and only if for some Car it is not true that that Person drives that Car. A key aspect of generating the relational calculus version of the rule is knowing where to place existential quantifiers. Unprojected root variables are existentially quantified. Hence the derivation rule currently being discussed leads to the following relational calculus formula: {x:Person | ∃y:Car ~x drives y}. ORM is essentially a sugared, visual version of sorted logic, hence in ORM each variable that is projected is a typed variable. The act of projecting on a typed variable in the scope of a negation ensures that the type declaration for that variable is lifted outside the negation. As a more general approach that works also with unsorted relational calculus, we introduce the following Existential Placement Rule (EP). For each variable ν that occurs only in the rule body, place ∃ν immediately before the minimal wff that contains all the ν occurrences. Hence, if ν occurs only inside a negation then place ∃ν immediately after the negation symbol. In contrast to our NORMA and VisualBlox implementation, the ActiveQuery tool BIB001 , although dealing well with many tasks, fails to provide correct semantics for this rule when formulated as a query. doesntDriveAllCars(x) <-Person(x), Car(y), !drives(x, y). Figure 4 shows an ORM schema with two derived fact types. The FORML derivation rules involve a multiply operator and a sum function (both are treated as functions in NORMA). An earlier paper discussed how to capture these two rules in the role calculus  . We now discuss their transformation to Datalog LB . The asserted fact types map in the usual way. The invoice total rule uses the subtotal rule, generating a named version of the following relational calculus expression: {i:Invoice, t:Float32 | t = sum{st:AUDValue | ∃li:LineItem (li is on i & li has subtotal value st)}}. Datalog LB includes a function called "total" to sum over sets or bags of numeric values. This function may now be applied to the derived subtotal predicate to derive the invoice total predicate. A special "agg" syntax is used for this as well as other aggregate functions (e.g. counts, minima and maxima). The type declaration and derivation rule for the invoice total is rendered by the following Datalog LB code: Derivation rules and queries are safe only if they are guaranteed to execute in a finite time. Most versions of datalog implement safety using syntactic checks proposed by Ullman (e.g. all head variables must occur in the rule body, and any variables in an arithmetic or relational subgoal must also appear in a positive relational subgoal)  . While efficient to implement, these safety rules are in fact too strong (e.g. see BIB002 ), and we are researching ways to accept rules in a more convenient format that can be transformed into Ullman-safe rules. Apart from more sophisticated support for safety, we plan to extend our ORM-to-Datalog LB conversion to 100% coverage, add support for dynamic rules  , and extend both ORM and our mapping procedures to exploit new features being added to Datalog LB (e.g. existential variables in rule heads).