tailieunhanh - Keyword Search in Databases- P18

Keyword Search in Databases- P18:Conceptually, a database can be viewed as a data graph GD(V ,E), where V represents a set of objects, and E represents a set of connections between objects. In this book, we concentrate on two kinds of databases, a relational database (RDB) and an XML database. In an RDB, an object is a tuple that consists of many attribute values where some attribute values are strings or full-text; there is a connection between two objects if there exists at least one reference from one to the other | John 84 4. KEYWORDSEARCHINXMLDATABASES School 0 Classes Dean Class Class Class Class Class Instructor Title Instructor TA Instructor Students Title Title John CS2A John Ben John Ben CS3A CS4A 0. CS5A Title Projects SportsClub Autonet P2P OSP 0 1 Participants Participants Participants 1 1 John Ben Ben Ben Figure Example XML documents Xu and Papakonstantinou 2005 A node u is a sibling of node v if and only if pre u differs from pre v only in the last component. For example Title and Instructor are sibling nodes but Class and Instructor are not sibling nodes. A node u is an ancestor of another node v if and only if pre u is a prefix of pre v . For example Classes is an ancestor John . For simplicity we use u v to denote that pre u pre v . u v denotes that u v or u v. We also use u x v to denote that u is an ancestor of v or equivalently v is a descendant of u. u x v denotes that u x v or u v. Note that if u x v then u v but the other direction is not always true. LCA SLCA ELCA AND CLCA In the following we show the definitions of LCA SLCA Xu and Papakonstantinou 2005 ELCA Guo et al. 2003 and CLCA Li et al. 2007a which are the basis of semantics of answer definitions. Definition Lowest Common Ancestor LCA . For any two nodes vi and v2 u is the LCA of vi and v2 if and only if 1 u x vi and u x v2 2 for any u if u x vi and u x v2 then u x LCA of nodes vi and v2 is denoted as lca v1 v2 . Note that lca v1 v2 is the same as lca v2 vi . Given any three nodes v2 vi v where v2 vi v lca v v2 lca v vi . Given any three nodes v vi v2 where v vi v2 lca v v2 lca v vi . . XML AND PROBLEM DEFINITION 85 a lca vltv2 lca .