Abstract
A framework for modeling query semantics as graph properties is presented. In this framework, a single definition of a query automatically gives rise to several semantics for evaluating that query under varying degrees of incomplete information. For example, defining natural joins automatically gives rise to full disjunctions. Two of the proposed semantics have incremental-polynomial-time query-evaluation algorithms for all types of queries that can be defined in this framework. Thus, the proposed framework generalizes previous definitions of semantics for incomplete information and improves previous complexity results for query evaluation.
This work was supported by the Israel Science Foundation (Grant 96/01).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Amer-Yahia, S., Lakshmanan, L.V.S., Pandit, S.: FleXPath: flexible structure and full-text querying for xml. In: Proc. 2004 ACM SIGMOD International Conference on Management of Data (2004)
Cohen, S., Kanza, Y., Sagiv, Y.: Generating relations from XML documents. In: Calvanese, D., Lenzerini, M., Motwani, R. (eds.) ICDT 2003. LNCS, vol. 2572, pp. 282–296. Springer, Heidelberg (2002)
Cohen, S., Sagiv, Y.: Generating all maximal solutions for hereditary, connected-hereditary and rooted-hereditary graph properties, Corr ID: cs.DS/0410039 (2004)
Galindo-Legaria, C.: Outerjoins as disjunctions. In: Proc. 1994 ACM SIGMOD International Conference on Management of Data (1994)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)
Guha, S., Jagadish, H.V., Koudas, N., Srivastava, D., Yu, T.: Approximate xml joins. In: Proc. 2002 ACM SIGMOD International Conference on Management of Data (2002)
Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: On generating all maximal independent sets. Information Processing Letters 27(3), 119–123 (1988)
Kanza, Y., Nutt, W., Sagiv, Y.: Queries with incomplete answers over semistructured data. In: Proc. 18th Symposium on Principles of Database Systems (1999)
Kanza, Y., Sagiv, Y.: Flexible queries over semistructured data. In: Proc. 20th Symposium on Principles of Database Systems (2001)
Kanza, Y., Sagiv, Y.: Computing full disjunctions. In: Proc. 22nd Symposium on Principles of Database Systems (2003)
Libkin, L.: A semantics-based approach to design of query languages for partial information. Semantics in Databases (1995)
Maier, D., Sagiv, Y., Yannakakis, M.: On the complexity of testing implications of functional and join dependencies. J. ACM 28(4), 680–695 (1981)
Mendelzon, A.O., Mihaila, G.A.: Querying partially sound and complete data sources. In: Proc. 20th Symposium on Principles of Database Systems (2001)
Rajaraman, A., Ullman, J.D.: Integrating information by outerjoins and full disjunctions. In: Proc. 15th Symposium on Principles of Database Systems (1996)
Srivastava, D., Amer-Yahia, S., Cho, S.: Tree pattern relaxation. In: Proc. 8th International Conference on Extending Database Technology (2002)
Vardi, M.Y.: On the complexity of bounded-variable queries. In: Proc. 14th Symposium on Principles of Database Systems (1995)
Yannakakis, M.: Algorithms for acyclic database schemas. In: Proc. 7th International Conference on Very Large Data Bases (1981)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cohen, S., Sagiv, Y. (2004). An Abstract Framework for Generating Maximal Answers to Queries. In: Eiter, T., Libkin, L. (eds) Database Theory - ICDT 2005. ICDT 2005. Lecture Notes in Computer Science, vol 3363. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30570-5_9
Download citation
DOI: https://doi.org/10.1007/978-3-540-30570-5_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24288-8
Online ISBN: 978-3-540-30570-5
eBook Packages: Computer ScienceComputer Science (R0)