Welcome to DiSC 2002
SIGMOD 2001
PODS 2001
= PODS'01 Website
= SIGMOD/PODS'01 Plena
<<< = PODS'01 Papers>>>
= Invited Talks
= Award Talks
= Tutorials
SIGMOD RECORD 2001
CIKM 2001
CoopIS 2001
DASFAA 2001
DASFAA 2000
DBPL 2001
Data Engineering Bul
DEXA_EC-WEB 2001
DMKD 2001
DPDJ 2001
HYPERTEXT 2001
ICDE 2001
ICDM 2001
ICDT 2001
JCDL 2001
KDD 2001
KDD_EXPLORATIONS 20
KRDB 2001
MDM 2001
MIR 2001
MIS 2001
RIDE 2001
SBBD 2001
SIGIR 2001
SIGIR FORUM 2001
SSDBM 2001
SSTD 2001
TODS 2001
TIME 2001
VLDB 2001
VLDBJ 2001

Flexible Queries Over Semistructured Data


Yaron Kanza and Yehoshua Sagiv

  View Paper (PDF)  

Return to Querying Web Data


Abstract

Flexible queries facilitate, in a novel way, easy and concise querying of databases that have varying structures. Two different semantics, exible and semiexible, are introduced and investigated. The complexity of evaluating queries under the two semantics is analyzed. Query evaluation is polynomial in the size of the query, the database and the result in the following two cases. First, a semiexible DAG query and a tree database. Second, a exible tree query and a database that is any graph. Query containment and equivalence are also investigated. For the exible semantics, query equivalence is always polynomial. For the semiexible semantics, query equivalence is polynomial for DAG queries and exponential when the queries have cycles. Under the semiexible and exible semantics, two databases could be equivalent even when they are not isomorphic. Database equivalence is formally defined and characterized. The complexity of deciding equivalences among databases is analyzed. The implications of database equivalence on query evaluation are explained.


DiSC'02 © 2003 Association for Computing Machinery