@inproceedings{10.1145/773153.773169,
    Abstract = {A query against a database behind a site like Napster may search, e.g., for all users who have downloaded more jazz titles than pop music titles. In order to express such queries, we extend classical monadic second-order logic by Presburger predicates which pose numerical restrictions on the children (content) of an element node and provide a precise automata-theoretic characterization. While the existential fragment of the resulting logic is decidable, it turns out that satisfiability of the full logic is undecidable. Decidable satisfiability and a querying algorithm even with linear data complexity can be obtained if numerical constraints are only applied to those contents of elements where ordering is irrelevant. Finally, it is sketched how these techniques can be extended also to answer questions like, e.g., whether the total price of the jazz music downloaded so far exceeds a user's budget.},
    Address = {New York, NY, USA},
    Author = {Seidl, Helmut and Schwentick, Thomas and Muscholl, Anca},
    BookTitle = {Proceedings of the Twenty-Second ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems},
    File = {Numerical Document Queries - seidl2003 - a.pdf},
    ISBN = {1581136706},
    Keywords = {Presburger arithmetic, querying XML documents, monadic second order logic, automata},
    Location = {San Diego, California},
    Pages = {155--166},
    Publisher = {Association for Computing Machinery},
    Series = {PODS '03},
    Title = {Numerical Document Queries},
    URL = {https://doi.org/10.1145/773153.773169},
    Year = {2003},
    bdsk-url-1 = {https://doi.org/10.1145/773153.773169},
    date-added = {2023-03-02 20:52:13 +0100},
    date-modified = {2023-03-02 20:52:13 +0100},
    numpages = {12},
    doi = {10.1145/773153.773169}
}

@inproceedings{10.1145/773153.773169, Abstract = {A query against a database behind a site like Napster may search, e.g., for all users who have downloaded more jazz titles than pop music titles. In order to express such queries, we extend classical monadic second-order logic by Presburger predicates which pose numerical restrictions on the children (content) of an element node and provide a precise automata-theoretic characterization. While the existential fragment of the resulting logic is decidable, it turns out that satisfiability of the full logic is undecidable. Decidable satisfiability and a querying algorithm even with linear data complexity can be obtained if numerical constraints are only applied to those contents of elements where ordering is irrelevant. Finally, it is sketched how these techniques can be extended also to answer questions like, e.g., whether the total price of the jazz music downloaded so far exceeds a user's budget.}, Address = {New York, NY, USA}, Author = {Seidl, Helmut and Schwentick, Thomas and Muscholl, Anca}, BookTitle = {Proceedings of the Twenty-Second ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems}, File = {Numerical Document Queries - seidl2003 - a.pdf}, ISBN = {1581136706}, Keywords = {Presburger arithmetic, querying XML documents, monadic second order logic, automata}, Location = {San Diego, California}, Pages = {155--166}, Publisher = {Association for Computing Machinery}, Series = {PODS '03}, Title = {Numerical Document Queries}, URL = {https://doi.org/10.1145/773153.773169}, Year = {2003}, bdsk-url-1 = {https://doi.org/10.1145/773153.773169}, date-added = {2023-03-02 20:52:13 +0100}, date-modified = {2023-03-02 20:52:13 +0100}, numpages = {12}, doi = {10.1145/773153.773169} }