Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Keyword Search in Databases- P19: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 | 4.2. SLCA-BASED SEMANTICS 89 4.2.1 PROPERTIES OF LCA AND SLCA Property 4.9 Given a set S and two nodes v and Vj with v Vj then closest vi S closest vj S . Proof. We prove it by contradiction by assuming that closest vi S closest vj S . Then closest vi S rm vi S and closest vj S lm vj S rm vi S lm vj S . Recall that closest v S is chosen from lm v S and rm v S and lm vi S lm vj S and rm vi S rm vj S if all exists. If lm vj S rm vi S then lm vj S lm vi S therefore lm vi S lm vj S by the fact that lm vi S lm vj S . Similarly we can get that rm vi S rm vj S . Also we can learn that lm vi S rm vi S otherwise closest vi S lm vi S . Let lm denote lm vi S and rm denote rm vi S . It holds that lm vi vj rm. According to Property 4.2 lca lm vj lca lm vi and lca rm vi lca rm vj . According to the definition of closest lca lm vi x lca rm vi and lca rm vj lca lm vj which is a contradiction. Property 4.10 Let V and U be lists of nodes e.g. V Vi vi and U ui ui such that V U e.g. v Ui for 1 i l. Let lca V and lca U be the LCA of nodes in V and U respectively. Then 1. if lca V lca U then lca U lca V 2. if lca V lca U then either lca V x lca U or lca V f lca U then for any W with U W lca V f lca W . Proof. This is an extension of Property 4.3 to more than two nodes. The proof is by induction when V and U contain only two nodes it is proven in Property 4.3. Assume that it is true for V U and W we prove it is true for V U W where V V U vi U U U ui with Vl ui. One important property of lca is that lca V lca lca V Vl . If lca U lca V then either lca U lca V or lca V lca U . Otherwise lca V lca U according to Property 4.3 there are three cases of lca V and lca U and we only need to prove the last case i.e. the case that lca V f lca U . Then for any W W U wi if lca U lca W then we are done otherwise lca W lca U then lca V f lca W because lca W lca W . 90 4. KEYWORD SEARCH IN XML DATABASES Tai ble 4.0 id ki k2 kl idm id2 idi Figure 4.3 Stack Data Structure 4.2.2 EFFICIENT ALGORITHMS FOR .
