Flexible Queries over Semistructured Data
Summary: Introduces flexible and semiflexible semantics for semistructured queries; proves polytime evaluation for (i) semiflexible DAG queries on tree DBs and (ii) flexible tree queries on arbitrary graph DBs. Shows flexible query equivalence is polytime, semiflexible equivalence is poly for DAGs but exponential with cycles; defines non‑isomorphic database equivalence and analyzes its complexity and impact on evaluation. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Yaron Kanza
- 2. Yehoshua Sagiv
Incoming Citations (Sorted by Pagerank)
Showing 11 of 11 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 257 | Making Database Systems Usable | 2007 | SIGMOD | 0.00030223397 |
| 434 | XSEarch: A Semantic Search Engine for XML | 2003 | VLDB | 0.0002328559 |
| 1,812 | Expressive Languages for Path Queries over Graph-Structured Data | 2010 | PODS | 0.00010467069 |
| 5,575 | Structure and Content Scoring for XML | 2005 | VLDB | 5.4264592e-05 |
| 7,143 | A Graph Database for a Virtualized Network Infrastructure | 2018 | SIGMOD | 4.8191495e-05 |
| 7,609 | A System for Keyword Proximity Search on XML Databases | 2003 | VLDB | 4.6966255e-05 |
| 9,188 | Querying Virtual Hierarchies using Virtual Prefix-Based Numbers | 2014 | SIGMOD | 4.3770416e-05 |
| 11,780 | Virtualized Network Service Topology Exploration Using Nepal | 2017 | SIGMOD | 4.1945683e-05 |
| 12,025 | A Social Network Database that Learns How to Answer Queries | 2013 | CIDR | 4.1945683e-05 |
| 12,253 | Using XMorph to Transform XML Data | 2010 | VLDB | 4.1945683e-05 |
| 12,563 | Database-Inspired Search | 2005 | VLDB | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 0 of 0 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 9,535 | Graph Data Models, Query Languages and Programming Paradigms | 2018 | VLDB | 4.3265843e-05 |
| 12,297 | Equivalence of SQL Queries In Presence of Embedded Dependencies | 2009 | PODS | 4.1945683e-05 |
| 8,851 | Efficient Approximations of Conjunctive Queries | 2012 | PODS | 4.4363908e-05 |
| 6,948 | Semantic Acyclicity on Graph Databases | 2013 | PODS | 4.8898337e-05 |
| 2,099 | Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries | 2018 | VLDB | 9.5479391e-05 |
| 5,195 | Equivalence of Queries Combining Set and Bag-Set Semantics | 2006 | PODS | 5.6366303e-05 |
| 4,038 | Querying Complex Structured Databases | 2007 | VLDB | 6.5082212e-05 |
| 431 | On the Complexity of Database Queries (Extended Abstract) | 1997 | PODS | 0.00023370207 |
| 1,037 | Querying Graph Databases | 2013 | PODS | 0.00014502493 |
| 3,681 | Queries with Incomplete Answers over Semistructured Data | 1999 | PODS | 6.8492288e-05 |