F-logic: Introduction to F-logic Elements of F-logic 2.1. Objects and their ID terms 2.2. feature structure (data expression

Size: px

Start display at page:

Download "F-logic: Introduction to F-logic Elements of F-logic 2.1. Objects and their ID terms 2.2. feature structure (data expression"

がんまちゃわんや
5 years ago
Views:

1 F-logic: Introduction to F-logic Elements of F-logic 2.1. Objects and their ID terms 2.2. feature structure (data expressions) 2.3. F-clauses (as non-logical axioms) 2.4. F-structure and entailment 2.5. H-structure (Herbrand structure) 3. entailment 3.1. Inference System 3.2. Inference Rules F-logic by Examples 4.1. Parameteric Polymorphism 4.2. Join in F-logic 4.3. Join in JAVA

3 1.1 MultiSet is defined as a Vector of elements with counters Vector, MultiSet, ElementWithCounter, Element (is defined as) subclass subclasses Write programs just in the way you understand objects and their relationships 3

4 import java.util.vector; // final class MultiSet extends Vector { MultiSet() {capacityincrement=100; // Vector protected void addelement(element element) {// super int index = findindex(element); if (index < 0) super.addelement(new ElementWithCounter(element)); else getelementwithcounter(index).count(); private Element getelement(int i) {// return ((ElementWithCounter)elementAt(i)).getElement(); private ElementWithCounter getelementwithcounter(int i) { return (ElementWithCounter)elementAt(i); private int findindex(element element) {// // // public boolean lessthan(object anotherele) // MultiSet // addelement // Vector Hashtable // ElementWithCounter value key-value for (int i=0; i<size(); i++) if (getelement(i).equals(element)) return i; return -1; void show() { for (int i=0; i<size(); i++) getelementwithcounter(i).show(); System.out.println(); final class ElementWithCounter { private Element element; Element getelement() {return element; private int counter=1; void count() {counter++; ElementWithCounter(Element element) {this.element=element; void show() {System.out.print(counter+" "); element.show(); // String getkey() {return element.getkey(); interface Element { // boolean equals(object x); // void show(); // String getkey(); 4

5 final class MyElement implements Element { private String str; // public String getkey() {return str; MyStr(String str) {this.str = str; public String getkey() {return str; public boolean equals(object x) {return ((MyStr)x).str.equals(str); public void show() {System.out.print(str+", "); // 5

6 1.2 Introduction to F-logic nonlogical axiom Herbarand universe: object ID = Herbrand universe memberof, subclassof, relation, feature/method object ID object = object identity relation mary = mother(john) : ID object paramodulation terminological logic 1. F-logic 2. Write facts, rules and knowledge just in the way you understand objects and their relationships 6

7 1.3 a f b a b join Herbrand universe vr, va VirtualRecord, VirtualAttr 7

8 :- mv(car1) DB JDBC Java 8

9 // Java ResultSet rs = stmt.executequery("select * FROM CUSTOMER"); // rs // while (rs.next()) { String str1 = rs.getstring("name"); int str2 = rs.getint("cust_id"); 1. narrowing or 2. Ψ-, or 3. e.g. a = father(b) fatherof(a,b)... 9

10 2 Elements of F-logic subclass ofmembership(instance of)

11 2.1 Objects and their ID terms 1. x U y U z x U z 2. U binary relation 3. nonlogical axiom 1. x : y x is a member of y x :: y x is a subclass of y 2. child(mary) object X : child(y) :- Y [ child X ] 3. = X : Z : X : Y, Y :: Z 11

12 2.2 feature structure (data expressions) a[m b] a[m {b 1, b 2 ] a[m@p 1, p 2 b] a[m@p 1, p 2 {b 1, b 2 ] a p 1,... m. I ( m )( a, p 1,..., p k ) U I : U F unc(u k+1, U) k=0 I ( m )( a, p 1,..., p k ) P (U) I : U F unc(u k+1, P (U)) k=0 1. a[m b] I ( m )( a ) b 2. a[m {b 1,..., b k ] I ( m )( a ) V and 1. Therefore, semantically { b 1,..., b k V where, F unc : set of partial functions where, P (U) : power set of U a[m {b 1,..., b k ] (a[m {b j ] for j = 1,..., k) 2. abbreviation: a[m b j ] a[m {b j ] 3. ( ) k = X[M B j ] X[M {B 1,..., B k ] j=1 12

13 2.3 F-clauses (as non-logical axioms) F-molecule (molecular formula) ISA assertion o1 : o2, o1 :: o2, object molecule o[data expression;...] F-clause: F-molecule A 1,..., A n : B 1,..., B m ( universally quantified) 1. ISA hierarchy: 45 : integer. "CS":string. "Bob":string. string::datatype.... bob: mnger. bob: facultymember. (no primary class) mnger::employee. facultymember::employee. cs: dept. 2. database facts: (molecule) bob [ name Bob ; age 40; worksfor cs [ dsname CS ; mngr bob; assistants {john,sally ] ] 3. Deductive Rules: E [ boss M ] :- E:employee, D:dept, M:employee, E [ worksfor D [mnger M ] ] 4. entailment : S = mh[boss bob] : mh : faclutymember, mh[worksf or cs]] mh: facultymember CS S = mh[boss bob] 13

14 2.4 F-structure and entailment F-structure;: F = (U, U, U, I, I ) 1. object ID term U 2. instanceof, subclassof, where x U y, y U z x U z 3. U () entailment: For a F-clause A, and a set of F-clauses S, S = A for all F-structure F, F = S F = A def = A for all F-structure F, F = S def A Inference H-structure: Type Inference: 14

15 2.5 H-structure (Herbrand structure) object ID fuctor object universe U identity relation oid 1 = oid 2 oid j object. F = t 1 = t 2 t 1 F = t 2 F def where t F : evaluation under F = X = X. = X = Y Y = X. = X = Z : X = Y, Y = Z. = f(x 1,..., X n ) = f(y 1,..., Y n ) : X 1 = Y 1,..., X n = Y n. john = fatherof(mary) F = john = fatherof(mary) F john fatherof(mary) U 15

16 Herbrand base HB(F ) def set of all ground F-molecules H-structure H def H HB(F ) such that H = α α H for all α HB(F ) (closed under entailment) E [boss M] :- E:employee,D:dept,M:employee, E [worksfor D [ mnger M ]]. (1) Y = Z :- X [M Y], X [M Z]. (2) (1) ground instance (2) ground instance ()\\ 16

17 2.6 H-structure as Working Memory H-structure: 1. H-universe: object ID 2. H-therefore, H-universe a[m b], a:b, a::c name Production System 1. If A then B 2. A 3. H- structure name space working memory 17

18 3 entailment Given S: set of F-molecules, α: ground F-molecule, Qestion: S = α or not Herbrand Theorem (F-logic version): S = α S { α : unsat finite unsat. S [S] { α where [S] set of g-inst. of F-molecules in S β or β [S] F- 3. F-molecules entailment 18

19 3.1 Inference System Qestion: Given unsat S (false in every F-structure) S (1) β, β F-molecules (2)entailment nonlogical axiom S: unsat. set of ground F-clauses S 19

20 3.2 Inference Rules resolution: Hs : As, A A, Bs : Es (Hs, Bs : As, Es)σ where σ : mgu from A to A paramodulation L(t) Bs t 1 = t 2 Cs (L(t 2 ) B C)σ ISA inference: t 1 :: t 2 B t 2 :: t 1 C axiom schema: x :: x (t 1 = t 2 B Cσ t 1 :: t 2 B t 2 :: t3 C t 1 : t 2 B t 2 :: t3 C (t 1 :: t3 B C)σ (t 1 : t3 B C)σ 20

21 3.3 C 1 σ 1,..., C k σ k D there exist D and ζ s.t. Dζ = D C 1,..., C k D C 1,..., C k D mgu 21

22 4 F-logic by Examples 4.1 Parameteric Polymorphism Car:dieselCars(Year) :- Car:car [ enginetype "diesel"; makeyear Year ] nil:list(t). cons(x,y):list(t) :- X:T, Y:list(T). (base) (step) :- cons(mh,cons(bob,nil)):list(empl). (step) :- mh:empl, cons(bob,nil):list(empl). (ISA) mh:empl. :- cons(bob,nil):list(empl). (step) :- bob:empl, nil:list(empl). (ISA) bob:empl :- nil:list(empl). (base) : Prolog import java.util.vector; final class List extends Vector {// Vector final static List nil = new List(); // nil List cons(element element) {insertelementat(element, 0); return this; Element getelement(int index) {return (Element)elementAt(index); abstract class Element { /*. Element list(t) T */ final class Employee extends Element { private String name; private int age; Employee(String str, int age) {name=str; this.age=age; private void show() {System.out.print("["+name+","+age+"], "); public static void main(string args[]) { Employee mh = new Employee("mh",30); Employee bob = new Employee("bob",50); List list = List.nil.cons(mh).cons(bob); for (int i=0;i<list.size();i++) ((Employee)list.getElement(i)).show(); 22

23 4.2 Join in F-logic 1. ( a[attr b]) s1 : student[indv hg, dept physics]. s2 : student[indv bob, dept cs, ta class3]. hg, bob hg : indv[name HG, weight 50, hoby music]. bob : indv[name bob, hoby music]. 2. objectid 3. thus, 4. object objectid p(x,y,z) p(x,y,z) [ name X, weight Y, height Z]. 23

24 1. P, Q, join(p,q,c) join(p,q,c): P Q (denoted by join(p,q,nil)) C nil c( 1, 2, ) 1 = 2 2. P Q new(t1,t2) where (1) rename(attr): Attr (2) new(p tuple, Qtuple)[P Attr V P, rename(qattr) V Q] : P tuple[p Attr V P ], Qtuple[QAttr V Q]. 3. join(p,q,c) C rename join(p,q,cs) new(p tuple, Qtuple) : join(p, Q, nil) : P tuple : P, Qtuple : Q. new(p tuple, Qtuple) : join(p, Q, c(p Attr, QAttr, cs)) : P tuple : P [P Attr V ], Qtuple : Q[QAttr V ], new(p tuple, Qtuple) : join(p, Q, cs). 24

25 Fig. Herbrand universe Fig. 25

26 4.3 Join in JAVA object ID feature-relation Herbrand universe object object(id) (cartecian product) object VirtualAttr VirtualRecord view view import java.util.vector; import common.myio.*; import common.fileprocess.normalcsv; import java.io.*; import common.printobj.*; /* PrintObj : Std (StdOut) (FileOutput) NormalCSV : */ // class Attr (abstract) of real or virtual attrs abstract class Attr { abstract String getname(); abstract int getindex(); abstract void show(printobj po); void show() {show(printobj.stdout); boolean equals(attr attr) { return getname().equals(attr.getname()); // subclass RealAttr of real attrs final class RealAttr extends Attr{ private String attrname; String getname() {return attrname; private int indextoschema;// int getindex() {return indextoschema; RealAttr(String s, int i) {attrname=s; indextoschema=i; void show(printobj po) { 26

27 po.print(attrname+"("+indextoschema+")"); // subclass VirtualAttr of virtual attrs final class VirtualAttr extends Attr{//cartecian product // rename(attr) private Attr originalattr;//pointers to real or virtual attrs Attr getoriginalattr() {return originalattr; private int relationindex; int getrelationindex() {return relationindex; VirtualAttr(Attr ra, int rrindex) { originalattr = ra; relationindex = rrindex; String getname() {// recursion RealAttr.getName return originalattr.getname(); int getindex() {// recursion RealAttr.getIndex return originalattr.getindex(); void show(printobj po) {// recursion RealAttr.show po.print(relationindex+".");originalattr.show(po); // class Record (abstract) of real or virtual records abstract class Record { abstract String getvalue(attr attr);// record_id [ attr value ] void show(attr[] attrs, PrintObj po) { if (attrs.length==0) return; for (int i=0;i<attrs.length-1;i++) po.print(getvalue(attrs[i])+","); po.println(getvalue(attrs[attrs.length-1])); boolean equals(record record2, Condition[] conds) { for (int c=0;c<conds.length;c++) if (!getvalue(conds[c].leftattrofeq()). equals(record2.getvalue(conds[c].rightattrofeq()))) return false; return true; 27

28 // subclass RealRecord of real records final class RealRecord extends Record { private String[] values; RealRecord (String[] ss) {values=ss; String getvalue(attr attr) {// attr must be realattr String s=null; try{ s = values[((realattr)attr).getindex()]; catch (Exception e) { myio.seriouserror("attr for real record not defined: "+e+" : ");attr.show(); ; return s; // subclass VirtualRecord (of product type) final class VirtualRecord extends Record { private Record[] records;// pointers to real or virtual records VirtualRecord(Record[] rs) {records=rs; String getvalue(attr attr) {// attr must be virtual String s=null; try{// VirtualAttr vattr = (VirtualAttr)attr; s = records[vattr.getrelationindex()].getvalue(vattr.getoriginalattr()); catch (Exception e) { myio.seriouserror("attr for virtual record not defined: "+e+" : "); attr.show(); ;// return s; // class Condition {// of LHSAttr = RHSAttr final class Condition { private Attr leftattrofeq, rightattrofeq; Attr leftattrofeq() {return leftattrofeq; Attr rightattrofeq() {return rightattrofeq; Condition(Attr attr1, Attr attr2) {leftattrofeq=attr1; rightattrofeq=attr2; 28

29 // class Relation of relations final class Relation { private String relname; private Attr[] schema; Attr getattr(int index) {return schema[index]; private Vector records = new Vector(); //of record Record getrecord(int index) {return (Record)records.elementAt(index); void addrecord(record record) {records.addelement(record); Relation(String relname, String[] schemainstr) {//create this.relname=relname; schema = new Attr[schemaInStr.length]; for (int i=0;i<schemainstr.length;i++) schema[i] = new RealAttr(schemaInStr[i],i); Relation(String relname, Relation[] relations) {//create product relation this.relname=relname; int nofattrs =0; for (int i=0;i<relations.length;i++) nofattrs=nofattrs+relations[i].schema.length; schema = new Attr[nofAttrs]; int index=0; for (int i=0;i<relations.length;i++) for (int j=0; j<relations[i].schema.length;j++) schema[index++] = new VirtualAttr(relations[i].schema[j], i); Relation join(relation relation, Condition[] conditions) { Relation[] relations = {this, relation; Relation join = new Relation("("+relName+" x "+relation.relname+")", relations); for (int i=0;i<records.size();i++) { Record record1 = getrecord(i); for (int j=0;j<relation.records.size();j++) { Record record2 = relation.getrecord(j); if (!record1.equals(record2, conditions)) continue; Record[] recordpair = {record1, record2; join.addrecord(new VirtualRecord(recordpair)); ; ; return join; void show(attr[] attrs, PrintObj po) { po.println("//--- "+relname+" ---"); for (int i=0;i<attrs.length-1;i++) {attrs[i].show(po); po.print(", ");; attrs[attrs.length-1].show(po);po.println(); for (int i=0;i<records.size();i++) getrecord(i).show(attrs,po); 29

30 void show(printobj po) {show(schema,po); // Relation naturaljoin(relation relation2) { boolean[] properrel2attrs = new boolean[relation2.schema.length]; for (int j=0;j<relation2.schema.length;j++) properrel2attrs[j]=true; Condition[] conds = // properrel2attrs equationsforcommonattrs(relation2.schema, properrel2attrs); Relation join = join(relation2,conds); join.schema = naturaljoinschema(join.schema, properrel2attrs, conds.length); return join; private Condition[] equationsforcommonattrs(attr[] schema2, boolean[] properrel2attrs) { int[] eqcorrespondence = new int[schema.length]; int nofcommonattrs = 0; for (int i=0;i<schema.length;i++) { boolean flag=false; for (int j=0; j<schema2.length;j++) if (schema[i].equals(schema2[j])) { eqcorrespondence[i]=j; properrel2attrs[j]=false; nofcommonattrs++; flag=true; break; ; if (!flag) eqcorrespondence[i]=-1; ; Condition[] equations = new Condition[nofCommonAttrs]; nofcommonattrs = 0; for (int i=0;i<schema.length;i++) { if (eqcorrespondence[i] < 0) continue; equations[nofcommonattrs++] = new Condition(schema[i], schema2[eqcorrespondence[i]]); ; return equations; private Attr[] naturaljoinschema(attr[] productschema, boolean[] properrel2attrs, int nofcommonattrs) { Attr[] newschema = new Attr[productSchema.length - nofcommonattrs]; for (int i=0;i<schema.length;i++) newschema[i] = productschema[i]; int index=schema.length; for (int j=0;j<properrel2attrs.length;j++) if (properrel2attrs[j]) newschema[index++]=productschema[schema.length+j]; return newschema; 30

31 // class LoadRelation of task objects for loading CSV final class LoadRelation extends NormalCSV { private Relation relation; Relation loadrelation(string[] args) { csvfileprocessing(args); return relation; protected String inputformmessage() {return "LoadRelation CsvFileName"; protected String defineinputfilename(string[] args) {return args[0]; protected void processcommandline(string[] args) { protected void setparameters() { relation = new Relation(getInputFileName(), getcsvattrs()); protected void processtuple(string[] tuple, int datalinenumber) { relation.addrecord(new RealRecord(tuple)); protected void postprocessing(){ // class TestJoin { final class TestJoin { public static void main(string args[]) { StdOut stdout = PrintObj.stdout; if (args.length!=3) myio.seriouserror(" CsvFile1 CsvFile2 outputcsv"); Relation[] rels = new Relation[2]; for (short j=0;j<2;j++) { String[] newargs = {args[j]; rels[j] = new LoadRelation().loadRelation(newArgs); // rels[j].show(stdout); ; // rels[0].naturaljoin(rels[1]).show(stdout); FileOutput output = new FileOutput(args[2]); rels[0].naturaljoin(rels[1]).show(output); output.close(); System.out.println("+++ "+args[2]+" "); 31

ALG ppt

ALG ppt 2012 6 21 (sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/lecture/alg/2012/index.html 1 l l O(1) l l l 2 (123 ) l l l l () l H(k) = k mod n (k:, n: ) l l 3 4 public class MyHashtable