Coverart for item
The Resource Generating plans from proofs: the interpolation-based approach to query reformulation, Michael Benedikt, Julien Leblay, Balder ten Cate, Efthymia Tsamoura

Generating plans from proofs: the interpolation-based approach to query reformulation, Michael Benedikt, Julien Leblay, Balder ten Cate, Efthymia Tsamoura

Label
Generating plans from proofs: the interpolation-based approach to query reformulation
Title
Generating plans from proofs: the interpolation-based approach to query reformulation
Statement of responsibility
Michael Benedikt, Julien Leblay, Balder ten Cate, Efthymia Tsamoura
Creator
Contributor
Author
Subject
Language
eng
Summary
Query reformulation refers to a process of translating a source query--a request for information in some high-level logic-based language--into a target plan that abides by certain interface restrictions. Many practical problems in data management can be seen as instances of the reformulation problem. For example, the problem of translating an SQL query written over a set of base tables into another query written over a set of views; the problem of implementing a query via translating to a program calling a set of database APIs; the problem of implementing a query using a collection of web services. In this book we approach query reformulation in a very general setting that encompasses all the problems above, by relating it to a line of research within mathematical logic. For many decades logicians have looked at the problem of converting "implicit definitions" into "explicit definitions," using an approach known as interpolation. We will review the theory of interpolation, and explain its close connection with query reformulation. We will give a detailed look at how the interpolation-based approach is used to generate translations between logic-based queries over different vocabularies, and also how it can be used to go from logic-based queries to programs
Member of
Cataloging source
CaBNVSL
http://library.link/vocab/creatorName
Benedikt, Michael
Dewey number
005.7565
Illustrations
illustrations
Index
no index present
LC call number
QA76.9.D3
LC item number
B454 2016
Literary form
non fiction
Nature of contents
  • dictionaries
  • abstracts summaries
  • bibliography
http://library.link/vocab/relatedWorkOrContributorDate
1979-
http://library.link/vocab/relatedWorkOrContributorName
  • Leblay, Julien
  • Cate, Balder David ten
  • Tsamoura, Efthymia
http://library.link/vocab/subjectName
Querying (Computer science)
Target audience
  • adult
  • specialized
Label
Generating plans from proofs: the interpolation-based approach to query reformulation, Michael Benedikt, Julien Leblay, Balder ten Cate, Efthymia Tsamoura
Instantiates
Publication
Bibliography note
Includes bibliographical references (pages 173-177) and index
Carrier category
online resource
Carrier MARC source
rdacarrier
Color
multicolored
Content category
text
Content type MARC source
rdacontent
Contents
  • 1. Introduction -- 1.1 Overview -- 1.2 First-order logic and databases -- 1.3 Entailment and proofs -- 1.4 Summary -- 1.5 Bibliographic remarks --
  • 2. Vocabulary-based target restrictions -- 2.1 Reformulating queries using interpolation -- 2.1.1 From a semantic property to a first-order reformulation -- 2.1.2 Craig interpolation and beth definability -- 2.1.3 Handling equality -- 2.2 Relativized-quantifier interpolation -- 2.3 Positive existential reformulation -- 2.4 Existential reformulation -- 2.5 The methodology in action -- 2.6 Safety of reformulations -- 2.7 Decidable reformulation -- 2.7.1 Decidable end-to-end reformulation for expressive constraints -- 2.7.2 Reformulation with inclusion dependencies -- 2.7.3 TGDs with terminating chase: positive existential reformulation -- 2.7.4 TGDs with terminating chase: RQFO reformulation -- 2.8 Finite instances and restricted constraints -- 2.9 Summary -- 2.10 Bibliographic remarks --
  • 3. Access methods and integrity constraints -- 3.1 Basics of target restrictions based on access methods -- 3.2 Nested plans -- 3.3 Expressiveness of plan languages -- 3.3.1 Relationship of USPJAD-plans to USPJAD queries -- 3.3.2 Relationship of USPJAD-plans to other formalisms -- 3.4 Semantic properties and entailments related to plans -- 3.5 Statement of the main results on access determinacy and reformulation -- 3.6 Access interpolation -- 3.7 Proving the access interpolation theorem -- 3.8 Extension to non-Boolean queries -- 3.9 Decidable plan-generation -- 3.9.1 The case of inclusion dependencies -- 3.9.2 Constraints with terminating chase -- 3.10 Finite instances and access restrictions -- 3.11 Summary -- 3.12 Bibliographic remarks --
  • 4. Reformulation algorithms for TGDs -- 4.1 Finding plans through chase proofs -- 4.2 Plan search algorithms -- 4.3 Properties of SPJ plan-generation -- 4.4 RA-plans for schemas with TGDs -- 4.4.1 Proof to RA-plan algorithm -- 4.4.2 Correctness of the algorithm -- 4.5 Chase-based and interpolation-based plan-generation -- 4.6 Summary -- 4.7 Bibliographic remarks --
  • 5. Low-cost plans via proof search -- 5.1 Cost functions on plans -- 5.2 How good are proof-based plans? -- 5.2.1 Optimality in terms of methods used -- 5.2.2 Optimality of proof-based plans in runtime accesses -- 5.3 Simultaneous proof and plan search -- 5.4 Beyond prefix proofs and left-deep plans -- 5.5 Summary -- 5.6 Bibliographic remarks --
  • 6. Conclusion -- Bibliography -- Authors' biographies -- Index
Control code
201602DTM043
Dimensions
unknown
Extent
1 PDF (xix, 185 pages)
File format
multiple file formats
Form of item
online
Isbn
9781627059541
Media category
electronic
Media MARC source
isbdmedia
Other control number
10.2200/S00703ED1V01Y201602DTM043
Other physical details
illustrations.
Reformatting quality
access
Specific material designation
remote
System details
System requirements: Adobe Acrobat Reader
Label
Generating plans from proofs: the interpolation-based approach to query reformulation, Michael Benedikt, Julien Leblay, Balder ten Cate, Efthymia Tsamoura
Publication
Bibliography note
Includes bibliographical references (pages 173-177) and index
Carrier category
online resource
Carrier MARC source
rdacarrier
Color
multicolored
Content category
text
Content type MARC source
rdacontent
Contents
  • 1. Introduction -- 1.1 Overview -- 1.2 First-order logic and databases -- 1.3 Entailment and proofs -- 1.4 Summary -- 1.5 Bibliographic remarks --
  • 2. Vocabulary-based target restrictions -- 2.1 Reformulating queries using interpolation -- 2.1.1 From a semantic property to a first-order reformulation -- 2.1.2 Craig interpolation and beth definability -- 2.1.3 Handling equality -- 2.2 Relativized-quantifier interpolation -- 2.3 Positive existential reformulation -- 2.4 Existential reformulation -- 2.5 The methodology in action -- 2.6 Safety of reformulations -- 2.7 Decidable reformulation -- 2.7.1 Decidable end-to-end reformulation for expressive constraints -- 2.7.2 Reformulation with inclusion dependencies -- 2.7.3 TGDs with terminating chase: positive existential reformulation -- 2.7.4 TGDs with terminating chase: RQFO reformulation -- 2.8 Finite instances and restricted constraints -- 2.9 Summary -- 2.10 Bibliographic remarks --
  • 3. Access methods and integrity constraints -- 3.1 Basics of target restrictions based on access methods -- 3.2 Nested plans -- 3.3 Expressiveness of plan languages -- 3.3.1 Relationship of USPJAD-plans to USPJAD queries -- 3.3.2 Relationship of USPJAD-plans to other formalisms -- 3.4 Semantic properties and entailments related to plans -- 3.5 Statement of the main results on access determinacy and reformulation -- 3.6 Access interpolation -- 3.7 Proving the access interpolation theorem -- 3.8 Extension to non-Boolean queries -- 3.9 Decidable plan-generation -- 3.9.1 The case of inclusion dependencies -- 3.9.2 Constraints with terminating chase -- 3.10 Finite instances and access restrictions -- 3.11 Summary -- 3.12 Bibliographic remarks --
  • 4. Reformulation algorithms for TGDs -- 4.1 Finding plans through chase proofs -- 4.2 Plan search algorithms -- 4.3 Properties of SPJ plan-generation -- 4.4 RA-plans for schemas with TGDs -- 4.4.1 Proof to RA-plan algorithm -- 4.4.2 Correctness of the algorithm -- 4.5 Chase-based and interpolation-based plan-generation -- 4.6 Summary -- 4.7 Bibliographic remarks --
  • 5. Low-cost plans via proof search -- 5.1 Cost functions on plans -- 5.2 How good are proof-based plans? -- 5.2.1 Optimality in terms of methods used -- 5.2.2 Optimality of proof-based plans in runtime accesses -- 5.3 Simultaneous proof and plan search -- 5.4 Beyond prefix proofs and left-deep plans -- 5.5 Summary -- 5.6 Bibliographic remarks --
  • 6. Conclusion -- Bibliography -- Authors' biographies -- Index
Control code
201602DTM043
Dimensions
unknown
Extent
1 PDF (xix, 185 pages)
File format
multiple file formats
Form of item
online
Isbn
9781627059541
Media category
electronic
Media MARC source
isbdmedia
Other control number
10.2200/S00703ED1V01Y201602DTM043
Other physical details
illustrations.
Reformatting quality
access
Specific material designation
remote
System details
System requirements: Adobe Acrobat Reader

Library Locations

Processing Feedback ...