Transcript ppt file - NUS School of Computing

XDO2: A Deductive Object-Oriented
Query Language for XML
Wei Zhang1, Tok Wang Ling1, Zhuo Chen1, and Gillian Dobbie2
School of Computing
National University of Singapore1
Department of Computer Science
University of Auckland
New Zealand2
1
Outline
•
•
•
•
•
Background and Motivation
XDO2 Database Example
XDO2 Language Features
 Simple and compact
 Compact query return format
 Multi-valued variables and aggregate functions
 Separating structure and value
 Not-predicate negation
 Recursion querying
Comparison with Related Work
Conclusion and Future Work
2
Background - XTree
•
XTree [1] is a generalization of and has advantages over XPath





•
XTree uses [ ] to group same level attributes and elements
together
One XPath expression defines one variable vs one XTree expression
defines multiple variables
XPath cannot define return format. However, XTree can define
return format
Multi-valued variables expressed explicitly in XTree using { } vs no
syntactic difference in XPath
Element tags (attribute names) separated from values in XTree
using stru  value vs use of functions to separate structure and
value pairs in XPath
In short, XTree is designed to have a tree structure while XPath
does not
[1] Z. Chen, T.W. Ling, M.C. Liu, and G. Dobbie. XTree for declarative XML querying.
In Proceedings of DASFAA, pages 100-112, Korea, 2004
3
Motivation
•
•
Our proposed XDO2 is a novel XML query language which is
based on XTree and has deductive features such as deductive
rules and negation, and some object-oriented features such as
inheritance and methods
Major contributions of XDO2




Negation: supported using not-predicate instead of conventional
logical negation as used in XQuery
Derived attributes/methods: implemented as (recursive) deductive
rules to deduce new properties
(Multiple) Inheritance: enables a subclass object to inherit the
properties from its superclass objects
Multiple variables in one expression, compact return format,
explicitly expresses multi-valued variables, and separates structure
from value
4
XDO2 Database Example –
Company XML data
<root>
<person pno=“p1”>
<name>John</name>
<address>
<street>King Street</street>
<city>Ottawa</city>
</address>
<birthyear>1975</birthyear>
<sex>Male</sex>
</person>
<person pno=“p2”>
<spouse pno=“p3” />
<name>Mike</name>
<address>
<street>Albert</street>
<city>Ottawa</city>
</address>
<birthyear>1954</birthyear>
<sex>Male</sex>
</person>
<person pno=“p3”>
<spouse pno=“p2” />
<name>Mary</name>
<address>
<street>Albert</street>
<city>Ottawa</city>
</address>
<birthyear>1958</birthyear>
<sex>Female</sex>
</person>
<company cno=“c1”>
<name>Star</name>
<employee eno=“e1” pno=“p1”>
<salary>6000</salary>
<hobby>Tennis</hobby>
<hobby>Soccer</hobby>
</employee>
<employee eno=“e2” pno=“p2”>
<salary>4000</salary>
<hobby>Tennis</hobby>
</employee>
</company>
</root>
5
XDO2 Database Example –
ORA-SS Schema Diagram
root
company
person
ISA
pno name
street
address
birthyear, sex
D:2004
city
employee
spouse
cno name
age bachelor
pno
eno
pno
+
salary hobby
Fig 1: ORA-SS schema diagram
6
XDO2 Database Example Schema Features
•
•
Two derived attributes using rules
 age derived attribute in person class
 bachelor derived attribute in person class
Inheritance
 Employee class is a subclass of person class and inherits all
the properties of person class (attributes and derived
attributes)
7
XDO2 Database Example –
Derived Attribute Age
Rule R1 defines that the age of a person is 2005 minus his/her
birthyear.
(R1)



$p/age : $a :- /root/person : $p/birthyear : $b,
$a = 2005 - $b.
Notation “:-” is to specify if the right hand side (body) is
true, then the left hand side (head) is true.
Notation “:” assigns the value of left hand side to the right
hand side. If the left hand side is an object class, then the
right hand side binds to the object identifier, such as person.
Single-valued variables are denoted by “$” followed by a
string literal.
8
XDO2 Database Example –
Derived Attribute Bachelor
Rule R2 defines that a person is a bachelor if he is a male and without
spouse.
(R2)



$p/bachelor : true :- /root/person : $p/
[sex : “Male”, not(spouse : $s)].
Notation “[ ]” is to group the same level properties (attributes,
derived attributes) together which are defined under the same
parent object
Notation “not” is to negate the existence of enclosed term
Two Boolean values true and false are reserved
[2] T.W. Ling. The prolog not-predicate and negation as failure rule.
New Generation Computing, 8(1):5-31, 1990
9
XDO2 Database Example –
Inheritance
The following statement defines that employee object class is a
subclass of person object class.
employee ISA person
by employee.pno ISA person.pno

Notice the first part of the statement defines the class
inheritance while the second part of the statement defines
the object inheritance
10
XDO2 Database Example –
Query
(Eg1) Find the age and salary of all employees who are bachelors,
with age less than 30, and salary larger than 5000.
/db/youngRichBachelor : $e/[age : $a, payroll : $s]  /root/company/
employee : $e/[age : $a, bachelor : true, salary : $s],
$a < 30, $s > 5000.



Notation “” is to specify the left hand side is used to construct
the XML result and the right hand side is the query and the
conditional parts
Derived attributes age and bachelor specified in rule R1 and rule
R2 are used directly in the query
age and bachelor properties are inherited from the person class by
employee being a subclass of person class
11
XDO2 Database Example –
Query Result
Using the LHS result construction expression of example 1, we can
generate the following XML data result.
<db>
<youngRichBachelor eno=“e1”>
<age>29</age>
<payroll>6000</payroll>
</youngRichBachelor>
</db>
Note: $e which binds to the object identifier of employee, is used
as the value of the result element youngRichBachelor
12
XDO2 Language Features

Simple and compact query expression
(Eg2) Find the year and title of each book, and its authors’ last name
and first name.
XDO2 expression:
/bib/book/[@year : $y, title : $t, author/[last : $l, first : $f]]
XPath expressions:
$book in /bib/book, $y in $book/@year, $t in $book/title,
$author in $book/author, $last in $author/last, $first in $author/first



One XDO2 expression corresponding to 6 XPath expressions
Using [ ] to group the same level attributes, elements, and/or methods
together to have a tree structure.
$book and $author are needed in XPath expressions
13
XDO2 Language Features

Compact result format
(Eg3) List the titles and publishers of books which are published after 2000.
XDO2 query expression:
/result/recentbook/[title : $t, publisher : $p]  /bib/book/[@year : $y,
title : $t, publisher : $p], $y > 2000.
XQuery expression:
for $book in /bib/book, $y in $book/@year, $t in $book/title, $p in
$book/publisher
where $y > 2000
return <result><recentbook>{$t} {$p}</recentbook></result>

One XDO2 expression is used for query result format while XML element
tags is mixed with the XPath expressions in XQuery
14
XDO2 Language Features

Multi-valued variables and aggregate functions
(Eg4) List the titles of the book which has more than 1 author.
XDO2 query expression:
/result/multiAuthorBook/title : $t 
/bib/book/[title : $t, author : <$a>], <$a>.count() > 1.
XQuery expression:
for $book in /bib/book, $t in $book/title
let $a in $book/author
where count($a) >1
return
<result><multiAuthorBook>{$t}</multiAuthorBook></result>


Multi-valued variables are denoted by < > (list-valued) or { } (setvalued)
Object-oriented fashion built-in aggregate functions instead of
function based fashion
15
XDO2 Language Features

Separating structure from value
(Eg5) Get sub-element with value “John” in some person element.
XDO2 query expression:
$ele  /root/person/$ele : “John”.
XQuery expression:
for $b in /root/person/*
where string($b) = “John”
return local-name($b)


Using stru : value to separate the structure from the value
naturally
In XQuery, built-in functions string() and local-name() have to be
used to get values and structures respectively
16
XDO2 Language Features

Not-predicate negation (nested)
(Eg6) To retrieve the name of the company where every employee has
hobby “Tennis”.
XDO2 query expression:
/db/allLikeTennisCom : $n  /root/company : $c/name : $n,
$c/not(employee/not(hobby : “Tennis”)).
XQuery expression:
for $c in /root/company
where EVERY $e IN $c/employee SATISFIES
SOME $h IN $e/hobby SATISFIES string($h) = “Tennis”
return <db><allLikeTennisCom>{string($c/name)}
</allLikeTennisCom></db>

XDO2 query expression is much simpler and more compact using the
not-predicate compared with XQuery, which needs keyword “EVERY”,
“SOME”, “IN”, SATISFIES”
17
XDO2 Language Features

Not-predicate negation (sub-tree)
(Eg7) To retrieve the companies which do not have an employee who
has sex “Male” and birthyear 1975.
XDO2 query expression:
/db/company : $c  /root/company : $c/not(employee/
[sex : “Male”, birthyear : 1975]).
XQuery expression:
for $c in /root/company
where NOT (SOME $e IN $c/employee SATISFIES ($e/sex = “Male”
AND $e/birthyear = 1975))
return <db>{$c}</db>

Using the not-predicate on a subtree structure, XDO2 expression is more
compact while XQuery needs “NOT”, “SOME”, “IN”, “SATISFIES”, “AND”.
[2] T.W. Ling. The prolog not-predicate and negation as failure rule.
New Generation Computing, 8(1):5-31, 1990
18
XDO2 Language Features

Recursion querying
(Eg8) Suppose there is a sub-element child directly under the person
element. The following deductive rules define descendants of person.
$p/descendant : $c :- /root/person : $p/child : $c.
$p/descendant : $d :- /root/person : $p/child : $c, $c/descendant : $d.
To retrieve all the descendants of a person with pno ‘p1’.
/db/person_p1/descendant : $d  /root/person : ‘p1’/descendant : $d.

for each descendant of person with pno value ‘p1’, single-valued
variable $d will bind to the descendant’s identifier and output the
result. The recursive rules are recursively used to infer all the
person’s descendants.
19
Comparison with Related Work
XDO2
XQuery
XTreeQuery
F-logic [9]
XML_RL [8]
Underlying data
XML tree
XML tree
XML tree
Object
XML tree
Path expression
XTree
XPath
XTree
Deductive rule
Yes
Recursive
rule
Notpredicate
No
Recursive
function
Logical
negation
No
Recursive
query
Logical
negation
Path
expression
Yes
Logical
negation
XTree-like
expression
Partial
Recursive
query
Logical
negation
No need
Yes
Yes
Yes
Yes
Yes
No
Yes
No
Yes
Yes
No
Yes
Yes
Yes
Yes
No
No
Yes
No
Recursion
Negation
Quantification
Multi-valued
variable
Direct structure
querying
Object-oriented
features
Recursive rule
[8] M.C. Liu. A logical foundation for XML. In CAiSE, pages 568-583, 2002.
[9] M. Kifer, G. Lausen, and J. Wu. Logical foundations of object-oriented and frame-based languages.
Journal of ACM, 42(4):741-843, 1995.
20
Conclusion
•
•
A novel new XML query language XDO2 which is
based on XTree and has deductive and objectoriented features. The relationship between XDO2
and XQuery is similar to the relationship between
Datalog and SQL
XDO2 queries are simpler and more compact than
current XML query languages such as XQuery
because XDO2 is based on XTree, and supports
(recursive) deductive rules and the not-predicate.
21
Conclusion – Cont’d
•
Important features and contributions of XDO2
 Negation: supported using not-predicate instead
of conventional logical negation as used in XQuery
 Derived attributes/methods: implemented as
(recursive) deductive rules to deduce new
properties
 (Multiple) Inheritance: enables a subclass object
to inherit the properties from its superclass objects
 Multiple variables in one expression, compact
return format, explicit multi-valued variables, and
separating structure from value are supported
naturally due to XTree
22
Future Work
•
•
How to evaluate the XDO2 queries efficiently?
Especially those queries involving recursive deductive
rules and not-predicate.
Approaches for XDO2 queries evaluation?
Datalog like bottom-up approach
Prolog like top-down approach
Combining both
23
References
[1] Z.Chen, T.W. Ling, M.C. Liu, and G.Dobbie. XTree for declarative XML querying. In
Proceedings of DASFAA, pages 100-112, Korea, 2004.
[2] T.W. Ling. The prolog not-predicate and negation as failure rule. New Generation
Computing, 8(1):5-31, 1990.
[3] T.W. Ling and M.L. Lee and G. Dobbie. Semistructured Database Design. Springer,
2005.
[4] T.W. Ling and W.B.T. Lee. DO2: A deductive object-oriented database system. In
proceedings of the 9th International Conference on Database and Expert System
Applications, pages 50-59, 1998.
[5] M.C. Liu and T.W. Ling. Towards declarative XML querying. In Proceedings of WISE,
pages 127-138, Singapore, 2002.
[6] M.C. Liu, G. Dobbie, and T.W. Ling. A logical foundation for deductive object-oriented
databases. ACM Transactions Database Systems, 27(1):117-151, 2002.
[7] M. Kifer, G. Lausen, and J. Wu. Logical foundations of object-oriented and framebased languages. Journal of ACM, 42(4):741-843, 1995.
[8] M.C. Liu. A logical foundation for XML. In CAiSE, pages 568-583, 2002.
[9] M. Kifer, G. Lausen, and J. Wu. Logical foundations of object-oriented and framebased languages. Journal of ACM, 42(4):741-843, 1995.
[10]M.C. Liu and T.W. Ling. Towards declarative XML quering. In Proceedings of WISE,
pages 127-138, Singapore, 2002.
24
The End
•
Thank You!
•
Any Questions?
25