tailieunhanh - Keyword Search in Databases- P19

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 | . SLCA-BASED SEMANTICS 89 PROPERTIES OF LCA AND SLCA Property 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 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 Let V and U be lists of nodes . V Vi vi and U ui ui such that V U . 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 to more than two nodes. The proof is by induction when V and U contain only two nodes it is proven in Property . 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 there are three cases of lca V and lca U and we only need to prove the last case . 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 id ki k2 kl idm id2 idi Figure Stack Data Structure EFFICIENT ALGORITHMS FOR .